Wie Suche ich in einem möglichst langen weg in einem Graphen

[Pelzi]

Zitat von Daniel:

Hast Du denn ein paar weitere Informationen über den Graphen? Wild alles durchprobieren wird Dich eine Menge an Rechenzeit kosten.

Denken wir doch mal an ein rechteckiges Labyrinth. Start links oben, Ende rechts unten. Wenn Du diese Punkte hast, kannst Du ja wieder suchen lassen. Und die Suche wird wichtig sein, damit der Algorithmus seinen Weg bewerten kann: In Deinem Fall je weiter vom Ziel weg, desto besser. Die Information, wie weit es zum Ziel ist, sollte vorhanden sein. Ich hatte da mal was geschrieben, das ließe sich wie schon angeregt abwandeln: http://www.delphipraxis.net/internal...ct.php?t=85844.

Also nagut, dann etwas ausführlicher, es geht um ein zweidimensionales Spielfeld. In dem Man waagerecht, senkrecht, und slinks-unten rechs oben diagonal springen kann. Dafür ahbe ich mir einen graphen gebaut:

Delphi-Quellcode:

procedure makegraph(var FGraph: TGraph);
var i,j,k,l: Integer;
begin
for i:=0 to 7 do
  for j:=0 to 10 do
    for k:=0 to 7 do
      for l:=0 to 10 do
      begin
        if (j=l) and  (i=k) then FGraph[i,j,k,l]:=false
        else if j=l then FGraph[i,j,k,l]:=true
        else if i=k then FGraph[i,j,k,l]:=true
        else if (i+j)=(k+l) then FGraph[i,j,k,l]:=true
        else FGraph[i,j,k,l]:=false;
        if feldungueltig(i,j) or feldungueltig(k,l) then FGraph[i,j,k,l]:=false;
      end;
end;

So wenn nun ein feld besucht wurde, wird nicht nur dieses Feld gelöscht sondern alle Wege, die dieses Feld überqueren würden.
Das habe ich so realiesiert:

Delphi-Quellcode:

procedure loeschefeld(x,y: Integer);
var i,j,k,l: integer;
begin
  for i:=0 to 7 do
    for j:=0 to 10 do
    begin
      FGraph[y,x,i,j]:=false;

      if (i=y) or (j=x) or (i+j=x+y) then
        for k:=0 to 7 do
          for l:=0 to 10 do
          begin
            if ( (i=y) and (i=k) ) and ( ( (j<x) and (x<l) ) or ( (l<x) and (x<j) ) ) then FGraph[i,j,k,l]:=false
            else if ( (j=x) and (j=l) ) and ( ( (i<y) and (y<k) ) or ( (k<y) and (y<i) ) ) then FGraph[i,j,k,l]:=false
            else if ( ( (j+i) = (y+x)) and ( (j+i) = (k+l)) ) and ( ( (i<y) and (y<k) ) or ( (k<y) and (y<i) ) ) then FGraph[i,j,k,l]:=false
          end;
    end;
end;

So wenn ich nun via Backtracking vorgehe, habe ich das Problem, dass ich die Gelöschten Kanten nach einem Schritt nicht mehr wiederherrstellen kann, da ich nciiht weiß ob die Kanten die ich entfernt habe, vorher vorhanden waren oder nciht. Ich müsste also nach jedem Schritt den ganzen Graphen kopieren. Und deswegen ist Backtraking nicht der geeigneteste Algorithmus.

pelzi