Traveling Salesman Problem: Backtracking/Rekursion tuts net?

Ransom · Hält's aus hier Beiträge: 14

Hallo,

hier meldet sich wieder der 13er-Info-LK-Schüler mit einem neuen Problem

Im Moment arbeite ich an einem Projekt. Dazu gehört die Entwicklung eines Programms, mit dessen Hilfe ich das Traveling Salesman Problem erklären möchte.
Ich habe in das Programm unter anderem einen einfachen Backtracking-Algorithmus eingebaut. Wenn ich diesen im laufenden Programm nun aufrufe, dauert es fast eine Minute, dann kommt eine Fehlermeldung ("Im Projekt ist eine Exception der Klasse EConvertError aufgetreten. Meldung: '' "). Ich vermute einfach mal frei heraus, dass es etwas mit der Rekursion zu tun hat, da im CPU-Fenster irgendwas mit "push" steht und ich im Projekt ansonsten keine Keller verwende.

Habe das Projekt angehängt.

Danke und ein gutes neues Jahr!

Ransom

Einloggen, um Attachments anzusehen!

IngoD7 · Beiträge: 629 D7

Siehe Kommentare in deinem Code.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

  function sofar(order:string):integer; //Dieser Funktion wird beim Backtracking für order immer der String '1' übergeben.
                                        //Kontrolliere deinen Aufruf, ob das so sein soll.
  var counter:integer;
  begin
    counter:=0;
    REPEAT              //Endlosschleife!!! Begründung siehe folgend.
      inc(counter);              //counter wird incrementiert. Erster Durchlauf counter = 1 danach 2, 3, usw.
      if length(order)<=1 then result:=0 else   //length(order) ist immer 1, die Bedingung also immer(!) erfüllt.
        CASE order[counter] of
          [...]                 //CASE-Anweisung wird nie(!) ausgeführt, daher habe ich sie hier gestrichen.
    UNTIL counter=length(order)-1;  //counter ist immer größer(!) als length(order)-1. Letzteres ist immer 0, 
                                    //und counter zählt ab 1 nach oben.
  end;  //of function sofar

Ich kenne die angewendeten Algorithmen beim Handelsreisenden nicht. Ich habe dein Prg nur ab dem Aufruf TSPc.exactbacktracking(folge,distanz); im Einzelschritt verfolgt (Haltepunkt und dann per F7), um zu sehen was es macht.

So wäre es dir auch aufgefallen.

jaenicke · Verfasst: Mo 01.01.07 05:21

Die genannte Fehlermeldung hat damit allerdings nix zu tun.
Die ist sehr einfach zu erklären und ich würde mal empfehlen, nachdem der Fehler auftritt in Delphi per Einzelschritt (F7) nach dem Ort des Fehlers zu suchen...
Da zeigt Delphi diese Zeile an:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

  procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
  var i,w:integer;
  begin
    w:=sofar(reihenfolge);
    if complete(reihenfolge)=true then
      begin
        if w<smallest then smallest:=w;
        solution:=reihenfolge;
      end
    else //if complete(reihenfolge)=false
      for i:=1 to citycount do
        if (possiblynext(inttostr(i)[1],reihenfolge)) and
          ((w+ARdistances[strtoint(reihenfolge[length(reihenfolge)-1]),i,1])<smallest)
          then
            begin
              reihenfolge:=reihenfolge+inttostr(i);
              search(reihenfolge,smallest,solution);
              //jetzt passiert das Backtracking!!
            end;
  end;

Dazu noch die Info EConvertError, da war mir klar, dass der Fehler in diesem Quelltext hier in Zeile 13 liegen muss, nämlich bei StrToInt...
Und als ich dann den Inhalt von Reihenfolge angesehen habe, war auch klar warum: Da stand nur eine 1 drin... Nun ja, Length(reihenfolge) - 1 ist also 0 und reihenfolge[0] ist also #0, also das "Nullzeichen"... Und das lässt sich nicht in einen Integer-Wert umwandeln.
Du solltest beim Zugriff auf ein bestimmtes Zeichen eines Strings immer prüfen, ob der String auch lang genug ist, wenn du das vorletzte Zeichen (Length - 1) haben willst, also mindestens 2 Zeichen lang.

IngoD7 · Beiträge: 629 D7

jaenicke hat folgendes geschrieben:

Die genannte Fehlermeldung hat damit allerdings nix zu tun.

Nein, die Fehlermeldung nicht, aber die Gedenkminute. :wink:

Ich suche Fehler möglichst analog zum Programmablauf. Hier kommt die Endlosschleife zuerst. Und da ein Programm sowieso zum Zufallsgenerator wird, wenn eine Schleife ins Nirvana läuft, befasse ich mich mit dahinterliegenden Programmteilen allermeistens erst, wenn zuvor gefundene Fehler beseitigt sind.

Ransom · Hält's aus hier Beiträge: 14

Danke schonmal an euch beide.
Ich baue ganz gerne so kleine Fehler in meine Programme ein, wie z.B. hier, auf das vorletzte, statt auf das letzte Zeichen eines Strings zuzugreifen, weshalb das Programm dann nicht läuft. Die Sache mit der falschen if-Abfrage, die in dem von IngoD7 behandelten Teil das Problem war, ist da schon komplexe Abwechslung

Ich habe jetzt also, dank eurer Hinweise, die Fehler soweit beseitigt und hab das Programm auch 1000 mal mit F7 verfolgt

Dabei ist mir folgendes aufgefallen:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

  procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
  var i,w:integer;
  begin
    w:=sofar(reihenfolge);
    if complete(reihenfolge)=true then
      begin
        if w<smallest then smallest:=w;
        solution:=reihenfolge;
      end
    else //if complete(reihenfolge)=false
      for i:=1 to citycount do
        if (possiblynext(inttostr(i)[1],reihenfolge)) and
          ((w+ARdistances[strtoint(reihenfolge[length(reihenfolge)]),i,1])<smallest)
          then
            begin
              reihenfolge:=reihenfolge+inttostr(i);
              search(reihenfolge,smallest,solution);
              //jetzt passiert das Backtracking!!
            end;
  end;

Nachdem die letzte Stufe der Rekursion durchlaufen ist und das Programm wieder zur vorherigen zurückspringt, wird statt der in dieser Stufe vorhandenen reihenfolge (bei 4 Städten z.B. '123') die reihenfolge verwendet, die in der innersten Rekursion gefunden und dort schon in solution geschrieben wurde. Zum Beispiel also '12341'. Daher wird das Programm immer nur so durchlaufen, dass die Städte in der Reihenfolge ABCDA besucht werden und es werden keine kürzeren Routen gesucht.

Zum besseren Verständnis habe ich ein Struktogramm der search-Prozedur erstellt:
[url=img466.imageshack.us...mage=struktong5.gif] user defined image

[/url]

Er soll also durch Rekursion zurückspringen und statt ABCDA auch mal ADCBA oder ACBDA etc ausprobieren, da diese Wege ja für die Rundreise kürzer sein könnten. Er benutzt aber immer nur das zuerst gefundene ABCDA anstatt wieder die Reihenfolge weiterzuverwenden, die in der jeweiligen Rekursionsstufe gefunden worden war.

Einloggen, um Attachments anzusehen!

IngoD7 · Beiträge: 629 D7

Ransom hat folgendes geschrieben:

Er soll also durch Rekursion zurückspringen und statt ABCDA auch mal ADCBA oder ACBDA etc ausprobieren, da diese Wege ja für die Rundreise kürzer sein könnten. Er benutzt aber immer nur das zuerst gefundene ABCDA anstatt wieder die Reihenfolge weiterzuverwenden, die in der jeweiligen Rekursionsstufe gefunden worden war.

So ähnlich kann ich das bestätigen.

Er ruft bei 4 Orten die Procedure search immer genau 9 mal auf. Und zwar immer mit den folgenden reihenfolge(n):
1
12
123
1234
12341
1234
123
1234
1234

Egal bei wieviel Orten - es wird nie die Reihenfolge wirklich geändert. Er geht bei Erstellung der Reihenfolgen nie weiter zurück als bis 123. Somit kann er z.B. nie den Ort Nummer 3 mal an zweiter Stelle berechnen.

Um das zu überprüfen, habe ich eine Listbox1 auf das Form gezogen und folgendes ins Programm eingefügt:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
  var i,w:integer;
  begin
    w:=sofar(reihenfolge);
    Form1.ListBox1.Items.Add(reihenfolge);  //<--EINGEFÜGT
    if complete(reihenfolge)=true then
[...]
  end;

Ich stecke in dem Programm nicht tief genug drin, um zu sagen warum es sich so verhält. Es ist auch leider nicht sonderlich leicht lesbar.

Anmerkung: Ich habe hier bei mir die Procedure delay in der Unit Udelay deaktiviert (auskommentiert). Dann geht's schneller. Wer braucht schon diese künstlichen Pausen ...?

Jedenfalls würde ich neben der Einzelschrittdiagnose immer diese Art von Protokoll mittels Listboxen oder Memos - wie oben erwähnt - empfehlen. Gerade bei Rekursivaufrufen sollte man im Fehlerfall das Programm dazu nötigen, seine Geheimnisse mal selbst aufzulisten. ;-)

Ransom · Hält's aus hier Beiträge: 14

Ja hab ich denn da jetzt was falsch verstanden, oder sollte er eigentlich bei dieser Rekursion z.B. mit 4 Städten so vorgehen:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

A
AB
ABC
ABCD
ABCDA
ABDC
ABDCA
ACBD
ACBDA
ACDB
ACDBA
ADBC
ADBCA
ADCB
ADCBA

?

Ich dachte immer, Rekursion heißt, er macht alles bis zum erneuten Aufruf und nachdem er diesen Aufruf verarbeitet hat, macht er den Rest weiter, der nach dem Aufruf steht?

IngoD7 · Beiträge: 629 D7

Ransom hat folgendes geschrieben:

Ja hab ich denn da jetzt was falsch verstanden, oder sollte er eigentlich bei dieser Rekursion z.B. mit 4 Städten so vorgehen:

Wie auch immer. Ich würde es eh nicht so programmieren, wie du es da angefangen bist. Aber darum geht nicht. ;-)

Er muss in jedem Fall alle möglichen Routen bei 4 Städten berechnen - unabhängig von den möglichen Zwischenschritten.
Also:
ABCDA
ABDCA
ACBDA
ACDBA
ADBCA
ADCBA

Dabei mag er - abhängig von der Programmierung - vielleicht z.B. die Route ADBCA nicht mehr zu ende berechnen, weil sie vielleicht schon nach der Strecke ADB zu lang ist und er das merkt. Aber zumindest sollte er auch mal irgendwann den Versuch unternehmen, die Route überhaupt mal umzustellen.
Das ist bei dir bisher nicht der Fall.

Ransom hat folgendes geschrieben:

Ich dachte immer, Rekursion heißt, er macht alles bis zum erneuten Aufruf und nachdem er diesen Aufruf verarbeitet hat, macht er den Rest weiter, der nach dem Aufruf steht?

Ich weiß nicht, ob ich das richtig verstanden habe, aber eines ist sicher: Nach dem rekursiven Aufruf von search in der Procedure search steht in deinem Programm doch gar nichts mehr.

Da, wo deine Bemerkung steht (siehe bei <== HIER im Code)...

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

  procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
  var i,w:integer;
  begin
    w:=sofar(reihenfolge);
    if complete(reihenfolge)=true then
      begin
        if w<smallest then smallest:=w;
        solution:=reihenfolge;
      end
    else //if complete(reihenfolge)=false
      for i:=1 to citycount do
        if (possiblynext(inttostr(i)[1],reihenfolge)) and
          ((w+ARdistances[strtoint(reihenfolge[length(reihenfolge)]),i,1])<smallest)
          then
            begin
              reihenfolge:=reihenfolge+inttostr(i);
              search(reihenfolge,smallest,solution);
              //jetzt passiert das Backtracking!!            //<============== HIER
            end;
  end;

... müsste eigentlich irgendwelcher Programmcode auftauchen.

Es ist jedenfalls die erste rekursive Procedure die ich sehe, die direkt hinter dem rekursiven Aufruf endet.

Kurz:
Deine Procedure search stimmt leider hinten und vorne nicht.

Ransom · Hält's aus hier Beiträge: 14

Du hast da was übersehen: Die Prozedur endet nicht hinter dem rekursiven Aufruf - da steckt er nämlich noch in einer for-Schleife, die er zu Ende führen muss, damit eben das funktioniert, was ich haben will

Die Prozedur habe ich auf der Homepage einer Schule gefunden und geringfügig angepasst - prinzipiell ist sie aber gleich geblieben.

IngoD7 hat folgendes geschrieben:

Aber zumindest sollte er auch mal irgendwann den Versuch unternehmen, die Route überhaupt mal umzustellen.
Das ist bei dir bisher nicht der Fall.

Das ist mir auch aufgefallen

- was ich bräuchte, wär die Antwort, warum er das nicht macht...

Kennt sich hier niemand wenigstens etwas mit dem TSP oder eben halt Rekursion aus? Ich verzweifel' langsam

IngoD7 · Beiträge: 629 D7

Ransom hat folgendes geschrieben:

Du hast da was übersehen: Die Prozedur endet nicht hinter dem rekursiven Aufruf - da steckt er nämlich noch in einer for-Schleife, die er zu Ende führen muss, damit eben das funktioniert, was ich haben will

Mit der Schleife ergänzt er doch nur die Route. Im längsten Fall bis alle Orte eingebaut sind. Irgendwann fällt er aber zurück, nämlich dann, wenn er erstmals die Route ABCDA aufgebaut hat. Und was dann an der Stelle passiert, kannste dir ja mal selber anschauen:

Deklariere eine globale Variable SearchTiefe als integer.
Ziehe eine TListBox als Listbox1 auf das Form.
Ergänze folgende Zeilen im Code:

markieren

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:

  procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
  var i,w:integer;
  begin

    w:=sofar(reihenfolge);
    if complete(reihenfolge)=true then
      begin
        if w<smallest then smallest:=w;
        solution:=reihenfolge;
      end
    else //if complete(reihenfolge)=false
      for i:=1 to citycount do
        if (possiblynext(inttostr(i)[1],reihenfolge)) and
          ((w+ARdistances[strtoint(reihenfolge[length(reihenfolge)]),i,1])<smallest)
          then
            begin
              reihenfolge:=reihenfolge+inttostr(i);
              inc(SearchTiefe);
              search(reihenfolge,smallest,solution);
              dec(SearchTiefe);
              Form1.ListBox1.Items.Add(inttostr(SearchTiefe)+#32+inttostr(smallest)+#32+solution);
              //jetzt passiert das Backtracking!!
            end;
  end;

begin
  entfernung:=maxInt;
  loesungsfolge:='';
  SearchTiefe:=1;
  search('1',entfernung,loesungsfolge);
  SearchTiefe:=0;
  Form1.ListBox1.Items.Add('----------------------');
  Form1.ListBox1.Items.Add(inttostr(SearchTiefe)+#32+inttostr(entfernung)+#32+loesungsfolge);
end;

Lass das Programm so laufen und schaue dir den Inhalt der Listbox an.
Weder die Suchtiefen, noch deren Ergebnisse (ist immer dasselbe) lassen auf korrekt Implementierung schließen.

Momentan halte ich den ganzen Algorithmus für so verkehrt, dass es sich kaum lohnt, da den Fehler zu suchen. Ich würde es neu programmieren.

Ransom hat folgendes geschrieben:

Kennt sich hier niemand wenigstens etwas mit dem TSP oder eben halt Rekursion aus? Ich verzweifel' langsam

Danke, dass ich deiner Meinung nach von beidem nicht einmal "wenigstens etwas" Ahnung habe. :roll:

Ich weiß ja nicht, wie lange du dich schon mit solchen Sachen beschäftigst, aber Rekursion hat es in sich. Das menschliche Hirn ist dafür normalerweise nicht gebaut. ;-)

Und noch schwieriger ist es, fremde Rekursionen anderer Leute zu durchschauen - gerade dann, wenn sie nicht funktionieren. Von daher hast du schon relativ großes Glück, dass überhaupt jemand versucht, sich so tief mit deinem Programm zu beschäftigen.

Ehemaliges Mitglied Erhaltene Danke: 1

ich würde dir erst mal literaturstudium empfehlen... Google hilft hier weiter...

bspw.

da gibts auch jede menge pascal beispielcodes.. aber bitte nicht, als deine lösung dem lehrer verkaufen :wink:

Ransom · Hält's aus hier Beiträge: 14

Okay. Gucken wir uns das gerade mal aus der anderen Perspektive an:

Ausgehend von Stadt A soll er mögliche Routen suchen. Bevor er eine Stadt an die Reihenfolge dranhängt, guckt er, ob die Reihenfolge + diese Stadt nicht schon größer ist, als die schon gefundene, kürzeste Route (zu Anfang maxInt). Wenn dem nicht so ist, hängt er die Stadt an die Reihenfolge und sucht weiter Nachfolger, bis er alle Städte besucht hat. Dann kommt noch die Rückreise zur Ausgangsstadt A dazu. Jetzt wo eine komplette mögliche Rundreise gefunden ist, guckt er, ob diese Reise kürzer ist, als die bisher gefundene kürzeste. Wenn ja wird diese die neue kürzeste Reise. Und jetzt soll er eben "zurückspringen" und eine andere Möglichkeit suchen, z.B. statt nach AB zu C zu gehen nach D gehen etc.

Ich glaube, das Prinzip ist dir längst klar und ich glaube auch, dass dieser Ansatz richtig ist, oder? Genau das steht im Struktogramm, das ich (übrigens durch Google-Suche) hier gefunden habe: wvs.be.schule.de/...
Den Artikel auf Wikipedia hatte ich mir auch schon durchgelesen. Allerdings ist alles, was da so an Algorithmen steht, viel zu hochgestochen für meine Zwecke (ich bin kein Forscher, sondern nur ein Schüler, der einen passenden Backtracking-Algorithmus für das Problem erklären soll - Sinn der Übung ist, dass die anderen Schüler [und auch ich] diesen auch verstehen

). Zu komplex ist z.B. auch der Code von DelphiForFun.
Ich habe mir überlegt, wie ich den Algorithmus schreiben würde, und bin dabei genau auf die Lösung gekommen, die auch in oben verlinkter Quelle angegeben ist. Ich möchte mir ja auch lieber selber was ausdenken, was ich dann auch verstehe, statt einfach etwas zu kopieren, das bringt mir selber ja auch nichts.

Worauf ich hinauswill: Meint ihr nicht, dass der Ansatz im Struktogramm richtig ist? Meiner Meinung nach müsste er eigentlich funktionieren. IngoD7, du sagst, du hälst den Algorithmus für total verkehrt. Nur warum? Ich verstehe nicht, was daran falsch sein soll und mir fällt ehrlich gesagt auch kein anderer Ansatz zum neu Programmieren ein.
Ich bin nunmal nur Schüler und damit quasi Delphi-Anfänger und habe keine jahrelange Erfahrung mit komplexer Programmierung.

@Ingo: Da du nur sagst "das tuts nicht" ging ich davon aus, dass du dich mit dem TSP nicht auskennst. Mir ist klar, dass Rekursion schon eine ziemlich komplizierte Sache ist - vielleicht kannst du aber auch nachvollziehen, dass mich "das stimmt hinten und vorne nicht" ohne etwas Konkretes oder "such doch mal in Google" (was ich schließlich gemacht hab und dabei diesen noch erfreulich verständlichen Algorithmus gefunden habe) der Lösung nicht näher bringen. Da ich das Struktogramm von einer Schulhomepage habe, dachte ich, dass es korrekt sein muss - zumal ich ja wie gesagt auf den gleichen Ansatz kam.

Um die Prozedur einfach zu halten, würde ich es vorziehen, in meiner Implementation einen möglichen Fehler zu suchen, zumal ich bisher keinen Grund habe, die Richtigkeit des Algorithmus' aus der Quelle in Frage zu stellen.

IngoD7 · Beiträge: 629 D7

Ransom hat folgendes geschrieben:

Ich glaube, das Prinzip ist dir längst klar und ich glaube auch, dass dieser Ansatz richtig ist, oder?

Ja.

Ransom hat folgendes geschrieben:

Worauf ich hinauswill: Meint ihr nicht, dass der Ansatz im Struktogramm richtig ist?

Ist doch eigentlich egal, oder? Wenn das Struktogramm so richtig ist, dann ist es das Programm aber zumindest nicht. Den Fehler haben wir bisher aber noch nicht gefunden, obwohl wir möglicherweise ein korrektes Struktogramm vorliegen haben. Ist das Struktogramm falsch, haben wir eh schlechte Karten.
Ich aus meiner Sicht kann das Struktogramm so nicht bewerten. Ich traue der Schleife for i jedenfalls nicht.
Das kann ich dir aber kaum verbal-schriftlich erklären, ich kann es mir im Moment ja selbst noch nicht erklären. Ich kann es möglicherweise durch Analysen des Programmlaufs irgendwann beweisen und dann vielleicht auch erklären, aber im Moment eben noch nicht. (Könnte ich's würde ich's dir ja sagen.) Daher interessiert mich das Struktogramm momentan nicht so sehr.

Ransom hat folgendes geschrieben:

IngoD7, du sagst, du hälst den Algorithmus für total verkehrt. Nur warum? Ich verstehe nicht, was daran falsch sein soll und mir fällt ehrlich gesagt auch kein anderer Ansatz zum neu Programmieren ein.

Ich meine damit nicht unbedingt das Struktogramm (siehe Erklärung oben), ich meine den programmierten Algorithmus. Dass der nicht korrekt ist, beweist ja das Ergebnis.

Zum Neuprogrammieren würde mir möglicherweise keine so besonders neue Lösungsfindung einfallen, aber mit Sicherheit eine andere Programmierung, die besser lesbar ist. Aber um dir das zu 100% hier und in diesem Augenblick voraussagen zu können fehlt mir einfach etwas das "Gefühl" für Rekursion. Wenn man sich damit nicht ständig beschäftigt, verliert man es. Ich habe schon rekursiv programmiert, das ist aber einen Augenblick her.

Ransom hat folgendes geschrieben:

@Ingo: [...]vielleicht kannst du aber auch nachvollziehen, dass mich "das stimmt hinten und vorne nicht" ohne etwas Konkretes [...] der Lösung nicht näher bringen.

Ja, natürlich kann ich das nachvollziehen. Aber ich kenne den Fehlergrund in deinem Code auch noch nicht. Ich vermute keinen Tippfehler, sondern einen dicken Logikfehler. Und der ist aus so einem schlecht lesbaren Code nicht soooo schnell rauszufinden.

Ich kann dir noch keine Lösung präsentieren, aber ich habe dir eine kleine Hilfe dahin aufgezeigt: Die Analyse von Programmteilen mittels vom Programm selbst erzeugten Protokollen in Listboxen z.B.

Anders gehe ich das Problem im Moment auch nicht an. Zur Zeit bastel ich nahezu hinter jeden zweiten Zeile der Proc search ein Form1.Listbox1.Items.Add(<<Aktuelle Inhalte der Variablen>>), einfach um zu sehen, wann er was gerade hat und berechnet. Im Kopf kann das doch kein Mensch überblicken. Solche Analysen könntest du auch betreiben. Oder drauf warten, dass meine Zeit es zulässt und mein Ehrgeiz lange genug anhält, dir eine Lösung zu präsentieren.

Vielleicht hast du ja auch Glück, dass hier ein absoluter Crack mitliest und denkt: "Das Elend ist ja nicht länger zu ertragen. Jetzt schaue ich mir die Sache mal an." ;-)

Ransom hat folgendes geschrieben:

Um die Prozedur einfach zu halten, würde ich es vorziehen, in meiner Implementation einen möglichen Fehler zu suchen, zumal ich bisher keinen Grund habe, die Richtigkeit des Algorithmus' aus der Quelle in Frage zu stellen.

Um die Prozedur einfach zu halten??? :lol:

Na, das ist nicht gerade mein Grund.
Mein Grund, bei deiner Implementation zu bleiben ist der, dass du dich damit schon befasst hast und dir jeder hingeklatschte neue funktionierende Algorithmus absolut nichts bringen würde.

Also: Forschen wir weiter ...

Ehemaliges Mitglied Erhaltene Danke: 1

das strukto ist teilweise korrekt. du darfst aber nicht das for... mit for in pascal gleichsetzen. sondern für jede.... und hier ist der unterschied... zwischen einer iterativen udn einer rekursiven lösung... das strukto zeigt dir eine rekursive lösung auf, welche du interativ lösen möchtest ohne jedoch darauf einzugehen. deswegen bleib ich dabei, beschäftige dich erst mal theoretisch mit dem TSP und der rekursion... und schau die die beispielprogramme an...

IngoD7 · Beiträge: 629 D7

So, jetzt gibt es Futter!

Ich habe - wie angekündigt - jeden Schritt der Procedure search quasi von ihr selbst protokollieren lassen. Dabei habe ich sozusagen jede Entscheidung und Maßnahme, die die Procedure trifft, "ins Deutsche" übersetzt. Dennoch ist es etwas schwer zu lesen, aber es sollte gehen. Notfalls sollten Papier und Bleistift helfen, wenn das Hirn es nicht mehr packt. ;-)

Die V- und N-Nummern am Anfang der Zeilen sind Marken hier bei mir in deinem Quelltext und ansonsten für die Analyse völlig unwichtig.

Was auffällt ist z.B. folgendes:
Bei Aufrufen der Proc search sollte die erreichte Rekursionstiefe immer gleich der Anzahl der bereits eingebauten Orte in der Route sein. Das ist aber nicht immer der Fall, nur am Anfang. Beim 6. Aufruf ist das schon nicht mehr so.

Außerdem habe ich einen Bock gefunden:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

  procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
  var i,w:integer;
  begin

    w:=sofar(reihenfolge);
    if complete(reihenfolge)=true then
      begin
        if w<smallest then smallest:=w;
        solution:=reihenfolge;
      end
    [...]

Sobald eine Reihenfolge komplett wäre, würdest du sie immer zur aktuellen Lösung machen - auch wenn sie nicht die aktuell kürzeste wäre. Im Moment wirkt sich dieser Fehler aber nicht aus, weil der Programmlauf eh nur einmal dort überhaupt hinkommt. Es wird im ganzen Lauf immer nur genau eine komplette Lösung gefunden. Das ist die, die er seit dem 5. Aufruf von search durchschleppt und am Schluss auch ausgibt.

Lies dich mal ein in die Materie und komme wieder auf mich zu, wenn es hier weitergehen soll.

Das Protokoll für 4 Orte:

markieren

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:
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:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:

V00   ==> Erstmaliger Aufruf von search!

V01   1. Aufruf von Procedure search.  --> Rekursionstiefe:1
      Aktuelle kürzeste Entfernung:2147483647   Analyseroute: "1"   Aktuelle Lösungsroute: ""
      Ermittelte Strecke für Analyseroute:0
V04   Analyseroute noch nicht komplett. Schleife fürs Anhängen des nächsten Ortes starten.
V05      Rekursionstiefe: 1 - Schleifenvariable i (Ort) = 1
V06         Zwischenergebnis: Ort "1" steht als letztes in aktueller Route "1"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "1" kann NICHT an bestehender Route "1" angehängt werden.
V05      Rekursionstiefe: 1 - Schleifenvariable i (Ort) = 2
V09         ERGEBNIS: Ort "2" könnte an bestehender Route "1" angehängt werden.
V10   Neuer Ort "2" wird angehängt, da er die Strecke nicht in unzulässiger Weise verlängert.
         (Neue Entfernung (365) ist noch kleiner als bisherige kürzeste Lösung (2147483647).)
      ==> Eine Rekursionsebene tiefer gehen (Rekursiver Aufruf von search)!

V01   2. Aufruf von Procedure search.  --> Rekursionstiefe:2
      Aktuelle kürzeste Entfernung:2147483647   Analyseroute: "12"   Aktuelle Lösungsroute: ""
      Ermittelte Strecke für Analyseroute:365
V04   Analyseroute noch nicht komplett. Schleife fürs Anhängen des nächsten Ortes starten.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 1
V07         Zwischenergebnis: Ort "1" befindet sich bereits in aktueller Route "12"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "1" kann NICHT an bestehender Route "12" angehängt werden.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 2
V06         Zwischenergebnis: Ort "2" steht als letztes in aktueller Route "12"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "2" kann NICHT an bestehender Route "12" angehängt werden.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 3
V09         ERGEBNIS: Ort "3" könnte an bestehender Route "12" angehängt werden.
V10   Neuer Ort "3" wird angehängt, da er die Strecke nicht in unzulässiger Weise verlängert.
         (Neue Entfernung (840) ist noch kleiner als bisherige kürzeste Lösung (2147483647).)
      ==> Eine Rekursionsebene tiefer gehen (Rekursiver Aufruf von search)!

V01   3. Aufruf von Procedure search.  --> Rekursionstiefe:3
      Aktuelle kürzeste Entfernung:2147483647   Analyseroute: "123"   Aktuelle Lösungsroute: ""
      Ermittelte Strecke für Analyseroute:840
V04   Analyseroute noch nicht komplett. Schleife fürs Anhängen des nächsten Ortes starten.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 1
V07         Zwischenergebnis: Ort "1" befindet sich bereits in aktueller Route "123"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "1" kann NICHT an bestehender Route "123" angehängt werden.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 2
V07         Zwischenergebnis: Ort "2" befindet sich bereits in aktueller Route "123"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "2" kann NICHT an bestehender Route "123" angehängt werden.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 3
V06         Zwischenergebnis: Ort "3" steht als letztes in aktueller Route "123"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "3" kann NICHT an bestehender Route "123" angehängt werden.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 4
V09         ERGEBNIS: Ort "4" könnte an bestehender Route "123" angehängt werden.
V10   Neuer Ort "4" wird angehängt, da er die Strecke nicht in unzulässiger Weise verlängert.
         (Neue Entfernung (1260) ist noch kleiner als bisherige kürzeste Lösung (2147483647).)
      ==> Eine Rekursionsebene tiefer gehen (Rekursiver Aufruf von search)!

V01   4. Aufruf von Procedure search.  --> Rekursionstiefe:4
      Aktuelle kürzeste Entfernung:2147483647   Analyseroute: "1234"   Aktuelle Lösungsroute: ""
      Ermittelte Strecke für Analyseroute:1260
V04   Analyseroute noch nicht komplett. Schleife fürs Anhängen des nächsten Ortes starten.
V05      Rekursionstiefe: 4 - Schleifenvariable i (Ort) = 1
V07         Zwischenergebnis: Ort "1" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V08         Zwischenergebnis: Ort "1" als Startort bei ansonsten bereits fertiger Route "1234" identifiziert
                              ==> Ort kann (als Endort) doch angehängt werden.
V09         ERGEBNIS: Ort "1" könnte an bestehender Route "1234" angehängt werden.
V10   Neuer Ort "1" wird angehängt, da er die Strecke nicht in unzulässiger Weise verlängert.
         (Neue Entfernung (1426) ist noch kleiner als bisherige kürzeste Lösung (2147483647).)
      ==> Eine Rekursionsebene tiefer gehen (Rekursiver Aufruf von search)!

V01   5. Aufruf von Procedure search.  --> Rekursionstiefe:5
      Aktuelle kürzeste Entfernung:2147483647   Analyseroute: "12341"   Aktuelle Lösungsroute: ""
      Ermittelte Strecke für Analyseroute:1426
V02   Analyseroute komplett.
V03   Neue Route ist kürzer (1426) als bisherige Lösung (2147483647). Entfernung wird als momentan kürzeste übernommen.
V11   Analyseroute "12341" wird als aktuelle Lösung übernommen.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

N13   1. Rückfall aus Procedure search.  --> Rekursionstiefe:4
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "12341"   Aktuelle Lösungsroute: "12341"
      Schleife fürs Anhängen des nächsten Ortes fortsetzen. Aktueller Stand der Schleifenvariable i: 1
V05      Rekursionstiefe: 4 - Schleifenvariable i (Ort) = 2
V07         Zwischenergebnis: Ort "2" befindet sich bereits in aktueller Route "12341"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "2" kann NICHT an bestehender Route "12341" angehängt werden.
V05      Rekursionstiefe: 4 - Schleifenvariable i (Ort) = 3
V07         Zwischenergebnis: Ort "3" befindet sich bereits in aktueller Route "12341"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "3" kann NICHT an bestehender Route "12341" angehängt werden.
V05      Rekursionstiefe: 4 - Schleifenvariable i (Ort) = 4
V07         Zwischenergebnis: Ort "4" befindet sich bereits in aktueller Route "12341"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "4" kann NICHT an bestehender Route "12341" angehängt werden.
N15   Schleife fürs Anhängen des nächsten Ortes beendet.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

N13   2. Rückfall aus Procedure search.  --> Rekursionstiefe:3
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "1234"   Aktuelle Lösungsroute: "12341"
      Schleife fürs Anhängen des nächsten Ortes fortsetzen. Aktueller Stand der Schleifenvariable i: 4
N15   Schleife fürs Anhängen des nächsten Ortes beendet.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

N13   3. Rückfall aus Procedure search.  --> Rekursionstiefe:2
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "123"   Aktuelle Lösungsroute: "12341"
      Schleife fürs Anhängen des nächsten Ortes fortsetzen. Aktueller Stand der Schleifenvariable i: 3
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 4
V09         ERGEBNIS: Ort "4" könnte an bestehender Route "123" angehängt werden.
V10   Neuer Ort "4" wird angehängt, da er die Strecke nicht in unzulässiger Weise verlängert.
         (Neue Entfernung (785) ist noch kleiner als bisherige kürzeste Lösung (1426).)
      ==> Eine Rekursionsebene tiefer gehen (Rekursiver Aufruf von search)!

V01   6. Aufruf von Procedure search.  --> Rekursionstiefe:3
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "1234"   Aktuelle Lösungsroute: "12341"
      Ermittelte Strecke für Analyseroute:1260
V04   Analyseroute noch nicht komplett. Schleife fürs Anhängen des nächsten Ortes starten.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 1
V07         Zwischenergebnis: Ort "1" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V08         Zwischenergebnis: Ort "1" als Startort bei ansonsten bereits fertiger Route "1234" identifiziert
                              ==> Ort kann (als Endort) doch angehängt werden.
V09         ERGEBNIS: Ort "1" könnte an bestehender Route "1234" angehängt werden.
V16   Neuer Ort "1" wird nicht angehängt, da er die Strecke in unzulässiger Weise verlängern würde (zu lang).
         (Neue Entfernung (1426) wäre nicht kürzer als bisherige kürzeste Lösung (1426).)
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 2
V07         Zwischenergebnis: Ort "2" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "2" kann NICHT an bestehender Route "1234" angehängt werden.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 3
V07         Zwischenergebnis: Ort "3" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "3" kann NICHT an bestehender Route "1234" angehängt werden.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 4
V06         Zwischenergebnis: Ort "4" steht als letztes in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "4" kann NICHT an bestehender Route "1234" angehängt werden.
N15   Schleife fürs Anhängen des nächsten Ortes beendet.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

N13   4. Rückfall aus Procedure search.  --> Rekursionstiefe:2
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "1234"   Aktuelle Lösungsroute: "12341"
      Schleife fürs Anhängen des nächsten Ortes fortsetzen. Aktueller Stand der Schleifenvariable i: 4
N15   Schleife fürs Anhängen des nächsten Ortes beendet.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

N13   5. Rückfall aus Procedure search.  --> Rekursionstiefe:1
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "12"   Aktuelle Lösungsroute: "12341"
      Schleife fürs Anhängen des nächsten Ortes fortsetzen. Aktueller Stand der Schleifenvariable i: 2
V05      Rekursionstiefe: 1 - Schleifenvariable i (Ort) = 3
V09         ERGEBNIS: Ort "3" könnte an bestehender Route "12" angehängt werden.
V10   Neuer Ort "3" wird angehängt, da er die Strecke nicht in unzulässiger Weise verlängert.
         (Neue Entfernung (475) ist noch kleiner als bisherige kürzeste Lösung (1426).)
      ==> Eine Rekursionsebene tiefer gehen (Rekursiver Aufruf von search)!

V01   7. Aufruf von Procedure search.  --> Rekursionstiefe:2
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "123"   Aktuelle Lösungsroute: "12341"
      Ermittelte Strecke für Analyseroute:840
V04   Analyseroute noch nicht komplett. Schleife fürs Anhängen des nächsten Ortes starten.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 1
V07         Zwischenergebnis: Ort "1" befindet sich bereits in aktueller Route "123"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "1" kann NICHT an bestehender Route "123" angehängt werden.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 2
V07         Zwischenergebnis: Ort "2" befindet sich bereits in aktueller Route "123"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "2" kann NICHT an bestehender Route "123" angehängt werden.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 3
V06         Zwischenergebnis: Ort "3" steht als letztes in aktueller Route "123"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "3" kann NICHT an bestehender Route "123" angehängt werden.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 4
V09         ERGEBNIS: Ort "4" könnte an bestehender Route "123" angehängt werden.
V10   Neuer Ort "4" wird angehängt, da er die Strecke nicht in unzulässiger Weise verlängert.
         (Neue Entfernung (1260) ist noch kleiner als bisherige kürzeste Lösung (1426).)
      ==> Eine Rekursionsebene tiefer gehen (Rekursiver Aufruf von search)!

V01   8. Aufruf von Procedure search.  --> Rekursionstiefe:3
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "1234"   Aktuelle Lösungsroute: "12341"
      Ermittelte Strecke für Analyseroute:1260
V04   Analyseroute noch nicht komplett. Schleife fürs Anhängen des nächsten Ortes starten.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 1
V07         Zwischenergebnis: Ort "1" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V08         Zwischenergebnis: Ort "1" als Startort bei ansonsten bereits fertiger Route "1234" identifiziert
                              ==> Ort kann (als Endort) doch angehängt werden.
V09         ERGEBNIS: Ort "1" könnte an bestehender Route "1234" angehängt werden.
V16   Neuer Ort "1" wird nicht angehängt, da er die Strecke in unzulässiger Weise verlängern würde (zu lang).
         (Neue Entfernung (1426) wäre nicht kürzer als bisherige kürzeste Lösung (1426).)
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 2
V07         Zwischenergebnis: Ort "2" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "2" kann NICHT an bestehender Route "1234" angehängt werden.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 3
V07         Zwischenergebnis: Ort "3" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "3" kann NICHT an bestehender Route "1234" angehängt werden.
V05      Rekursionstiefe: 3 - Schleifenvariable i (Ort) = 4
V06         Zwischenergebnis: Ort "4" steht als letztes in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "4" kann NICHT an bestehender Route "1234" angehängt werden.
N15   Schleife fürs Anhängen des nächsten Ortes beendet.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

N13   6. Rückfall aus Procedure search.  --> Rekursionstiefe:2
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "1234"   Aktuelle Lösungsroute: "12341"
      Schleife fürs Anhängen des nächsten Ortes fortsetzen. Aktueller Stand der Schleifenvariable i: 4
N15   Schleife fürs Anhängen des nächsten Ortes beendet.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

N13   7. Rückfall aus Procedure search.  --> Rekursionstiefe:1
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "123"   Aktuelle Lösungsroute: "12341"
      Schleife fürs Anhängen des nächsten Ortes fortsetzen. Aktueller Stand der Schleifenvariable i: 3
V05      Rekursionstiefe: 1 - Schleifenvariable i (Ort) = 4
V09         ERGEBNIS: Ort "4" könnte an bestehender Route "123" angehängt werden.
V10   Neuer Ort "4" wird angehängt, da er die Strecke nicht in unzulässiger Weise verlängert.
         (Neue Entfernung (420) ist noch kleiner als bisherige kürzeste Lösung (1426).)
      ==> Eine Rekursionsebene tiefer gehen (Rekursiver Aufruf von search)!

V01   9. Aufruf von Procedure search.  --> Rekursionstiefe:2
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "1234"   Aktuelle Lösungsroute: "12341"
      Ermittelte Strecke für Analyseroute:1260
V04   Analyseroute noch nicht komplett. Schleife fürs Anhängen des nächsten Ortes starten.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 1
V07         Zwischenergebnis: Ort "1" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V08         Zwischenergebnis: Ort "1" als Startort bei ansonsten bereits fertiger Route "1234" identifiziert
                              ==> Ort kann (als Endort) doch angehängt werden.
V09         ERGEBNIS: Ort "1" könnte an bestehender Route "1234" angehängt werden.
V16   Neuer Ort "1" wird nicht angehängt, da er die Strecke in unzulässiger Weise verlängern würde (zu lang).
         (Neue Entfernung (1426) wäre nicht kürzer als bisherige kürzeste Lösung (1426).)
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 2
V07         Zwischenergebnis: Ort "2" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "2" kann NICHT an bestehender Route "1234" angehängt werden.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 3
V07         Zwischenergebnis: Ort "3" befindet sich bereits in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "3" kann NICHT an bestehender Route "1234" angehängt werden.
V05      Rekursionstiefe: 2 - Schleifenvariable i (Ort) = 4
V06         Zwischenergebnis: Ort "4" steht als letztes in aktueller Route "1234"  ==> Ort kann nicht angehängt werden.
V09         ERGEBNIS: Ort "4" kann NICHT an bestehender Route "1234" angehängt werden.
N15   Schleife fürs Anhängen des nächsten Ortes beendet.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

N13   8. Rückfall aus Procedure search.  --> Rekursionstiefe:1
      Aktuelle kürzeste Entfernung:1426   Analyseroute: "1234"   Aktuelle Lösungsroute: "12341"
      Schleife fürs Anhängen des nächsten Ortes fortsetzen. Aktueller Stand der Schleifenvariable i: 4
N15   Schleife fürs Anhängen des nächsten Ortes beendet.
N12   ==> Eine Rekursionsebene höher gehen (Rückfall aus search)!

      ---------------------------------------------------------------------------------------
N14   Letzter Rückfall aus Procedure search.  --> Rekursionstiefe:0
      Kürzeste Entfernung:1426   Lösungsroute: "12341"

IngoD7 · Beiträge: 629 D7

Womit wir anscheinend beim Paradebeispiel für "Zeitinvestition für die Tonne" sind ...? :cry:

Naja, solltest du entgegen dem Anschein das Interesse nicht verloren haben oder irgendjemand anders sich hierfür interessieren: Hier die Lösung.

Zuvor eine Ergänzung zu meinem letzten Posting:

IngoD7 hat folgendes geschrieben:

Außerdem habe ich einen Bock gefunden:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

  procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
  var i,w:integer;
  begin

    w:=sofar(reihenfolge);
    if complete(reihenfolge)=true then
      begin
        if w<smallest then smallest:=w;
        solution:=reihenfolge;
      end
    [...]

Sobald eine Reihenfolge komplett wäre, würdest du sie immer zur aktuellen Lösung machen - auch wenn sie nicht die aktuell kürzeste wäre.

Das ist zwar korrekt, aber der "Fehler" wirkt sich nicht aus, weil der Code (absichtlich!) nie die Procedure search mit einer kompletten Reihenfolge aufruft, wenn sie nicht auch die aktuell kürzeste ist. Das wird woanders in der Procedure so gesteuert (siehe den Code ganz unten beim Kommentar (B)) und der eigentlich enthaltene "Fehler" hier kann sich nie auswirken. Dennoch würde ich sicherheitshalber eine Änderung für eine verbesserte Logik vornehmen. Siehe dazu den Code ganz unten beim Kommentar (A).)

Ansonsten habe ich mittlerweile mein "mieses Gefühl" bzgl. der i-Schleife bestätigt bekommen. Sie wird tatsächlich etwas abenteuerlich eingesetzt, ist aber nicht das Hauptübel.

Das eigentliche Problem hatte ich aber schon zuvor (etwas intuitiv) vermutet:

IngoD7 hat folgendes geschrieben:

Ich weiß nicht, ob ich das richtig verstanden habe, aber eines ist sicher: Nach dem rekursiven Aufruf von search in der Procedure search steht in deinem Programm doch gar nichts mehr.

Da, wo deine Bemerkung steht (siehe bei <== HIER im Code)...

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:

  procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
[...]
              reihenfolge:=reihenfolge+inttostr(i);
              search(reihenfolge,smallest,solution);
              //jetzt passiert das Backtracking!!            //<============== HIER
            end;
  end;

... müsste eigentlich irgendwelcher Programmcode auftauchen.

Es ist jedenfalls die erste rekursive Procedure die ich sehe, die direkt hinter dem rekursiven Aufruf endet.

Auf deutsch: Es muss an der Stelle - wie ich jetzt sicher weiß - der zuletzt angefügte Ort aus der Reihenfolge entfernt werden. Siehe dazu im folgenden Code beim Kommentar (C).

Also so:

markieren

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:

  procedure search(reihenfolge:string;VAR smallest:integer;VAR solution:string);
  var i,w:integer;
  begin
    w:=sofar(reihenfolge);
    if complete(reihenfolge)=true then
      begin
        if w<smallest then 
         begin  // <===== (A) Änderung zur "logischen Sicherheit"
          smallest:=w;
          solution:=reihenfolge;
        end;
      end
    else //if complete(reihenfolge)=false
      for i:=1 to citycount do
        if (possiblynext(inttostr(i)[1],reihenfolge)) and
          ((w+ARdistances[strtoint(reihenfolge[length(reihenfolge)]),i,1])<smallest)  //<-- (B)
          then
            begin
              reihenfolge:=reihenfolge+inttostr(i);
              search(reihenfolge,smallest,solution);
              //jetzt passiert das Backtracking!!
              delete(reihenfolge,length(reihenfolge),1);  // <=== (C) WICHTIG!
            end;
  end;

Damit kommt die Sache einer ordnungsgemäßen Funktion schon sehr viel näher.

Ob das Programm jetzt tatsächlich alle möglichen "Entfernungskonstellationen" bei den Orten korrekt behandelt, weiß ich nicht zu 100%. Ich gehe aber momentan davon aus. Alle Tests bisher waren erfolgreich, soweit ich das "zu Fuß" nachvollziehen konnte.

//Nachtrag:
Damit wäre auch die mangelnde Qualität des Struktogrammes geklärt, welches den wichtigen Rückschnitt der Reihenfolge nicht erwähnt.

Ransom · Hält's aus hier Beiträge: 14

IngoD7 hat folgendes geschrieben:

Naja, solltest du entgegen dem Anschein das Interesse nicht verloren haben

Sorry, hatte noch anderen Schulkram zu tun.

Hey, IngoD7, ich bin sehr froh, dass es jetzt funktioniert

In einem Forum kann ich nicht viel mehr sagen als: Fettes Dankeschön!!!

Übrigens war deine Zeitinvestition nicht total "für die Tonne", denn du hast einem Delphi-dummen Schüler neue Möglichkeiten zur Fehlersuche gezeigt :wink:

Also nochmals danke, dass du so viel Mühe in die Lösung meines Problems investiert hast. Echt spitze, ich kann dieses Forum echt nur weiterempfehlen! user defined image

Ransom

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme