Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Stack Overflow


ene - Di 20.03.07 09:00
Titel: Stack Overflow
moin ich bekomme einen Stack Overflow bei folgendem Codeaufbau:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
Function IsValid(Const x,y,z: Integer): Integer;
Begin
  If (x >= Low(Mitte)) And (x <= High(Mitte)) And (y >= Low(Mitte[x])) And (y <= High(Mitte[x])) Then Result:= Mitte[x,y,z] Else Result:= 0;
End;


Function GetLongestLine(x,y,Tiefe: Integer): Boolean;
Var Zwischen: Boolean;
Begin
  Result:= False; Zwischen:= False;

    try
    Mitte[x,y,1]:= 0;
    If IsValid(x-1,y-1,0) = 1 Then Zwischen:= GetLongestLine(x-1,y-1,Tiefe+1);
    If IsValid(x  ,y-1,0) = 1 Then Zwischen:= GetLongestLine(x  ,y-1,Tiefe+1Or Zwischen;
    If IsValid(x+1,y-1,0) = 1 Then Zwischen:= GetLongestLine(x+1,y-1,Tiefe+1Or Zwischen;
    If IsValid(x-1,y  ,0) = 1 Then Zwischen:= GetLongestLine(x-1,y  ,Tiefe+1Or Zwischen;
//    If IsValid(x+1,y  ,0) = 1 Then Zwischen:= GetLongestLine(x+1,y  ,Tiefe+1) Or Zwischen;
//    If IsValid(x-1,y+1,0) = 1 Then Zwischen:= GetLongestLine(x-1,y+1,Tiefe+1) Or Zwischen;
//    If IsValid(x  ,y+1,0) = 1 Then Zwischen:= GetLongestLine(x  ,y+1,Tiefe+1) Or Zwischen;
//    If IsValid(x+1,y+1,0) = 1 Then Zwischen:= GetLongestLine(x+1,y+1,Tiefe+1) Or Zwischen;
    except
    on E: Exception do Writeln(E.Message, E.HelpContext);
    end;


    If Tiefe > Laenge Then Begin
      Laenge:= Tiefe;
      Zwischen:= True;
    End;

    If Zwischen Then Begin
      Mitte[x,y,1]:= 2;  
      Result:= True;
    End;
  End;


Das ist ein A* Algorithmus, Mitte ist ein Array Of Array Of Array [0..2] Of Byte. Sprich eine zweidimensionale Matrix, die zu jedem Punkt 2 Werte enthalten kann. So wie sie jetzt da steht, läufts, aber wenn ich restlichen Kommentare rausnehme um mehr Felder abzuprüfen, bekomme ich beim IsValid() einen StackOverflow und ich verstehs nicht :( Ich kann die Funktion auch leider nicht rausnehmen, weil mein Abfragen größer als das Array sein können. Bei einem Punkt am Rand werden alle 8 umschliessenden Werte überprüft.

Hat jemand das verstanden? Ansonsten bitte einfach nachfragen und vielen Dank im Vorraus.


Moderiert von user profile iconUGrohne: Topic aus Delphi Language (Object-Pascal) / CLX verschoben am Di 20.03.2007 um 10:12


ene - Di 20.03.07 10:18

Ok, IsValid rufe ich jetzt als StdCall auf und dann habe ich den StackOverflow in der rekursiven Funktion...aber keinen Plan warum :(


wdbee - Di 20.03.07 10:35

Wenn rekursive Aufrufe von Funktionen zu einem Stack Overflow führen, gibt es zwei mögliche Gründe:

1. Der Alg. ist zwar richtig, aber es werden zu viele bzw. zu große lokale Variablen (z.B. Arrays [0..Sehr Groß]) verwendet.
2. Der Alg. ist falsch, weil er nie terminiert.

Um 2. zu prüfen, kannst du mal eine globale Variable mit 0 initialisieren und bei jedem Aufruf der Funktion inkrementieren. Wenn der Stackoverflow auftritt, kannst du den Wert der Variablen mit der Exception anzeigen lassen. Dann siehst du, wie oft die Rekursion auftritt.


ene - Di 20.03.07 11:10

Also ich habe mal einen Zähler eingebaut und der StackOverflow tritt ja nach Bedingungen im Algo nach unterschiedlichen Durchläufen auf. Also würde ich mal sagen, dass er falsch terminiert ist, oder?

Die Frage die sich mir dabei noch stellt ist, warum er "teilweise" funktioniert, wenn ich nur nach oben oder unten suche :confused: Das Ergebnis ist dann zwar falsch, aber es wird ein Ergebnis geliefert.


ene - Di 20.03.07 11:29

Ich habs, ich hab den falschen Wert in die geschlossene Liste gesetzt, dann klappt auch. Vielen Dank!