Hallo,
ich programmiere ein Tool, das den kürzesten Weg finden soll, um n Postleitzahlen abzuklappern. Ich habe hier keinerlei Optimierung eingebaut sondern versuche einfach durch Durchgehen aller Möglichkeiten den kürzesten Weg zu finden.
Das Programm an sich steht - ich kann die Entfernung zweier PLZ berechnen (mithilfe von OpenGeoDB). Blöderweise will der Backtracking-Algorithmus nicht so ganz.
Kann sich das mal jemand anschauen?
Ich habe das komplette Projekt angehängt und hier die Backtracking-Prozedur:
Delphi-Quellcode:
procedure search(resList:TPlzList;distance:extended);
VAR curLength : integer;
srcList,temp : TPlzList;
newDistance : extended;
begin
srcList := PlzList;
while (srcList <> NIL) do begin
new(temp);
temp^.plz := srcList^.plz;
temp^.coord := srcList^.coord;
temp^.next := NIL;
if resList = NIL then begin
resList := temp;
end
else
resList^.next := temp;
newDistance := distance + getDistance(temp^.coord,resList^.coord);
if countList(resList) < countList(PlzList) then begin
showmessage(resList^.plz);
search(resList^.next,newDistance);
end
else if ((MinDist = 0) OR (newDistance < MinDist)) then begin
MinList := resList;
MinDist := newDistance;
end;
srcList := srcList^.next;
end;
end;
PlzList enthält alle PLZ, zu denen ich muss. getDistance() gibt mir die Entfernung zweier Koordinaten. In MinList will ich am Ende die kürzeste Reihenfolge der PLZ haben, in MinDist die dazugehörige Länge.
Wäre toll wenn mir jemand helfen kann.
Schöne Grüße,
Tim