Entwickler-Ecke
Algorithmen, Optimierung und Assembler - abgewandeltes Traveling Salesman Problem ohne Rekursion
JanaM - Di 20.09.11 22:11
Titel: abgewandeltes Traveling Salesman Problem ohne Rekursion
Hallo,
ich benötige einen Algorithmus für ein leicht abgeandeltes Traveling Salesman Problem. Die Reise soll an einen vorgegebenen Startpunkt beginnen, aber es soll zum Schluß nicht wieder dorthin zurückgekehrt werden.
Ich habe hier im Forum bereits eine Lösung für dieses Problem gefunden
http://www.delphi-forum.de/viewtopic.php?t=79372&start=0&postorder=asc&highlight=travelling+weihnachtsmann aber diese nutzt leider Rekursion.
Könnt ihr mir bitte helfen den Algorithmus so umzuschreiben, das er ohne Rekursion auskommt. Ich hab irgendwo gelesen, dass es möglich ist jede Rekursion aufzulösen, aber ich verstehe nicht wie das funktionieren soll.
Viele Grüße
Jana
JanaM - Mi 21.09.11 21:54
Danke BenBE,
uff, mal sehen ob ich das verstehe. Das muss ich mir morgen mal in aller ruhe ansehen.
BenBE - Do 22.09.11 01:08
Grob gesagt: Das was man normal via nem Stack macht, ist dort in einem Array umgesetzt. Siehe am Anfang der Schleife die Ausgabe in die Caption. Ich denke, das könnte etwas beim Verständnis helfen.
Xion - Do 22.09.11 11:21
Um Rekursion aufzulösen ist das Konzept meist gleich:
Statt einem rekursiven Aufruf der Form:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| procedure DoSomething(x: Integer);
begin
while x>100 do
begin
DoSomething(x-1);
DoSomething(x-1);
end:
end; |
packt man den Aufruf z.B. in ein Array
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:
| procedure DoSomething(x: Integer);
var Stack: array of integer;
Max: integer;
a: integer;
begin
Max:=0;
SetLength(Stack,Max+1);
Stack[Max]:=x;
while Max>0 do
begin
a:=Stack[Max];
Max:=Max-1;
SetLength(Stack,Max+1);
if a>100 then
begin
Max:=Max+1;
SetLength(Stack,Max+1);
Stack[Max]:=a-1;
Max:=Max+1;
SetLength(Stack,Max+1);
Stack[Max]:=a-1;
end;
end;
end; |
Sieht erstmal komplizierter aus (eine Liste statt dem Array wäre evtl hier auch besser), dafür gibt es aber keinen Stack Overflow.
BenBE - Do 22.09.11 12:31
Statt einem Endlosschleife der Form:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
| procedure DoSomething(x: Integer);
begin
while x>100 do
begin
DoSomething(x-1);
DoSomething(x-1);
end:
end; |
packt man den Aufruf z.B. in ein Array und erhält eine nicht ausgeführte Schleife der Form:
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:
| procedure DoSomething(x: Integer);
var Stack: array of integer;
Max: integer;
a: integer;
begin
Max:=0;
SetLength(Stack,Max+1);
Stack[Max]:=x;
while Max>0 do
begin
a:=Stack[Max];
Max:=Max-1;
SetLength(Stack,Max+1);
if a>100 then
begin
Max:=Max+1;
SetLength(Stack,Max+1);
Stack[Max]:=a-1;
Max:=Max+1;
SetLength(Stack,Max+1);
Stack[Max]:=a-1;
end;
end;
end; |
Sieht erstmal komplizierter aus, funktioniert dafür aber genauso nicht wie erwartet :mrgreen:
Xion - Do 22.09.11 16:48
:oops: :shock: :autsch:
OHWE, bin ich aus der Übung...
Aber ich denke das Prinzip ist klar geworden...in Copy und Paste sicherer Form :nut:
//Edit:
Es sind doch nur 3 Worte/Zeichen falsch soweit ich das sehe :D
JanaM - Sa 24.09.11 09:59
Ahh :idea: ,ich glaub, jetzt hab ich das Prinzip verstanden.
Den Algo von BenBE konte ich auch so anpassen, das er mein Problem löst :D .
Da ich andere Distanzen benötige, hab ich die Function GeoDist angepasst (simple Berechnung mittels Pytagoras reicht mir).
Für die Einschränkung das der Startpunkt feststeht brauchte ich nur
'Until Level < 0;'
durch
Until Level < 1;
ersetzten.
Ich danke Euch beiden vielmals.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!