Travelling salesman Problem mit dynamischer Programmierung
lima-city → Forum → Programmiersprachen → C/C++ und D
algorithmus
anzahl
art
code
distanz
einlesen
http
implementierung
jemand
matrix
menge
optimum
pause
problem
speichern
suche
system
test
url
verwendbaren implementierung
-
Wie der Titel bereits hinweist, bin ich auf der Suche nach einer verwendbaren Implementierung des Algorithmus zum Travelling salesman Problem (Problem des Handelreiseden) und dies soll mittels dynamischer Programmierung geschehn.
Ich will somit einen exakten (wenn auch Speicher- und Zeitintensiven) Algorithmus...
Leider bin ich bis jetzt erst auf Pseudecode gestossen, welcher mir nur sehr weniger weiter geholfen hat, da ich Probleme mit den Mathematischen Bezeichnungen habe und ich nach längerem Einarbeiten immer noch nicht sicher bin auf welche Art und Weise der Pseudocode zu implementieren wäre...
Quellen:
http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php (DE)
http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf (EN)
Hat jemand eine "einfache" implementierung (nicht wie z.B. die hier http://www.andrew.cmu.edu/user/neils/tsp/ )?
Oder kann mir jemand einen guten Gedankenanstoss zur Implementierung geben?
Danke im Voraus!
mfg KlasseT -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Leider gibt es im Internet wirklich viel zu wenig (exakte) Lösungen zu diesem Problem!
Ich habe es darum nun selbst implementiert und das Ganze sieht dann wie folgtaus:
#include <iostream> #include <cmath> using namespace std; int** C; // Optimums-Matrix int** d; // Distanzen zwischen den Städten int iN; // Anzahl Städte int NumberOfSetBits(int i); // Zählt die gesetzten Bits in einem Integer int main() { /** Anzahl Städte einlesen **/ scanf("%i",&iN); /** Initialisieren **/ C = new int*[iN+1]; // n Zahlen ohne 0 -> iN+1 for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0 C[i] = new int[(1<<iN)]; // 2^iN ohne 0, jedoch ist 2^iN bereits der komplette Weg (7 = 111 oder 15 = 1111); 1<<x = 2^x d = new int*[iN+1]; // n Zahlen ohne 0 for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0 d[i] = new int[iN+1]; // n Zahlen ohne 0 /** Eingabe **/ for(int i=1; i <= iN; i++) // Bis und mit iN ohne 0 for(int j=1; j <= iN; j++) // Bis und mit iN ohne 0 { scanf("%i", &d[i][j]); // Distanzen einlesen } /********************************************* * Algorithmus * *********************************************/ /** Initialisiere alle mit Mächtigkeitszahl 2 in C **/ for(int k=2; k <= iN; k++) // Ohne 0 & 1 für k, bis und mit iN { for(int c=2; c <= iN; c++) C[c][1+(1<<(k-1))] = d[1][k]; // Stadt 1 + Stadt k } /** Berechne die überigen Mächtigkeitszahlen in C **/ for(int s=3; s <= iN; s++) // Mächtigkeitszahl erhöhen, ohne 0,1,2 { for(int S=(1<<(s-2)); S < (1<<iN); S++) // Beginne bei 2^(s-2), ende bei 2^iN if(NumberOfSetBits(S) == s) // Menge mit der Mächtigkeitszahl s for(int k=2; k <= iN; k++) // Alle Städte durchgehen if((S&(1<<(k-1))) > 0) // Wenn Stadt k in Menge S vorkommt... && S >= (1<<(k-1)) { C[k][S]=9999999; for(int m=2; m <= iN; m++) // Zweite Verbindungsstadt finden { if(m == k || (S&(1<<(m-1))) == 0) // m darf nicht gleich k sein & m muss in der Menge S vorhanden sein continue; C[k][S] = min(C[m][S-(1<<(k-1))]+d[m][k], C[k][S]); // Was ist kleiner der "neue" Wert oder der Ursprungswert? break; } } } /** Optimum berechnen **/ int opt = 9999999; for(int k=2; k <= iN; k++) { opt = min(C[k][(1<<(iN))-1]+d[1][k], opt); } printf("%i\n",opt); // Pausieren //system("pause"); /** // Auskommentieren um die Optimums-Matrix auszugeben for(int i=1; i <= iN; i++) { for(int j=1; j < (1<<iN); j++) { printf("%i ",(C[i][j]<0?0:C[i][j])); } printf("\n\n"); }**/ return 0; } /** Bit-Zähler nach dem 'parallel'-Algorithmus (oder 'variable-precision SWAR'-Algorithmus) **/ int NumberOfSetBits(int i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return ((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; }
Mag wohl an der einen oder anderen Stelle nicht perfekt sein, funktioniert jedoch! :-)
Hier noch ein paar Beispiele:
3 0 12 65 12 0 5 65 5 0 4 0 12 15 5 12 0 6 3 15 6 0 18 5 3 18 0 5 0 13 34 23 3 13 0 11 14 6 34 11 0 2 18 23 14 2 0 5 3 6 18 5 0 20 0 377 223 636 190 758 307 398 963 94 706 425 614 178 55 772 199 358 500 317 377 0 344 889 667 752 42 691 200 116 202 74 43 44 275 35 391 302 4 273 223 344 0 941 942 39 737 188 618 575 816 276 323 416 846 312 932 615 754 454 636 889 941 0 938 422 948 679 961 552 162 77 420 936 643 486 54 790 916 221 190 667 942 938 0 383 972 941 181 547 459 875 430 352 576 643 321 763 218 465 758 752 39 422 383 0 131 57 736 811 231 812 220 155 763 895 717 933 720 45 307 42 737 948 972 131 0 764 151 883 689 338 810 224 124 147 660 395 507 155 398 691 188 679 941 57 764 0 889 392 85 540 49 764 859 453 891 827 253 695 963 200 618 961 181 736 151 889 0 743 632 833 650 561 532 788 587 469 363 102 94 116 575 552 547 811 883 392 743 0 347 471 25 938 596 306 921 384 612 522 706 202 816 162 459 231 689 85 632 347 0 671 971 671 456 876 189 299 154 489 425 74 276 77 875 812 338 540 833 471 671 0 128 77 57 503 44 497 876 442 614 43 323 420 430 220 810 49 650 25 971 128 0 774 706 86 222 549 725 405 178 44 416 936 352 155 224 764 561 938 671 77 774 0 317 893 683 704 830 524 55 275 846 643 576 763 124 859 532 596 456 57 706 317 0 676 490 875 998 31 772 35 312 486 643 895 147 453 788 306 876 503 86 893 676 0 676 222 238 696 199 391 932 54 321 717 660 891 587 921 189 44 222 683 490 676 0 306 397 720 358 302 615 790 763 933 395 827 469 384 299 497 549 704 875 222 306 0 264 267 500 4 754 916 218 720 507 253 363 612 154 876 725 830 998 238 397 264 0 848 317 273 454 221 465 45 155 695 102 522 489 442 405 524 31 696 720 267 848 0
Oder einen eigenen Generator:
#include <iostream> #include <cmath> #include <time.h> using namespace std; int main() { int ** test; int i; cin >> i; test = new int*[i]; for(int k=0; k<i;k++) test[k] = new int[i]; srand(time(NULL)); for(int z=0; z < i; z++) { for(int x=0; x < i; x++) { if(z == x) test[z][x] = 0; else { test[z][x] = rand() % 1000; test[x][z] = test[z][x]; } } } for(int z=0; z<i;z++) { for(int x=0; x<i; x++) cout << test[z][x] << " "; cout << endl; } system("pause"); return 0; }
Doch aufgepasst, wie bei vielen DP Lösungen wird viel Speicher benötigt, z.B. braucht es für 30 Städte bereits ~4GB an RAM! :-S
Viel Spass damit! -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage