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