scolia - Di 13.06.06 11:21
Titel: Travelling Salesman Problem - Backtracking mit Listen
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-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
| 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
BenBE - Di 13.06.06 20:06
Ich hab zwar nicht direkt dein Projekt angeschaut, aber versuch's mal so:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
| type
TPLZ = Record
PLZ: String;
Coord : TCoords;
end;
TPLZList = array of TPLZ;
TPLZListArray = Array of TPLZList;
Function search(resList:TPlzList; out: Distance: Extended;): TPLZListArray;
var
CurrLevel: Integer;
CurrArray: TPLZList;
procedure DoSearchList(List: TPLZList; Dist: Extended);
var
X, Y: Integer;
Tmp: TPLZList;
begin
Inc(CurrLevel);
Try
If Length(List) = 0 Then
Begin
if NearbyEquals(Dist, Distance) Then
begin
SetLength(Result, Length(Result) + 1);
Result[High(Result)] := CurrArray;
end
else If Dist < Distance Then
Begin
SetLength(Result, 1);
Result[0] := CurrArray;
Distance := Dist;
end;
exit;
end;
If Dist > Distance Then
Exit;
SetLength(Tmp, High(List));
For X := 0 To High(List) do
Begin
For Y := 0 To High(List) Do
If X <> Y Then
Tmp[Y - Ord(Y > X)] := List[Y];
CurrArray[CurrLevel] := List[X];
If CurrLevel = 0 Then
DistAdd := 0
else
DistAdd := GetDistance(CurrArray[CurrLevel-1], CurrArray[CurrLevel]);
DoSearchList(Tmp, Dist + DistAdd);
end;
finally
Dec(CurrLevel);
end;
end;
begin
SetLength(Result, 0);
Distance := Infinity; CurrLevel := -1;
SetLength(CurrArray, Length(ResList));
DoSearchPath(ResList, 0);
end; |
Ungetestet ... Habsch grad mal so aus'm Kopf geschrieben, müsste aber rein theoretisch so funzen. Ach ja:
GetDistance(CurrArray[CurrLevel-1], CurrArray[CurrLevel]); ermittelt den Abstand der beiden als Parameter angegebenen Postleitzahleneinträge.
HTH.