Travelling Salesman Problem - Backtracking mit Listen

[scolia]

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

[Udontknow]

Hallo!

Was genau ist denn dein Problem? Gibt es eine Fehlermeldung? Wenn ja, welche?

Cu,
Udontknow

[scolia]

Hi,

es gibt eine AccessViolation bei showmessage(resList^.plz);.
Dieses Objekt müsste aber eigentlich existieren, da ich ja resList ja vorher auf temp gelegt habe.

Mache ich meine Liste eventuell mit der Funktion countList kaputt? Die sieht so aus:

Delphi-Quellcode:

function countList (VAR pointer:TPlzList) : integer;
  VAR counter:integer;
begin
   counter := 0;
   while pointer <> NIL do begin
     counter := counter + 1;
     pointer := pointer^.next;
   end;
   countList := counter;
end;

Schöne Grüße,

Tim

[bockhop]

Hi Tim,

deine Vermutung ist richtig.
Du zerstörst aber nicht die Liste, sondern den Zeiger auf den ersten Eintrag.

Innerhalb deiner function countList mit einen temporären Zeiger arbeiten.

Liebe Grüße, Tim

[DGL-luke]

bruteforce? optimierung? backtracking? bau dir doch einfach einen A*... ressourcen im netz gibts dazu massig.