Stack-Overflow abfangen

[SirThornberry]

Bedenkt aber, daß man auch etwas mehr Speicher benötigt, wenn man sich den Weg merkt, da dieses für jede Rekusrionsebene einzeln gepeichert (kopiert und erweitert) werden muß. Da hast du einen Denkfehler.
Man muss sich maximal so viel Felder merken wie es insgesamt gibt (nicht alle Kombinationen). Zudem kann man auch noch mit Bits arbeiten (Pro Feld ein Bit) und schon benötigt man gar nicht mehr sooo viel Speicher.

[FredlFesl]

Echt? Ich würde der Matrix ein weiteres Feld gönnen (Visited:Boolean).
Betrete ich das Feld, prüfe ich, ob Visited=True, wenn ja, beende ich die Routine, ich war ja schon mal da.
Ansonsten setze ich Visited=True, suche nach weiteren Wegen und nehme aber nur die Nachbarfelder mit ins Boot, die ich noch nicht besucht habe.

Dann rufe ich mich selbst mit allen Nachbarkandidaten rekursiv auf.

Bevor ich die Routine verlasse, setze ich Visited wieder auf False:

Delphi-Quellcode:

Procedure TMatrix.Visit (Source : TPoint; Path : TPath);
Begin
  If Source = FinalDestination then
     Success(Path)
  Else If not Self.Visited[Source] Then begin
    Self.Visited[Source] := True;
    Foreach Neighbor in Source.Neighbors do 
      If not Self.Visited[Neighbor] Then
        Visit(Neighbor, Path+Neighbor)
    Self.Visited[Source] := False;
  End
End;

[himitsu]

OK, einen Denkfehler hab ich schon, wenn man die betretenen Felder wieder frei gibt, sobald mein wieder eine Ebene zurück geht, dann stimmt es.

[FredlFesl]

Oder einfach gleich A* nehmen, schließlich will er ja einen Weg von A->B finden.

[Luckie]

Das ist mir auch schon die ganze zeit im Kopf rumgeschwirrt. Hie rgibt es ein Demo und ein Tutorial: http://www.michael-puff.de/Programmierung/Delphi/Demos/

[Delphi-Laie]

Zitat von Sinthuor:

Problematisch wird es sobald ein Weg vor dem Ziel einen "Kreis bildet":
...
Hier kommt es zu einer Endlosschleife und dadurch zu einem Stackoverflow - den ich abfangen und stattdessen eine Fehlermeldung ausgeben möchte.

Das Problem ist hier nicht, irgendwelche Exceptions abzufangen (die auf ein grundlegende(ere)s Problem hindeuten), sondern der Fehler im Suchalgorithmus: Die Endlosschleifen entstehen m.E., weil es beim Suchen des Wegen gestattet ist, teilweise rückwärts zu gehen.

Ein korrekter Algorithmus wird bei diesen kleinen Feldern nie zu einem Stacküberlauf führen.