#1 26.09.2007 10:09:04

Dreamworld
UltraMember
Ort: Karlsruhe
Registriert: 06.12.2005
Beiträge: 368

Breiten/Tiefensuche

Hi, also ich hab ne Frage erstmal zur Breitensuche, bin über das Thema gestolpert und mir is da was nicht klar.
Ich mach das doch ungefähr so:
1. Wähle das Startelement
2. Markiere es als besucht, also entferne es von der Warteliste
3. Schiebe alle direkten Nachfolger von dem Startelement auf die Warteliste
4. Pope das nächste Element aus der Warteschlange, geh zu 2 bis das gepoppte=gesuchtes Element oder Liste leer.

Stimmt das soweit?
Wenn ja dann is mir nicht klar wie ich daraus jetzt meinen kürzesten Pfad finden soll? ALso ich hab das paar mal per Hand ausprobiert und ich finde zwar das Element, aber wo sehe ich da dann den kürzesten Pfad? Das is mir nicht klar.

MfG Dreamworld.

Beitrag geändert von Dreamworld (26.09.2007 10:09:23)

Offline

 

#2 26.09.2007 16:34:34

Lotipats
UltraMember
Registriert: 17.05.2005
Beiträge: 395

Re: Breiten/Tiefensuche

Wenn ich dich richtig verstanden habe, dann hast du es korrekt beschrieben.
Du beginnst oben in deinem Baum, das ist das erste Element in der Liste. Wenn es nicht das gesuchte ist, so fügst du die Nachfolger in der Liste AM ENDE hinzu. Danach löschst du das erste Element. Anschließend beginnst du den Vorgang wieder beim ersten Element. Ist es das gesuchte? Nein, so kommen dessen Nachfolger wieder ans Ende und du löschst wieder den ersten Eintrag. (Neuen) Ersten Eintrag ansehen ...

Durch dieses Vorgehen ist sichergestellt, dass du den Baum Ebene für Ebene durchgehst. Das erste Element, welches du findest, ist auch das mit dem kürzesten Weg von Root, da alle anderen nur in tieferen Ebenen liegen können. Es kann natürlich noch sein, dass ein Knoten auf der gleichen Ebene ebenfalls die Suchkriterien erfüllt. Jedoch hat dieser den gleichen Weg.

LOTIPATS

Offline

 

#3 26.09.2007 17:50:51

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Breiten/Tiefensuche

Zitat:

wo sehe ich da dann den kürzesten Pfad?

Jedes Element hat genau einen Vorgänger, wenn du an jedem Knoten auch den Vorgänger speicherst, kannst du dich leicht bis nach oben durch hangeln. Dann hast du deinen Pfad.

Was willst du eigentlich genau machen?


My software never has bugs. It just develops random features.

Offline

 

#4 26.09.2007 19:50:44

Dreamworld
UltraMember
Ort: Karlsruhe
Registriert: 06.12.2005
Beiträge: 368

Re: Breiten/Tiefensuche

Nichts spezielles, hat mich nur interessiert, danke für die Antworten.

Offline

 

#5 27.09.2007 10:18:43

Dreamworld
UltraMember
Ort: Karlsruhe
Registriert: 06.12.2005
Beiträge: 368

Re: Breiten/Tiefensuche

Verwirrt hat mich nur ein wenig, dass auf manchen Seiten stand, dass man dann den kürzesten Pfad sofort erhält. Ich dachte das sieht man dann anhand der Warteschlange. Weil man ja immer die direkten Nachfolger untersucht, muss der Pfad ja minimal sein, jedenfalls wenn man den ersten "Treffer" nemmt.
Falls ein Knoten nicht wie beim binären Baum mehrere Vorgänger hat, muss man (Coolcat) den Vorgänger jedes besuchten Knotens abspeichern, damit man dann  sich zurückhangeln kann.
Stimmt das so?

Offline

 

#6 27.09.2007 15:14:53

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Breiten/Tiefensuche

Zitat:

Falls ein Knoten nicht wie beim binären Baum mehrere Vorgänger hat,

In jedem Baum hat jeder Knoten genau einen Vorgänger, mit Ausnahme des Wurzelknotens. Ein Knoten kann aber einen oder mehrere Nachfolger haben. Bei einem Binärbaum maximal zwei.

Zitat:

dass man dann den kürzesten Pfad sofort erhält.

Ich vermute stark, das da stand, dass man den Knoten mit dem kürzesten Pfad zur Wurzel erhält, nicht den Pfad.

Zitat:

muss man (Coolcat) den Vorgänger jedes besuchten Knotens abspeichern, damit man dann  sich zurückhangeln kann.

Wenn du wirklich am Pfad interessiert bist, also der Liste der Knoten die auf dem Pfad liegen, musst du wie ich oben schon sagte neben den Nachfolgern eines Knotens auch den Vorgänger speichern.

Code:

Knoten = record
    parent: ^Knoten;
    left, right: ^Knoten;
    data: ^Daten;
end;

My software never has bugs. It just develops random features.

Offline

 

#7 27.09.2007 16:49:27

Lotipats
UltraMember
Registriert: 17.05.2005
Beiträge: 395

Re: Breiten/Tiefensuche

Da hab ich gleich mal eine Frage, wie ist das beim http://de.wikipedia.org/wiki/Gewurzelter_Baum. Ich habe auch gedacht, dass Knoten in Bäumen nur einen Vorgänger haben. Habe auch fleißig eine Antwort getippt, wollte das mit Wikipedia untermalen und dann bin ich auf das Bild bei Wikipedia (siehe http://de.wikipedia.org/wiki/Gewurzelter_Baum oben) gestoßen, was mich doch etwas stutzig gemacht hat. Da ist 2 ja direkt oder indirekt von den anderen erreichbar. Nun hätte ich 2 als Root gewählt, um daraus einen Baum nach meinem Verständnis zu machen. Aber dann müssten die Pfeile doch andersrum sein, oder etwa nicht?

Und dann kam ein Techniker von Dell, weshalb ich meine Antwort nicht beenden konnte ;P
Deshalb jetzt.

LOTIPATS

Offline

 

#8 27.09.2007 17:14:53

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Breiten/Tiefensuche

Lese einfach mal deinen Artikel genauer...

Zitat:

Es lassen sich Out-Trees, bei denen die Kanten von der Wurzel ausgehen, und In-Trees, bei denen die Kanten in Richtung Wurzel zeigen, unterscheiden.

Ist einfach nur eine Definitionssache. Im Fall von In-Trees nennt man die Wurzel auch manchmal Senke.


My software never has bugs. It just develops random features.

Offline

 

#9 27.09.2007 17:39:39

Dreamworld
UltraMember
Ort: Karlsruhe
Registriert: 06.12.2005
Beiträge: 368

Re: Breiten/Tiefensuche

ja stimmt, in einem Baum hat jeder Knoten nur einen Vorgänger, aber Breitensuche bezieht sich doch auf beliebige Graphen oder?
Aber is ok, habs verstanden, danke smile

Beitrag geändert von Dreamworld (27.09.2007 17:40:22)

Offline

 

#10 28.09.2007 10:04:35

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Breiten/Tiefensuche

Zitat:

aber Breitensuche bezieht sich doch auf beliebige Graphen oder?

Du kannst Breiten- und auch Tiefensuche in einem beliebigen Graphen machen.


My software never has bugs. It just develops random features.

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson