kostenloser Webspace werbefrei: lima-city

in: Travelling salesman Problem mit dynamischer Programmierung

geschrieben von forall

#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;
}

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

#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;
}

in: Der längste Thread aller Welten

geschrieben von forall

in: Mambo Server

geschrieben von forall

in: Mambo Server

geschrieben von forall

in: nt-user anmelden

geschrieben von forall