TSP: Nearest-Neighbour-Method

[fkerber]

Hi!
Nachdem ich jetzt den Text geschrieben habe, ist mir mal aufgefallen, wie lang er geworden ist. Deswegen also schonmal vorab danke fürs Lesen.

Momentan bin ich dabei, mehrere Lösungswege zu implementieren, um das Travelling-Salesman-Problem (Problem des Handlungsreisenden) zu lösen. Als einen einfachen Lösungsansatz gibt es da die Nearest-Neighbour-Method (Nächster-Nachbar-Methode). Ausgehend von der Startstadt wird immer die nächste noch nicht besuchte Stadt angefahren.

Leider habe ich keine Implementierungen gefunden und habe es dann jetzt selbst gemacht (eigentlich ja auch Sinn der Übung ;) )
Funktionieren tut das Ganze eigentlich recht gut, aber ich frage mich jetzt, wie gut der Algorithmus ist. Deswegen versuche ich mal, ihn hier zu erläutern und vielleicht kann ja jemand Verbesserungsvorschläge unterbreiten.

Delphi-Quellcode:

  cities: array of TPoint;
  distances: array of array of extended;

In cities werden die X/Y-Koordinaten der Städte gespeichert (Das ganze ist dynamisch, da der User per Klick auf ein Image die Städte einfügen kann). distances enthält jeweils die Entfernung zu den anderen Städten. Es ist also folglich ein zweidimensionales Array mit folgendem Aufbau:

distances[0][0]=Abstand der Stadt 0 zu sich selbst (=0)
distances[0][1]=Abstand der Stadt 0 zur Stadt 1
distances[1][1]=Abstand der Stadt 1 zu sich selbst (=0)
distances[i][j]=Abstand der Stadt i zur Stadt j

Dabei wird distances so gefüllt:

Delphi-Quellcode:

var i,j: integer;
begin
for i:=0 to length(cities)-1 do
 begin
  setlength(distances[i],0);
  for j:=0 to length(cities)-1 do
   begin
     setlength(distances[i], length(distances[i])+1);
     distances[i][j]:=sqrt(sqr(cities[i].X-cities[j].X) + sqr(cities[i].y-cities[j].y));
   end;
 end;
end;

Kernstück der ganzen Sache ist ja jetzt das Finden der jeweils nächsten Stadt. Also übergebe ich meiner Funktion distances[i], wobei i die Nummer der Stadt ist, in der ich mich befinde und von der aus, ich die nächstgelegene Stadt suche.
Die Funktion sieht folgendermaßen aus:

Delphi-Quellcode:

function Find_Min(Arr: array of extended): Integer; //liefert Index auf nächste Stadt
var
  i, m: Integer;
begin
  m:=0;
  while ((arr[m]=0) and (m < high(arr))) do inc(m);
  for i:=1 to High(Arr) do
    if ((Arr[i]< Arr[m]) and (arr[i]>0)) then m:=i;
  if arr[m]=0 then m:=0;
  Result:=m;
end;

Wie ihr seht, werden die Städte, mit Entfernung 0 übergangen (while-Schleife). Das soll so sein, da ich einfach die Entfernung zu bereits besuchten Städten auf 0 setze. Sollte die Entfernung zu allen Städten 0 betragen, dann wird als nächste Stadt die Anfangsstadt zurückgegeben.
Nachdem also die jeweils nächste Stadt gefunden wurde, werden die Entfernungen aller Städte zur gefundenen auf 0 gesetzt:

Delphi-Quellcode:

 for j:=0 to length(distances)-1 do
  distances[j][mindistcity]:=0; //mindistcity = Index auf nächste Stadt

Ihr seht, es sind also ein paar Schleifen drin und deswegen habe ich das Gefühl, das das Ganze, sagen wir mal "suboptimal" ist ;)
Vielleicht habt ihr Verbesserungsvorschläge...

Ciao und Danke
Frederic

[dahead]

mhh, was mir auffällt ist, dass du Setlength innerhalb von zwei Schleifen ausführst. Um das zu verhindern, solltest du Setlength anfangs _vor_ jeder Schleife ausführen.

was den restlichen code angeht: keine ahnung wie ich das angehen würde, kann dir daher diesbezüglich keine (optimierungs-)tipps geben.

wie ist denn die geschwindigkeit?

[fkerber]

Hi!

Stimmt, das ist schonmal ein Argument.
Ich weiß ja, wie weit die Schleife geht, danke.


Ciao Frederic

[marabu]

Hallo Frederic,

von der Distanzmatrix musst du nur das obere Dreieck speichern:

Delphi-Quellcode:

function GetDistances(ap: TPointDynArray): TDistDynArray;
var
  iRow, iCol: integer;
begin
  SetLength(Result, Pred(Length(ap)));
  for iRow := Low(ap) to Pred(High(ap)) do
  begin
    SetLength(Result[iRow], Pred(High(ap) - iRow));
    for iCol := Low(Result[iRow]) to High(Result[iRow]) do
      Result[iRow, iCol] := Distance(ap[iRow], ap[Succ(iRow + iCol)]);
  end;
end;

Reduziert die Einträge von n**2 auf (n/2)(n-2).

Grüße vom marabu

[alzaimar]

Hier eine Lösung, die genetische Programmierung verwendet. Echt geil!
http://www.torry.net/quicksearchd.ph...ling&Title=Yes

[generic]

in der ct war in diesem jahr ein anderer netter algo. dieser hatte sich etwas von ameisen abgeschaut.
dieser algo war auch sehr effektiv.

[fkerber]

Hi!

@marabu:
Danke. Klingt logisch, den Code schau ich mir morgen an. Vielen Dank.

@alzamair:
Danke, werd ich mir auch mal anschauen

@generic:
Genau den zu implementieren ist das eigentliche Ziel der Arbeit. Es soll dabei dann aufgezeigt werden, dass er effektiver ist, als der Nearest-Neighbour. Deswegen zunächst diese Implementierung.


Ciao Frederic