Laden...

Wie implementiert man am Besten eine Rekursion in einer Breitensuche?

Erstellt von TinyToon vor 4 Jahren Letzter Beitrag vor 4 Jahren 2.488 Views
T
TinyToon Themenstarter:in
7 Beiträge seit 2019
vor 4 Jahren
Wie implementiert man am Besten eine Rekursion in einer Breitensuche?

Wie implementiert man am Besten eine Rekursion in einer Breitensuche.

Der Sinn ist nach jedem gefundem Knoten in der Breitensuche, die Breitensuche erneut von diesem Knoten zu starten. Leider hat die Queue immer 2 Einträge nach der ersten Suche...

4.931 Beiträge seit 2008
vor 4 Jahren

Hallo,

sprichst du von einem Binärbaum (wegen der 2)?
Schonmal in Breitensuche geschaut?
Das "4. Wiederhole Schritt 2." unter "Algorithmus (informell)" kannst du als Rekursion auffassen (wenn auch nicht nötig). Warum möchtest du es denn rekursiv ausführen?

U
69 Beiträge seit 2019
vor 4 Jahren

Hi,

grundsätzlich wären etwas mehr Informationen schön.
Bspw.:

  • Wie sieht dein Algorithmus derzeit aus?
  • Wie sieht deine Test-Datenstruktur aus?
  • ....

Wozu brauchst du eine Queue? Das sieht mir ehr wie ein Überbleibsel einer iterativen Lösung aus.
Für die Rekursion würde ich der rekursiven Funktion das Suchziel (string/int/was auch immer) und eine Liste der Knoten (Input-Knoten) die zu untersuchen sind übergeben.
Enthält die Liste bereits deinen Zielknoten gebe diesen zurück.
Enthält die Liste den Zielknoten nicht, rufe die rekursive Funktion erneut auf, dieses mal mit allen Child-Knoten aller Input-Knoten.
usw.........
Sind die Input-Knoten leer wurde das Ziel nicht gefunden und du musst die Rekursion abbrechen.

“Knowledge cannot replace friendship. I'd rather be an idiot than lose you.”

  • Patrick to Spongebob
U
69 Beiträge seit 2019
vor 4 Jahren

Das "4. Wiederhole Schritt 2." unter "Algorithmus (informell)"

Ich sehe gerade, dass unter "Algorithmus (formal)" der erste Algorithmus die rekursive Variante ist...

“Knowledge cannot replace friendship. I'd rather be an idiot than lose you.”

  • Patrick to Spongebob
T
TinyToon Themenstarter:in
7 Beiträge seit 2019
vor 4 Jahren

Es geht darum ein pacman Spiel zu programmieren. Mit der einfachen Breitensuche läuft er aber logischerweise immer nur einen Pfad ab, würde man nun am nächsten Punkt(Knoten) erneut die Suche starten(Rekursion?) dann sollte er irgendwann alle Punkte erreicht haben.

T
461 Beiträge seit 2013
vor 4 Jahren

Wozu brauchst du dann eine Breitensuche?

Meine Idee wäre, das Spielfeld in einen (unsichtbaren) Raster darzustellen, jede Figur bewegt sich pixel für pixel in den nächsten Raster...

In dem Fall (aber auch sonst) kann dir die Breite egal sein, da du so oder so eine fixe Spielfeldgröße benötigst, somit hast du schon mal das Maß und nach dem kann man alles andere richten...

Alles so rein aus dem Kopf heraus 😉

Ich habe den Titel mal angepasst, so dass Suchende auch etwas damit anfangen können. EDIT: Ich sollte beim Wort "Shift" im Titel das "f" nicht vergessen... 😄

T
TinyToon Themenstarter:in
7 Beiträge seit 2019
vor 4 Jahren

Die Breitensuche benötige ich um hinterher ein backtracking laufen zu lassen, der pacman soll alle Leckerchen alleine finden...

A
764 Beiträge seit 2007
vor 4 Jahren

Es geht darum ein pacman Spiel zu programmieren. Mit der einfachen Breitensuche läuft er aber logischerweise immer nur einen Pfad ab, würde man nun am nächsten Punkt(Knoten) erneut die Suche starten(Rekursion?) dann sollte er irgendwann alle Punkte erreicht haben.

Hallo TinyToon

Kann es sein, dass du die Breitensuche mit der Tiefensuche verwechselst?
".. läuft er aber logischerweise immer nur einen Pfad ab .." ist doch nur bei der Tiefensuche möglich (korrigiert mich bitte wenn ich falsch liege).

Bei der Breitensuche durchsucht er alle Pfade ebenenweise gleichzeitig. In etwa so wie Urza das beschrieben hat.

Gruß
Alf

T
TinyToon Themenstarter:in
7 Beiträge seit 2019
vor 4 Jahren

richtig, er geht nach den Ebenen... er muss sich also für eine der 4 Richtungen entscheiden und zwar jene die zuerst in die Queue eingetragen wird usw.die anderen besucht er aber nicht, würde er allerdings jedesmal neu suchen, dann müsste er theoretisch alle finden

A
764 Beiträge seit 2007
vor 4 Jahren

richtig, er geht nach den Ebenen... er muss sich also für eine der 4 Richtungen entscheiden und zwar jene die zuerst in die Queue eingetragen wird usw.die anderen besucht er aber nicht, würde er allerdings jedesmal neu suchen, dann müsste er theoretisch alle finden

Wenn ich das richtig verstanden habe, entscheidet er sich bei der Breitensuche eben nicht für eine der 4 Richtungen, sondern geht alle Richtungen, bis das Ziel erreicht ist.

T
TinyToon Themenstarter:in
7 Beiträge seit 2019
vor 4 Jahren

das stimmt, die Breitensuche tut das, aber der Pacman kann nur in eine Richtung laufen

A
764 Beiträge seit 2007
vor 4 Jahren

das stimmt, die Breitensuche tut das, aber der Pacman kann nur in eine Richtung laufen

Also willst du eigentlich keine Breitensuche machen, sondern du willst das dein Packman durch den Dungeon läuft, aber nicht immer den gleichen Weg nimmt?

T
TinyToon Themenstarter:in
7 Beiträge seit 2019
vor 4 Jahren

ich will, dass der pacman durch sein Feld läuft und alle Leckerchen frißt, natürlich gibts auch Hindernisse in dem Feld also er muss ausrum laufen...das ganze aber automatisch...am besten mit der Breitensuche, ich muss ihm ja irgendwie zeigen wo es lang geht

A
764 Beiträge seit 2007
vor 4 Jahren

Wenn ich das richtig verstanden habe, dann willst du, dass Packman jeweils ein Feld läuft, dann ausrechnet, welche möglichen Lösungswege es gibt, davon einen auswählt und dann wiederum die neuen Lösungswege ausrechnet? Und sollen dabei die Geister berücksichtigt werden?

[Edit: typo]

T
TinyToon Themenstarter:in
7 Beiträge seit 2019
vor 4 Jahren

genau...ohne Geister...er soll nur alle Leckerchen fressen