abgewandeltes Traveling Salesman Problem ohne Rekursion

JanaM · Hält's aus hier Beiträge: 3

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 www.delphi-forum.de/...lling+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

BenBE · Verfasst: Mi 21.09.11 01:25

Siehe meine Lösung unter www.delphi-forum.de/....php?p=479319#479319 Ab Zeile 125 geht der wichtige Teil los.

_________________

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.

JanaM · Hält's aus hier Beiträge: 3

Danke BenBE,
uff, mal sehen ob ich das verstehe. Das muss ich mir morgen mal in aller ruhe ansehen.

BenBE · Verfasst: 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.

_________________

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.

Xion · Verfasst: Do 22.09.11 11:21

Um Rekursion aufzulösen ist das Konzept meist gleich:

Statt einem rekursiven Aufruf der Form:

Delphi-Quelltext

markieren

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

markieren

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
      //letzten Auftrag auslesen
      a:=Stack[Max];
      Max:=Max-1;
      SetLength(Stack,Max+1);

      //Auftrag auswerten
      if a>100 then
        begin
          //neuen Auftrag hinzufügen
          Max:=Max+1;
          SetLength(Stack,Max+1);
          Stack[Max]:=a-1;
          //neuen Auftrag hinzufügen
          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.

_________________
a broken heart is like a broken window - it'll never heal
Jen, [this computer] is infected. If this was a human being, I'd shoot it in the face. (IT Crowd)

BenBE · Verfasst: Do 22.09.11 12:31

Statt einem Endlosschleife der Form:

Delphi-Quelltext

markieren

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

markieren

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
      //letzten Auftrag auslesen
      a:=Stack[Max];
      Max:=Max-1;
      SetLength(Stack,Max+1);

      //Auftrag auswerten
      if a>100 then
        begin
          //neuen Auftrag hinzufügen
          Max:=Max+1;
          SetLength(Stack,Max+1);
          Stack[Max]:=a-1;
          //neuen Auftrag hinzufügen
          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:

_________________

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.

Xion · Verfasst: Do 22.09.11 16:48

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

_________________
a broken heart is like a broken window - it'll never heal
Jen, [this computer] is infected. If this was a human being, I'd shoot it in the face. (IT Crowd)

JanaM · Hält's aus hier Beiträge: 3

Ahh

,ich glaub, jetzt hab ich das Prinzip verstanden.
Den Algo von BenBE konte ich auch so anpassen, das er mein Problem löst

.
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.


Delphi-Forum.de	Delphi-Library.de
C-Sharp-Forum.de	C-Sharp-Library.de