Iterative Tiefensuche |
infoubi
Jungspund
Dabei seit: 30.07.2015
Beiträge: 14
|
|
Kann mir jemand erklären, was bei der iterativen Tiefensuche genau passiert? Mir fällt es schwer, den Unterschied zur normalen Breitensuche zu erkennen.
Also bei der Tiefensuche geht man von einem Knoten aus einfach mal bis ganz in die Tiefe. Kommt dann wieder zurück und macht das Selbe beim nächsten Knoten.
Bei der Breitensuche geht man von der Wurzel zum linken und rechten Knoten. Dann geht man einen Knoten weiter, wieder zum linken und rechten (bzw eifach zu allen direkte Erreichbaren).
Und die iterative Tiefensuche soll ja ein Mix aus beiden sein. Und ich weiss, dass man zuerst die Höhe 1 absucht, dann die Höhe 2 etc.
Aber macht man das nicht eigentlich genau bei der Breitensuche?
Was ist genau der Vorteil zur Breitensuche?
Der Vorteil gegenüber der normalen Tiefensuche scheint mir klar, da man bei der normalen Tiefensuche jenachdem "unendlich" tief geht, und das Gesuchte lange nicht oder gar nie findet..
|
|
01.08.2015 16:17 |
|
|
|
Die iterative Tiefensuche ist eine Tiefensuche mit maximaler Tiefe. So kannst du verhindern, dich in einem endlos langen Pfad zu verfangen, während im anderen Ast die Lösung zum Greifen nahe wäre. Wird bei der festgelegten Tiefe nichts gefunden, wird die Tiefe erhöht und von vorn gestartet.
Im Gegensatz zur Breitensuche werden dabei nicht alle erreichten Knoten im Arbeitsspeicher abgelegt, sondern nur der aktuelle Ast. Das heißt aber auch, dass du bei jeder Erhöhung der Tiefe wieder ganz von vorn beginnen musst, da ja keine Zwischenergebnisse abgespeichert sind.
__________________ Syntax Highlighting fürs Board (Link)
|
|
01.08.2015 18:47 |
|
|
infoubi
Jungspund
Dabei seit: 30.07.2015
Beiträge: 14
|
|
ok, vielen dank!
das mit dem arbeitsspeicher war mir nicht bewusst!
vielen dank für deine (erneute) hilfe!
|
|
01.08.2015 20:18 |
|
|
|