Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Greedy Search
Kurze Frage zu Greedy Search:
Es wird immer unter allen bereits besuchten States geschaut, wo der nächste Knoten mit dem geringsten Heuristikwert ist (und nicht nur vom aktuellen State aus)?
Normalerweise wird auch nicht gespeichert, ob man States schon mehrmals besucht hat, weswegen der Suchbaum unendlich groß werden kann und man in einer Endlosschleife landet?
der nächste noch-nicht-expandierte Knoten, richtig.
Das sind halt gewissermaßen zwei varianten von greedy; im zweifelsfalle in der Klausur einfach für beide Varianten antworten 
Aber wenn man antworten begründet, was man natürlich immer sollte, wird uns ja auch klar von welcher variante du ausgehst
Korrekt, Greedy Suche ist Best-First Suche (Breitensuche mit sortierter Knotenwarteschlange), bei der diese nach der Goaldistanz sortiert wird.
Wenn man nur vom aktuellen Zustand aus den nächstbesten Zustand auswählt ist es Hill Climbing (Tiefensuche).
So verstehe ich das auch; bei Zyklen kann sich die Greedy Suche aufhängen, da nicht wie bei A* noch die Pfadkosten addiert werden.
EDIT: Jazzpirate war wohl schneller
Würde mal nicht Hill Climbing und Tiefensuche vermischen.
übung 4.1:
What is the fundamental difference between Greedy Search and Hill Climbing? Explain.
Solution: HC is local search, i.e. the path is not kept because we are only interested in finding
a solution and not how we got there.
Bei Tiefensuche (Depth-first search?) ist der Pfad durchaus relevant…
1 „Gefällt mir“
Man muss den Pfad ja nicht speichern.
Hill-climbing (gradient ascent/descent) p.164:
Depth-first search with heuristic and w/o memory
Stimmt, aber die Begründung kann ich nur bedingt nachvollziehen. Ein fundamentaler Unterschied ist meiner Meinung nach, dass die Vorgehensweise komplett unterschiedlich ist: Greedy Search expandiert ganz andere Knoten und kann zu nicht expandierten Knoten springen, wenn dort die Heuristik bessere Werte liefert (da BFS). Hill Climbing wird das nicht machen, und mit Scheuklappen weiter in eine Richtung klettern.
…anders ausgedrückt: Der Unterschied ist nur die Menge der möglichen Knoten, die als nächstes expandiert werden können. Bei Greedy ist das die Menge aller bisher gefundenen, nicht-expandierten Knoten (und deren Pfade), bei Hill Climbing sind es nur die Nachbarn des aktuellen Knoten. Der Kernalgorithmus, i.e. „pick den Knoten mit der höchsten utility“ ist der selbe.
Oder anders ausgedrückt: Der Unterschied ist genau die Lokalität. Hill climbing ist local, greedy nicht.
2 „Gefällt mir“