{"id":258,"date":"2010-09-29T16:35:09","date_gmt":"2010-09-29T15:35:09","guid":{"rendered":"http:\/\/blog.my-gate.net\/2010\/09\/travelling-salesman-problem\/"},"modified":"2010-09-29T16:35:09","modified_gmt":"2010-09-29T15:35:09","slug":"travelling-salesman-problem","status":"publish","type":"post","link":"https:\/\/duerrenberger.dev\/journal\/2010\/09\/29\/travelling-salesman-problem\/","title":{"rendered":"Travelling Salesman Problem"},"content":{"rendered":"

An der Schule belege ich das Wahlkursfach Informatik. K\u00fcrzlich w\u00e4hlte\/bekam ich den Auftrag einen Vortrag \u00fcber einen Algorithmus f\u00fcr das \u201cTravelling Salesman Problem<\/a>\u201d oder auf Deutsch \u201cProblem des Handlungsreisenden<\/a>\u201d vorzustellen. Doch ich konnte nicht einfach einen \u201cnormalen\u201d Brute-Force<\/a> Algorithmus w\u00e4hlen sondern musste das Problem mit Hilfe Dynamischer Programmierung<\/a> l\u00f6sen, was die Aufgabe um einiges erschwerte. Denn als bald ich mich dann hinter das Problem machte, musste ich feststellen, dass ich das Dynamische Programmieren immer noch nicht wirklich beherrschte und auch kein fertiger Algorithmus ausser in Pseudocode im Internet zu finden ist.<\/p>\n

<\/p>\n

Ich versuchte dann den folgenden Pseudocode zu interpretieren:<\/p>\n

function algorithm TSP(G, n)\n for k := 2 to n do\n  C({1, k}, k) := dk,1<\/span>\n end for\n for s = 3 to n do\n  for all S \u2286 {1, 2, . . . , n}||S|| = s do\n   for all k \u2208 S do\n    {C(S, k) = minm\u2260k,m\u2208S<\/span>[C(S - {k},m) + dm,k<\/span>]}\n   end for\n  end for\n end for\n opt := mink\u22601<\/span>[C({1, 2, 3, . . . , n}, k) + d1,k<\/span>\n return (opt)\nend<\/pre>\n
Nach langem herum studieren kontaktierte ich dann verschiedene Personen und herhielt nach l\u00e4ngere Pause zur grossen \u00dcberraschung eine Antwort, welche mich einen Schritt n\u00e4her zur L\u00f6sung brachte.
\n  
Doch die Knacknuss konnte ich dann erst mit der Hilfe eines guten Freundes<\/a> l\u00f6sen. Denn bis anhin hatte ich grosse Probleme zu verstehen wie Funktion\/Variable \u201cC\u201d aus dem Quellcode zu implementieren w\u00e4re und genau diesen Punkt bekam ich erkl\u00e4rt. <\/p>\n
Obwohl mir nun eigentlich ziemlich klar war, wie der Algorithmus funktioniert, verwendet ich trotzdem noch ein paar Stunden f\u00fcr die Implementierung, welche sich dann beim \u201cKorrekturlesen\u201d meines Kollegen auch als teilweise fehlerhaft herausstellte. <\/p>\n
Im Endeffekt muss ich jedoch zugeben, dass sich die Arbeit l\u00e4ngstens gelohnt hat! Und da ich wie Anfangs beschrieben keine brauchbare Implementierung gefunden hatte, m\u00f6chte ich dies nun \u00e4ndern.<\/p>\n
#include <iostream>\n#include <cmath>\n\n#define INF 9999999\n\nusing namespace std;\n\nint** C; \/\/ Optimums-Matrix\nint** d; \/\/ Distanzen zwischen den St\u00e4dten\nint iN;  \/\/ Anzahl St\u00e4dte\n\nint NumberOfSetBits(int i); \/\/ Z\u00e4hlt die gesetzten Bits in einem Integer\n\nint main()\n{\n   \/** Anzahl St\u00e4dte einlesen **\/\n   scanf("%i",&iN);\n\n   \/** Initialisieren **\/\n   C = new int*[iN+1];         \/\/ n Zahlen ohne 0 -> iN+1\n   for(int i=1; i <= iN; i++)  \/\/ Bis und mit iN ohne 0\n      C[i] = new int[(1<<iN)]; \/\/ 2^iN ohne 0\n\n   d = new int*[iN+1];        \/\/ n Zahlen ohne 0\n   for(int i=1; i <= iN; i++) \/\/ Bis und mit iN ohne 0\n      d[i] = new int[iN+1];   \/\/ n Zahlen ohne 0\n\n   \/** Eingabe **\/\n   for(int i=1; i <= iN; i++)    \/\/ Bis und mit iN ohne 0\n      for(int j=1; j <= iN; j++) \/\/ Bis und mit iN ohne 0\n      {\n         scanf("%i", &d[i][j]);   \/\/ Distanzen einlesen\n      }\n\n   \/*********************************************\n    *                Algorithmus                *\n    *********************************************\/\n\n   \/** Initialisiere alle mit M\u00e4chtigkeitszahl 2 in C **\/\n   for(int k=2; k <= iN; k++) \/\/ Ohne 0 & 1 f\u00fcr k, bis und mit iN\n   {\n      for(int c=2; c <= iN; c++)\n         C[c][1+(1<<(k-1))] = d[1][k]; \/\/ Stadt 1 + Stadt k\n   }\n\n   \/** Berechne die \u00fcberigen M\u00e4chtigkeitszahlen in C **\/\n   for(int s=3; s <= iN; s++) \/\/ M\u00e4chtigkeitszahl erh\u00f6hen, ohne 0,1,2\n   {\n      \/\/ Beginne bei 2^(s-2), ende bei 2^iN\n      for(int S=(1<<(s-2)); S < (1<<iN); S++)\n         \/\/ Menge mit der M\u00e4chtigkeitszahl s\n         if(NumberOfSetBits(S) == s)\n            \/\/ Alle St\u00e4dte durchgehen\n            for(int k=2; k <= iN; k++)\n               \/\/ Wenn Stadt k in Menge S vorkommt... && S >= (1<<(k-1))\n               if((S&(1<<(k-1))) > 0)\n               {\n                  C[k][S] = INF;\n                  for(int m=2; m <= iN; m++) \/\/ Zweite Verbindungsstadt finden\n                  {\n                     \/\/ m darf nicht gleich k sein & m muss in der Menge S vorhanden sein\n                     if(m == k || (S&(1<<(m-1))) == 0)\n                        continue;\n                      \/\/ Was ist kleiner der "neue" Wert oder der Ursprungswert?\n                      C[k][S] = min(C[m][S-(1<<(k-1))]+d[m][k], C[k][S]);\n                      break;\n                  }\n               }\n   }\n\n   \/** Optimum berechnen **\/\n   int opt = INF;\n   for(int k=2; k <= iN; k++)\n   {\n      opt = min(C[k][(1<<(iN))-1]+d[1][k], opt);\n   }\n\n   printf("%in",opt);\n\n   \/\/ Pausieren\n   \/\/system("pause");\n\n   \/\/ Auskommentieren um die Optimums-Matrix auszugeben\n   \/*for(int i=1; i <= iN; i++)\n   {\n      for(int j=1; j < (1<<iN); j++)\n      {\n         printf("%i ",(C[i][j]<0?0:C[i][j]));\n      }\n      printf("nn");\n   }*\/\n\n   return 0;\n}\n\n\/** Bit-Z\u00e4hler nach dem 'parallel'\/'variable-precision SWAR'-Algorithmus **\/\nint NumberOfSetBits(int i)\n{\n    i = i - ((i >> 1) & 0x55555555);\n    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);\n    return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;\n}<\/pre>\n
Der Quellcode enth\u00e4lt bereits recht viele Kommentare und trotzdem k\u00f6nnte man dar\u00fcber noch viel erkl\u00e4ren. Ich m\u00f6chte mich jedoch nur auf ein paar Dinge beschr\u00e4nken.<\/p>\n
Um den Algorithmus zu verstehen ist es notwendig zu wissen was genau \u201cC\u201d ist. Es gibt verschiedene Arten \u201cC\u201d zu implementieren doch die wohl effizienteste ist wohl ein zweidimensionales Array. Das spezielle daran ist nun, dass der erste Index normal von 1 bis n geht und damit angibt in welcher Stadt die Rundreise aufh\u00f6ren soll bevor man zur ersten Stadt zur\u00fcckkehrt, der zweite Index jedoch einem Bitset<\/a> entspricht. Jedes einzelne Bit des Integer entspricht einer Stadt beginnend auf der rechten Seite mit Stadt 1. Der Algorithmus untersucht dann anhand der gesetzten Bits, welche St\u00e4dte f\u00fcr die gegeben Indizes gesucht werden. <\/p>\n
An der Position C[4][1011] w\u00fcrde dann also der k\u00fcrzeste Weg gespeichert werden, welcher bei der Stadt 1 beginnt, durch Stadt 2 geht und in Stadt 4 endet. Dezimal gesehen w\u00e4re der Zugriff dann nat\u00fcrlich C[4][11], da (1011)2 = (11)10 gilt. C[3][1111] entspr\u00e4che dann dem k\u00fcrzesten Weg von 1 \u00fcber 2 und 4 bis zur Stadt 3, usw.<\/p>\n
Da wir es hier mit einem Bitset aller St\u00e4dte zutun haben, wird auch schnell die Schw\u00e4che des Algorithmus klar, denn das zweidimensional Array braucht einen Speicher von n*2^n, was bei 30 St\u00e4dten bereits 4GB an Speicher entspricht\u2026<\/p>\n
Wenn man den Aufbau betrachtet kann man drei Abschnitte erkennen:<\/p>\n
    \n
  1. Initialisierung & Eingabe:<\/strong> Zu Beginn wird die Arrays (d = Distanzen & c) initialisiert und d wird mit den Eingaben gef\u00fcllt.<\/li>\n
  2. Auff\u00fcllen der Tabelle:<\/strong> Dann wir die Tabelle von Vorne nach Hinten mit den optimalen Wegen f\u00fcr die gegebenen Indizes aufgef\u00fcllt.<\/li>\n
  3. Optimums Berechnung & Ausgabe:<\/strong> Zum Schluss wird dann noch geschaut, welches der k\u00fcrzstes Weg ist, in dem zu alle letzten Werte von c die Distanz, von der ersten Stadt bis zur letzten Stadt, welche durch den ersten Index angegeben wird, dazu addiert wird. Das Optimum wird dann ausgegeben.<\/li>\n<\/ol>\n
    Was der Algorithmus nun nicht abdeckt, ist die Rekonstruktion der k\u00fcrzesten Rundreise, dies ist jedoch wieder ein einfacheres Problem, welches ich vielleicht sp\u00e4ter einmal noch l\u00f6sen werde.<\/p>\n
    Die PowerPoint Pr\u00e4sentation meines Vortrages mit dem Algorithmus, einem Zufallsgenerator f\u00fcr Probleme und Beispiel Eingaben k\u00f6nnte ihr HIER<\/a> herunterladen!<\/p>\n
    Viel Spass damit! \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":"
    An der Schule belege ich das Wahlkursfach Informatik. K\u00fcrzlich w\u00e4hlte\/bekam ich den Auftrag einen Vortrag \u00fcber einen Algorithmus f\u00fcr das \u201cTravelling Salesman Problem\u201d oder auf Deutsch \u201cProblem des Handlungsreisenden\u201d vorzustellen. Doch ich konnte nicht einfach einen \u201cnormalen\u201d Brute-Force Algorithmus w\u00e4hlen sondern musste das Problem mit Hilfe Dynamischer Programmierung l\u00f6sen, was die Aufgabe um einiges erschwerte. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,5,10,11,14],"tags":[68,102,107,270,271,373,374],"class_list":["post-258","post","type-post","status-publish","format-standard","hentry","category-pc","category-linux","category-rl","category-school","category-windows","tag-c","tag-dp","tag-dynamic-programming","tag-np","tag-np-complete","tag-travelling-salesman-problem","tag-tsp"],"_links":{"self":[{"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/posts\/258","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/comments?post=258"}],"version-history":[{"count":0,"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/posts\/258\/revisions"}],"wp:attachment":[{"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/media?parent=258"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/categories?post=258"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/duerrenberger.dev\/journal\/wp-json\/wp\/v2\/tags?post=258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}