| Autor |
Beitrag |
Christian S.
  
Beiträge: 20451
Erhaltene Danke: 2264
Win 10
C# (VS 2019)
|
Verfasst: Di 25.12.07 02:11
Ave!
Im folgenden möchte ich die Lösung für das TWP (= Travelling Weihnachtsmann Problem) vorstellen, welches eine unserer Paranüsse war. Die hier vorgestellte Lösung stellt sicherlich nicht die performanteste Lösung dar, vielmehr wurde Wert auf eine anschauliche Lösung gelegt.
Das Prinzip
Die Aufgabe war es, die minimale Geschwindigkeit zu finden, die der Weihnachtsmann fliegen musste, um innerhalb von insgesamt 40 Minuten in jeder Stadt drei Minuten zu verbringen. Mit anderen Worte, es musste die kürzeste Route gefunden werden, die alle Städte miteinander verbindet. Das ist also fast das Travelling Salesman Problem, nur dass man bei dem auch wieder am Ausgangspunkt ankommt und bei uns nicht.
Zur Lösung stellen wir erst einmal eine Entfernungsmatrix auf, in der die Entfernung von jeder Stadt zu jeder anderen Stadt gespeichert wird. Es würde natürlich eine Dreiecksmatrix reichen, aber es ist anschaulicher und macht von der Performance her eigentlich nichts, wenn wir die Matrix komplett füllen. Die Matrix sieht dann z.B. so aus:
  Quelltext
1:
2:
3:
4:
| Düsseldorf Köln München
Düsseldorf 0 40 490
Köln 40 0 455
München 490 455 0 |
Die kürzeste Route möchte ich in diesem Beispiel ähnlich wie bei Backtracking berechnen. Ich benutze eine Liste von Städten, die in meiner Route sind, und erweitere diese so lange um eine noch nicht benutzte Stadt, wie die Route kürzer als die beste Route ist. Ist die Route länger als die kürzeste Route, entferne ich die letzte Stadt aus der Route und versuche es mit einer anderen. Ist die Route vollständig und kürzer als die bisher kürzeste Route, habe ich eine neue kürzeste Route. Anders als beim "klassischen" Backtracking muss ich aber zu einer vorhandenen Route immer alle noch verbleibenden Städte hinzufügen.
Entfernungsberechnung
Besonders wichtig für dieses Problem war es, die Entfernung exakt zu berechnen. Die Positionen waren absichtlich sehr exakt angegeben, ebenso wurde der Erdradius aus diesem Grund vorgegeben. Da es nur ein Radius war, sollte von einer Kugel ausgegangen werden.
Die kürzeste Verbindung zwischen zwei Punkten auf einer Kugeloberfläche ist eine Orthodrome. Mit Hilfe der Formel für die Strecke zwischen zwei Punkten, von denen man Längen- und Breitengrad kennt, konnte man also die Entfernungsmatrix mit exakten Werten befüllen. Man musste nur beachten, dass eine Bogenminute 1/60 Grad sind und eine Bogensekunde 1/3600 Grad.
Implementation
An dieser Stelle möchte ich nur zeigen, wie die Methode für das Backtracking aussieht. Der Rest (im Anhang) ist kommentiert und sollte selbst erklärend sein.
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:
| method MainForm.GetSubRoutes(usedCities : Stack<City>; allCities : List<City>);
begin
var thisDistance := CalculateDistance(usedCities); if usedCities.Count = allCities.Count then begin
if thisDistance < fBestRoute.Distance then begin
var citiesStr := new StringBuilder;
for c in usedCities do
citiesStr.Append(c.ToString+' - ');
fBestRoute.Cities := citiesStr.ToString;
fBestRoute.Distance := thisDistance;
end;
exit; end;
var lastCity := iif(usedCities.Count > 0, Integer(usedCities.Peek), -1); var remainingCites := from c in allCities where (not usedCities.Contains(c));
for c in remainingCites do begin
if (lastCity > -1) and (thisDistance + fDistances[lastCity, Integer(c)] > fBestRoute.Distance) then
continue;
usedCities.Push(c); GetSubRoutes(usedCities, allCities); usedCities.Pop; end;
end; |
Ich habe mich entschlossen, die Route in einem Stack zu speichern. Das ist wahrscheinlich nicht das Schnellste, aber es entspricht ziemlich genau der bildlichen Vorstellung des Algorithmus.
Gehen wir davon aus, dass schon ein paar Städte in der Route sind (ist die Route leer, reduziert sich das Ganze auf eine Schleife über alle vorhandenen Städte). Zuerst einmal wird dann die Gesamtlänge der Route berechnet.
Wenn die Route vollständig ist, wird die Distanz mit der bisher kürzesten Distanz verglichen. Ist sie kürzer, wird die Route als neue kürzeste Route abgespeichert. Ist die Route nicht vollständig, geht man in einer Schleife alle verbleibenden Städte "c" durch. Ist die Distanz der vorhandenen Route plus der Distanz zwischen der letzten Stadt und c größer als die beste Route, muss man keine Routen mit c an dieser Stelle ausprobieren. Ist die Gesamtdistanz kleiner, wird c der Route hinzugefügt und mit dieser Route ruft man wieder die Methode auf. Anschließend wird c wieder aus der Route entfernt und man probiert es mit der nächsten Stadt.
Lösung
Man kommt auf folgende Lösung:
Quelltext
1:
2:
3:
| Hamburg - Berlin - Dresden - Coburg - Göttingen - Duisburg - Frankfurt - Freiburg - Stuttgart - München
1778,471 km
10670,82 km/h |
Selbstverständlich ist auch die exakt umgekehrte Route eine Lösung.
Optimierung
Die Lösung dürfte von der Performance her u.a.S. sein. So wird z.B. jede Route einmal hin und einmal zurück berücksichtigt. Auch die Bestimmung der verbleibenden Städte ist sicherlich suboptimal gelöst. Und einen Stack zu verwenden, in den immer wieder was reingepackt und rausgenommen wird, fördert die Performance auch nicht gerade. Die Lösung ist somit also nur anschaulich aber in keiner Weise als optimal oder schnell zu betrachten.
Im Anhang findet Ihr den Sourcecode zur Lösung (sollte mit dem kostenlosen Chrome Commandline Compiler kompilierbar sein) und auch eine ausführbare Version, bei der aber nicht viel zu sehen ist 
Grüße
Christian
Einloggen, um Attachments anzusehen!
_________________ Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".
|
|
Martok
Beiträge: 3661
Erhaltene Danke: 604
Win 8.1, Win 10 x64
Pascal: Lazarus Snapshot, Delphi 7,2007; PHP, JS: WebStorm
|
Verfasst: Di 25.12.07 03:53
Bingo, schon wieder was richtig. Schönes Weihnachtsgeschenk
Habs fast genauso gelöst, aber die verbleibenden Städte(-Indizes) in einem set of byte, und die besuchten Städte in einem String. Auch noch nicht optimal, aber 'ausreichend' schnell... _________________ "The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."
|
|
Tilman
Beiträge: 1405
Erhaltene Danke: 51
Win 7, Android
Turbo Delphi, Eclipse
|
Verfasst: Di 25.12.07 18:29
Die einzige Paranuss die ich abgeschickt habe, und anscheinend richtig (wenn ich mich nicht verklickt habe). Bin aber gespannt wieviele wegen Rundungsfehlern daneben gegriffen haben, wär mir um ein Haar passiert.
_________________ Bringe einen Menschen zum grübeln, dann kannst du heimlich seinen Reis essen.
(Koreanisches Sprichwort)
|
|
Marc.
Beiträge: 1876
Erhaltene Danke: 129
Win 8.1, Xubuntu 15.10
|
Verfasst: Di 25.12.07 20:37
Am Ende von Hand gelöst. *g
Die Entfernungen der Städte zueinander hatte ich richtig berrechnet, aber beim TSP hats dann gehakt.
Da half nur noch aufmalen und selbst Linien ziehen. 
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: Di 25.12.07 21:03
Also hier mal kurz meine Lösung
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:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
| Uses
Math;
Const
EarthRad: Extended = 6380;
Type
TGeoCord = Record
A, B: Extended;
End;
Const
GeoCords: Array[0..9] Of TGeoCord = (
(A: 51 + 28 / 60 + 54.46 / 3600; B: 06 + 46 / 60 + 53.59 / 3600; ),
(A: 48 + 46 / 60 + 44.13 / 3600; B: 09 + 10 / 60 + 49.88 / 3600; ),
(A: 52 + 31 / 60 + 06.85 / 3600; B: 13 + 22 / 60 + 36.01 / 3600; ),
(A: 51 + 35 / 60 + 51.51 / 3600; B: 09 + 57 / 60 + 57.20 / 3600; ),
(A: 50 + 15 / 60 + 51.04 / 3600; B: 10 + 58 / 60 + 55.50 / 3600; ),
(A: 47 + 59 / 60 + 43.68 / 3600; B: 07 + 51 / 60 + 12.43 / 3600; ),
(A: 48 + 13 / 60 + 08.18 / 3600; B: 11 + 37 / 60 + 29.16 / 3600; ),
(A: 53 + 32 / 60 + 36.11 / 3600; B: 09 + 59 / 60 + 14.91 / 3600; ),
(A: 50 + 02 / 60 + 49.21 / 3600; B: 08 + 34 / 60 + 18.53 / 3600; ),
(A: 51 + 03 / 60 + 07.60 / 3600; B: 13 + 44 / 60 + 29.63 / 3600; )
);
Var
GeoDists: Array[0..9, 0..9] Of Extended;
Function GeoDist(A, B: TGeoCord): Extended;
Begin
Result := arccos(sin(DegToRad(A.A)) * sin(DegToRad(B.A)) + cos(DegToRad(A.A)) * cos(DegToRad(B.A)) * cos(DegToRad(B.B) - DegToRad(A.B)));
Result := Result * EarthRad;
End;
function GeoDist2(A, B: TGeoCord): extended;
const
re = 6380.0;
var
l1,l2,b1,b2: Extended;
f_a,F, g, s, c, w, r, d, h1, h2, l, dummy: extended;
begin
b1 := DegToRad(A.A);
l1 := DegToRad(A.B);
b2 := DegToRad(B.A);
l2 := DegToRad(B.B);
f_a := 1/298.257223563;
F := (b1 + b2) / 2;
G := (b1 - b2) / 2;
l := (l1 - l2) / 2;
S := power(sin(g),2) * power(cos(l),2) + power(cos(f),2) * power(sin(l),2);
C := power(cos(g),2) * power(cos(l),2) + power(sin(f),2) * power(sin(l),2);
dummy := sqrt(S/C);
w := arctan(dummy) ;
R := sqrt(S * C) / w;
D := 2 * w * re;
H1 := (3 * R - 1) / (2 * C);
H2 := (3 * R + 1) / (2 * S);
result := D * (1
+ f_a * H1 * sin(f) * sin(f) * cos(g) * cos(g)
- f_a * H2 * cos(f) * cos(f) * sin(g) * sin(g));
end;
Procedure TForm1.Button1Click(Sender: TObject);
Var
X, Y: Integer;
Dest: Array[0..9] Of Integer;
DestDist: Array[0..9] of Extended;
Level: Integer;
MinDist: Extended;
CurDist: Extended;
Begin
Listbox1.Lines.Clear;
Listbox1.Lines.Add('Berechnen der Entfernungen ...');
StringGrid1.RowCount := 11;
StringGrid1.ColCount := 11;
For X := 0 To 9 Do
Begin
StringGrid1.Cells[1+X,0] := IntToStr(X);
StringGrid1.Cells[0,1+X] := IntToStr(X);
For Y := 0 To 9 Do
Begin
If X = Y Then
GeoDists[X, Y] := 0
else
GeoDists[X, Y] := GeoDist(GeoCords[X], GeoCords[Y]);
StringGrid1.Cells[1+X,1+Y] := Format('%.6f', [GeoDists[X, Y]]);
end;
end;
Listbox1.Lines.Add('Berechnen der kürzesten Strecke ...');
For X := 0 To 9 Do
Dest[X] := 0;
MinDist := Infinity;
DestDist[0] := 0;
Level := 1;
Y := 0;
Repeat
If Level = 10 Then
Begin
Inc(Y);
If Y and $F = 0 Then
Begin
Caption := 'Current Route:';
For X := 0 To 9 do
Caption := Caption + ' ' + IntToStr(Dest[X]);
Application.ProcessMessages;
end;
CurDist := 0;
For X := 1 To 9 Do
Begin
CurDist := CurDist + GeoDists[Dest[X-1], Dest[X]];
End;
If CurDist < MinDist Then
Begin
Listbox1.Lines.BeginUpdate;
Try
Listbox1.Lines.Add('Neuer kürzester Weg:');
For X := 0 To 9 Do
Begin
Listbox1.Lines.Add(Format('%d %.6f', [Dest[X], IfThen(X > 0, GeoDists[Dest[X-1], Dest[X]], 0)]));
End;
Listbox1.Lines.Add(Format('Distanz: %.3f km', [CurDist]));
MinDist := CurDist;
Finally
Listbox1.Lines.EndUpdate;
End;
End;
Dec(Level);
End;
Inc(Dest[Level]);
If Level = 0 Then
Application.ProcessMessages;
If Dest[Level] > 9 Then
Begin
Dec(Level);
Continue;
end;
X := 0;
While (X < Level) And (Dest[Level] <> Dest[X]) Do
Inc(X);
If X = Level Then
Begin
If Level >= 1 Then
Begin
DestDist[Level] := DestDist[Level-1] + GeoDists[Dest[Level-1], Dest[Level]];
If DestDist[Level] > MinDist Then
Continue;
end;
Inc(Level);
If Level < 10 Then
Dest[Level] := -1;
End;
Until Level < 0;
Caption := 'Done';
End; |
GeoDist2 ist Orthodrome mit Erdabplattung. Nimmt man diese, erhält man ungefähr 2km MEHR für die Entfernung, was dazu führt, dass man ne falsche Lösung bekommt. Und so ineffizient ist das mit dem alle durchprobieren nun auch wieder nicht ... Zumindest zeigt meine Version nach <1 Sekunde die korrekte Lösung in der Caption des Forms und in der Listbox an
Ach ja: Wer sich wundert, was die Repeat-Schleife hier macht: Die sorgt für ein iteratives Backtracing. Da hier sehr viel voraus berechnet werden kann, muss hier kaum nachgeholfen werden, um Geschwindigkeit zu bekommen.
MfG,
BenBE. _________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
|
