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

[Pelzi]

Hi,
Ich habe das Problem, dass ich in einem Graphen nicht einen Knoten finden, sondern möglichst viele Knoten besuchen, ohne einen doppelt zu besuchen, möchte.
Also einen möglichst langen weg ohne einen Knoten doppelt zu besuchen und ohne ein festes Ziel. Ich ahb mer schon Tiefensuche, Breitensuche und A*- Suche angesehen, die scheinen aber nciht gegeinet, da sie immer einen Knoten suchen.


Pelzi

[Der_Unwissende]

Zitat:

Zitat von Pelzi

Hi,
Ich habe das Problem, dass ich in einem Graphen nicht einen Knoten finden, sondern möglichst viele Knoten besuchen, ohne einen doppelt zu besuchen, möchte.
Also einen möglichst langen weg ohne einen Knoten doppelt zu besuchen und ohne ein festes Ziel. Ich ahb mer schon Tiefensuche, Breitensuche und A*- Suche angesehen, die scheinen aber nciht gegeinet, da sie immer einen Knoten suchen.

Aber die Algorithmen kannst Du doch leicht abwandeln! Schau Dir einfach mal die Idee genauer an und Du solltest es fast sehen. Nimm einfach die Tiefensuche, merk Dir alle besuchten Knoten und die besuchte Tiefe um zu einem Knoten zu gelangen. Dann schaust Du dir an, ob Du einen neuen Knoten erreichen kannst (eben noch nicht besucht). Ist dies der Fall, besuchst Du den (und merkst ihn Dir + erhöhst die Tiefe). Irgendwann gelangst Du zu einem Blatt oder einem Knoten, der nur bereits besuchte Nachbarn hat. Hier schaust Du Dir nun die Tiefe dieser Tour an, ist sie höher als die bisher max. hast Du eine bessere Lösung gefunden. Der Rest ist Rekursion.
Ist vielleicht nicht der schönste Weg, gibt bei Graphen eigentlich immer eine ganze Menge Algorithmen (und deren Einsatzgebiet), die sich leicht finden lassen sollten, aber man kann halt schon mit den von Dir genannten Verfahren meist sehr sehr viel erreichen.

Gruß Der Unwissende

[marabu]

Hi Pelzi,

mir kommt da noch folgender Algorithmus in den Sinn: Du bestimmtst die konvexe Hülle der Knotenmenge und verbindest dann die einzelnen Knoten im Uhrzeigersinn, wobei du sie gleichzeitig aus der betrachteten Knotenmenge entfernst. Die Verbindung des letzten Knoten mit dem ersten Knoten unterlässt du dann und bildest für die Restmenge wieder die konvexe Hülle. Den letzten Knoten der ersten Hülle verbindest du mit dem nächstgelegenen der zweiten Hülle und so weiter. Bildlich entsteht soetwas wie eine Schnecke.

Frohe Weihnachten

[Pelzi]

Zitat:

Zitat von Der_Unwissende

Aber die Algorithmen kannst Du doch leicht abwandeln! Schau Dir einfach mal die Idee genauer an und Du solltest es fast sehen. Nimm einfach die Tiefensuche, merk Dir alle besuchten Knoten und die besuchte Tiefe um zu einem Knoten zu gelangen. Dann schaust Du dir an, ob Du einen neuen Knoten erreichen kannst (eben noch nicht besucht). Ist dies der Fall, besuchst Du den (und merkst ihn Dir + erhöhst die Tiefe). Irgendwann gelangst Du zu einem Blatt oder einem Knoten, der nur bereits besuchte Nachbarn hat. Hier schaust Du Dir nun die Tiefe dieser Tour an, ist sie höher als die bisher max. hast Du eine bessere Lösung gefunden. Der Rest ist Rekursion.
Ist vielleicht nicht der schönste Weg, gibt bei Graphen eigentlich immer eine ganze Menge Algorithmen (und deren Einsatzgebiet), die sich leicht finden lassen sollten, aber man kann halt schon mit den von Dir genannten Verfahren meist sehr sehr viel erreichen.

Gruß Der Unwissende

Jup, aber wie stelle ich fest, dass ich alle Pfade besucht habe, bzw. wie schaffe ich es, beim nächsten versuch einen anderen Weg zu benutzen.

[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.

[Mr. Pink]

backtracking

[Pelzi]

Zitat:

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