Kürzlich habe ich mir ein paar gierige Algorithmusprobleme angesehen. Ich bin verwirrt über lokal optimal. Wie Sie wissen, bestehen gierige Algorithmen aus lokal optimalen Möglichkeiten. Aber die Kombination lokal optimaler Entscheidungen bedeutet nicht unbedingt global optimal, oder?
Machen Sie als Beispiel eine Änderung: Verwenden Sie die geringste Anzahl von Münzen, um 15 ¢ zu machen, wenn wir es getan haben 10 ¢, 5 ¢ und 1 ¢ Münzen können Sie dies mit einem 10 ¢ und einem 5 ¢ erreichen. Aber wenn wir eine 12 ¢ -Münze hinzufügen, schlägt der Greedy-Algorithmus fehl, da (1 × 12 ¢ + 3 × 1 ¢) mehr Münzen verwendet als (1 × 10 ¢ + 1 × 5 ¢).
Betrachten Sie einige klassische Greedy-Algorithmen, z. Huffman, Dijkstra. Meiner Meinung nach sind diese Algorithmen erfolgreich, da sie keine degenerierten Fälle haben, was bedeutet, dass eine Kombination von lokal optimalen Schritten immer gleich global optimal ist. Verstehe ich richtig?
Wenn mein Verständnis stimmt, gibt es eine allgemeine Methode, um zu prüfen, ob ein Greedy-Algorithmus optimal ist?
Ich habe einige Diskussionen über gierige Algorithmen an anderer Stelle auf der Website gefunden. Das Problem geht jedoch nicht zu sehr ins Detail.
Im Allgemeinen ist eine lokal optimale Lösung immer dann ein globales Optimum, wenn das Problem konvex ist. Dies beinhaltet lineare Programmierung; quadratische Programmierung mit einem positiv definierten Ziel; und nichtlineare Programmierung mit einer konvexen Zielfunktion. (NLP-Probleme neigen jedoch dazu, eine nicht konvexe Zielfunktion zu haben.)
Die heuristische Suche gibt Ihnen ein globales Optimum mit lokal optimalen Entscheidungen, wenn die heuristische Funktion bestimmte Eigenschaften hat. Konsultieren Sie ein AI-Buch für Details dazu.
Im Allgemeinen, wenn das Problem nicht konvex ist, kenne ich keine Methoden zum Nachweis der globalen Optimalität einer lokal optimalen Lösung.
Es gibt einige Theoreme, die Probleme ausdrücken, für die gierige Algorithmen in Bezug auf Matroide optimal sind (auch: Gieroide.) Siehe Wikipedia-Abschnitt für Details: Ссылка
Ein gieriger Algorithmus schafft es fast nie, die optimale Lösung zu finden. In den Fällen, in denen dies der Fall ist, hängt dies stark vom Problem selbst ab. Wie Ted Hopp erklärte, kann man bei konvexen Kurven das globale Optimum finden, wenn man davon ausgeht, dass man das Maximum der Zielfunktion natürlich finden sollte (umgekehrt funktionieren konkave Kurven auch, wenn man minimieren möchte). Sonst werden Sie fast sicher in den lokalen Optima stecken bleiben. Dies setzt voraus, dass Sie die Zielfunktion bereits kennen.
Ein weiterer Faktor, der mir einfällt, ist die Nachbarschaftsfunktion. Bestimmte Stadtteile werden, wenn sie groß genug sind, sowohl die globalen als auch die lokalen Maxima umfassen, so dass Sie die lokalen Maxima vermeiden können. Sie können jedoch die Nachbarschaft nicht zu groß machen oder die Suche wird langsam.
Mit anderen Worten, ob Sie ein globales optimales oder nicht mit gierigen Algorithmen finden, ist problemspezifisch, obwohl Sie in den meisten Fällen nicht das global optimale finden.
Sie müssen ein Zeugenbeispiel entwerfen, bei dem Ihre Prämisse, dass der Algorithmus ein globaler Algorithmus ist, fehlschlägt. Entwerfen Sie es nach dem Algorithmus und dem Problem.
Ihr Beispiel für den Münzwechsel war nicht gültig. Münzen sind absichtlich so konstruiert, dass alle Kombinationen möglich sind, aber nicht um Verwirrung zu stiften. Ihre Hinzufügung von 12c ist nicht garantiert und ist extra.
Bei Ihrem Zusatz ist das Problem nicht der Münzwechsel, sondern ein anderer (obwohl das Thema Münzen sind, können Sie das Beispiel ändern, was Sie wollen). Dafür hast du selbst ein Zeugenbeispiel gegeben, um zu zeigen, dass der gierige Algorithmus für dieses Problem in einem lokalen Maximum steckenbleibt.