In computer science, tree traversal is the process of visiting each node in a tree data structure. Tree traversal, also called walking the tree, provides for sequential processing of each node in what is, by nature, a non-sequential data structure. Such traversals are classified by the order in which the nodes are visited.
tree traversal. visiting each node in a tree data structure. das abgehen der einzelnen knoten eines baumes. ich nehm den wiki-artikel als referenz, weil ich
nicht sagen möchte "das heißt so und so" ...
natürlich kann man sich hier streiten (deswegen dieser beitrag hier), aber korrekt lautet, meiner meinung nach, die Technik (!): Depth (eigentlich breadth *g*)-First Traversal ... was man dann macht ist die depth-first search... also die suche...
drück ich mich eh nicht unklar aus? lol
und ja, ich nehms gern genau ... ich finde, das gehört auch irgendwie so ^^ ansonstn kann man ja gleich einfach nur irgendwas hinschmeißn ... und dafür
mach ich mir dann ehrlich gesagt keine arbeit.
Registriert: Do Sep 25, 2003 15:56 Beiträge: 7804 Wohnort: Sachsen - ERZ / C
Programmiersprache: Java (, Pascal)
Öhm...ich hab das gerade geändert...ohne das ich das hier gesehen habe. Mir gings da wie dir. Vielleicht wollte lyr da einfach zu ordentlich sein
Ich hätte zu dem Thema auch nochn bisl Senf dazuzugeben...aber hab gerade keine Zeit... In der Vorlesung "Einführung in die KI" hat unser Prof. Dilger nämlich ne nette Idee gehabt wie man die ganzen Suchen mit einadner in beziehung setzen kann. Total simple, aber gut verständlich.
_________________ Blog: kevin-fleischer.de und fbaingermany.com
nene, ich glaub du hast mich da falsch verstanden *gg*
diesen beitrag hab ich eben wegen DEINER änderung geschrieben ... *gg* ich bin der meinung, es sollte "Depth-First Traversal" heißn... eben der name
der technik... so weit ich das interpretieren kann. die technik ist ja, das man die baumknoten durchgeht ... und dabei ist man dann auf der suche.
das abgehen der knotenpunkte ist die technik, die suche ist ... was man macht... ja, blöd formuliert lol
Registriert: So Sep 26, 2004 05:57 Beiträge: 190 Wohnort: Linz
Depth-First Traversal war bei mir wohl eher auch deshalb weil ich es in der Vorlesung vor kurzem so gehört habe. Depth-First Search ist aber genauso richtig würde ich meinen.
"In der Vorlesung "Einführung in die KI" hat unser Prof. Dilger nämlich ne nette Idee gehabt wie man die ganzen Suchen mit einadner in beziehung setzen kann."
Nennt sich dann iterative deepening oder A-Stern, was besseres gibt es da meines Wissens nach nicht.
Registriert: So Sep 26, 2004 05:57 Beiträge: 190 Wohnort: Linz
"Ach...so heilig ist der auch nicht. Um ganz ehrlich zu sein ist der einfach nur eine etwas schlauere greedy-Suche. (GutZuWissen: Greedy heißt gierig)"
Also wenn man mal "heilig" als "das beste was möglich ist" definiert, dann würde ich schon meinen, dass der A-Stern diese Stellung verdient. A-Stern ist aber im Endeffekt eine Greedy-Suche. Meines Wissens nach ist das einzige Unterscheidungsmerkmal, dass A-Stern üblicherweise eine Heuristik verwendet (nicht zwingend der Fall), die Greedy-Suche jedoch die allgemeine Form im Sinne von bester Kandidat ist, wobei für den besten Kandidaten nicht zwingend eine Heuristik nötig ist.
A-Stern wäre somit eine spezielle Form der Greedy-Suche.
Also der direkte Vergleich:
Breitensuche (mit den wenigsten Kosten):
Dort wo k(x) minimal ist erweitern, wobei k(x) die bisherigen Kosten
A-Stern:
Dort wo k(x) + h(x) minimal ist erweitern, wobei k(x) die bisherigen Kosten und h(x) die geschätzten (wenn möglich minimalen) Kosten bis zum Ziel.
Greedy-Suche
Dort wo f(x) minimal ist erweitern, wobei f(x) beliebig sein kann, also beispielsweise k(x) oder auch k(x) + h(x) oder aber auch Hausnummer(x) wobei die Hausnummer wohl meistens eher weniger erfolgversprechend sein dürfte :-).
Mitglieder in diesem Forum: 0 Mitglieder und 7 Gäste
Du darfst keine neuen Themen in diesem Forum erstellen. Du darfst keine Antworten zu Themen in diesem Forum erstellen. Du darfst deine Beiträge in diesem Forum nicht ändern. Du darfst deine Beiträge in diesem Forum nicht löschen. Du darfst keine Dateianhänge in diesem Forum erstellen.