Not logged in. · Lost password · Register

Baum
Member since Jul 2014
16 posts
Subject: 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?
Jazzpirate
Member since Oct 2016
803 posts
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)?
der nächste noch-nicht-expandierte Knoten, richtig.

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?
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 ;-)
since
Member since Oct 2014
21 posts
In reply to post #1
Quote by Baum:
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)?
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).

Quote by Baum:
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?
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
nakami
Avatar
Member since Sep 2013
250 posts
+1 Shadow992
Quote by since:
Wenn man nur vom aktuellen Zustand aus den nächstbesten Zustand auswählt ist es Hill Climbing (Tiefensuche).

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...
video resources on computer science related topics:
https://gist.github.com/nakami/fdb78d1e79f4702e018833fa948…

There are two kinds of people in the world:
1. Those who can extrapolate from incomplete data
since
Member since Oct 2014
21 posts
Quote by nakami:
Würde mal nicht Hill Climbing und Tiefensuche vermischen.
[...]
Bei Tiefensuche (Depth-first search?) ist der Pfad durchaus relevant...
Man muss den Pfad ja nicht speichern.

Hill-climbing (gradient ascent/descent) p.164:
Depth-first search with heuristic and w/o memory


Quote by nakami:
ü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.
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.
Jazzpirate
Member since Oct 2016
803 posts
+2 nakami, since
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.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen