API tools faq
paste
Advertisement
Guest User

hill climbing harta

a guest
Apr 26th, 2017
71
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.01 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <conio.h>
  3. #include <time.h>
  4. #include <stdlib.h>
  5.  
  6. #define N 20
  7.  
  8. using namespace std;
  9.  
  10. int config[N], config1[N];
  11. int d[N][N];
  12.  
  13. void distanta() {
  14.  
  15.     d[1][2] = d[2][1] = 596;
  16.     d[1][3] = d[3][1] = 550;
  17.     d[1][4] = d[4][1] = 574;
  18.     d[1][5] = d[5][1] = 555;
  19.     d[1][6] = d[6][1] = 538;
  20.     d[1][7] = d[7][1] = 394;
  21.     d[1][8] = d[8][1] = 426;
  22.     d[1][9] = d[9][1] = 419;
  23.     d[1][10] = d[10][1] = 330;
  24.     d[1][11] = d[11][1] = 282;
  25.     d[1][12] = d[12][1] = 161;
  26.     d[1][13] = d[13][1] = 126;
  27.     d[1][14] = d[14][1] = 248;
  28.     d[1][15] = d[15][1] = 436;
  29.     d[1][16] = d[16][1] = 349;
  30.     d[1][17] = d[17][1] = 406;
  31.     d[1][18] = d[18][1] = 213;
  32.     d[1][19] = d[19][1] = 278;
  33.     d[1][20] = d[20][1] = 225;
  34.  
  35.  
  36.     d[2][3] = d[3][2] = 67;
  37.     d[2][4] = d[4][2] = 135;
  38.     d[2][5] = d[5][2] = 250;
  39.     d[2][6] = d[6][2] = 304;
  40.     d[2][7] = d[7][2] = 331;
  41.     d[2][8] = d[8][2] = 170;
  42.     d[2][9] = d[9][2] = 216;
  43.     d[2][10] = d[10][2] = 271;
  44.     d[2][11] = d[11][2] = 333;
  45.     d[2][12] = d[12][2] = 434;
  46.     d[2][13] = d[13][2] = 485;
  47.     d[2][14] = d[14][2] = 544;
  48.     d[2][15] = d[15][2] = 369;
  49.     d[2][16] = d[16][2] = 429;
  50.     d[2][17] = d[17][2] = 463;
  51.     d[2][18] = d[18][2] = 660;
  52.     d[2][19] = d[19][2] = 752;
  53.     d[2][20] = d[20][2] = 815;
  54.  
  55.  
  56.     d[3][4] = d[4][3] = 183;
  57.     d[3][5] = d[5][3] = 298;
  58.     d[3][6] = d[6][3] = 352;
  59.     d[3][7] = d[7][3] = 303;
  60.     d[3][8] = d[8][3] = 146;
  61.     d[3][9] = d[9][3] = 148;
  62.     d[3][10] = d[10][3] = 219;
  63.     d[3][11] = d[11][3] = 305;
  64.     d[3][12] = d[12][3] = 388;
  65.     d[3][13] = d[13][3] = 457;
  66.     d[3][14] = d[14][3] = 516;
  67.     d[3][15] = d[15][3] = 326;
  68.     d[3][16] = d[16][3] = 387;
  69.     d[3][17] = d[17][3] = 420;
  70.     d[3][18] = d[18][3] = 618;
  71.     d[3][19] = d[19][3] = 710;
  72.     d[3][20] = d[20][3] = 768;
  73.  
  74.  
  75.  
  76.     d[4][5] = d[5][4] = 115;
  77.     d[4][6] = d[6][4] = 169;
  78.     d[4][7] = d[7][4] = 278;
  79.     d[4][8] = d[8][4] = 147;
  80.     d[4][9] = d[9][4] = 263;
  81.     d[4][10] = d[10][4] = 249;
  82.     d[4][11] = d[11][4] = 311;
  83.     d[4][12] = d[12][4] = 412;
  84.     d[4][13] = d[13][4] = 463;
  85.     d[4][14] = d[14][4] = 463;
  86.     d[4][15] = d[15][4] = 478;
  87.     d[4][16] = d[16][4] = 444;
  88.     d[4][17] = d[17][4] = 538;
  89.     d[4][18] = d[18][4] = 671;
  90.     d[4][19] = d[19][4] = 763;
  91.     d[4][20] = d[20][4] = 792;
  92.  
  93.     d[5][6] = d[6][5] = 52;
  94.     d[5][7] = d[7][5] = 239;
  95.     d[5][8] = d[8][5] = 263;
  96.     d[5][9] = d[9][5] = 378;
  97.     d[5][10] = d[10][5] = 350;
  98.     d[5][11] = d[11][5] = 273;
  99.     d[5][12] = d[12][5] = 415;
  100.     d[5][13] = d[13][5] = 429;
  101.     d[5][14] = d[14][5] = 394;
  102.     d[5][15] = d[15][5] = 593;
  103.     d[5][16] = d[16][5] = 531;
  104.     d[5][17] = d[17][5] = 646;
  105.     d[5][18] = d[18][5] = 674;
  106.     d[5][19] = d[19][5] = 766;
  107.     d[5][20] = d[20][5] = 780;
  108.  
  109.     d[6][7] = d[7][6] = 217;
  110.     d[6][8] = d[8][6] = 316;
  111.     d[6][9] = d[9][6] = 417;
  112.     d[6][10] = d[10][6] = 327;
  113.     d[6][11] = d[11][6] = 256;
  114.     d[6][12] = d[12][6] = 399;
  115.     d[6][13] = d[13][6] = 406;
  116.     d[6][14] = d[14][6] = 353;
  117.     d[6][15] = d[15][6] = 575;
  118.     d[6][16] = d[16][6] = 509;
  119.     d[6][17] = d[17][6] = 691;
  120.     d[6][18] = d[18][6] = 651;
  121.     d[6][19] = d[19][6] = 743;
  122.     d[6][20] = d[20][6] = 758;
  123.  
  124.  
  125.     d[7][8] = d[8][7] = 160;
  126.     d[7][9] = d[9][7] = 200;
  127.     d[7][10] = d[10][7] = 116;
  128.     d[7][11] = d[11][7] = 113;
  129.     d[7][12] = d[12][7] = 232;
  130.     d[7][13] = d[13][7] = 268;
  131.     d[7][14] = d[14][7] = 293;
  132.     d[7][15] = d[15][7] = 358;
  133.     d[7][16] = d[16][7] = 292;
  134.     d[7][17] = d[17][7] = 407;
  135.     d[7][18] = d[18][7] = 490;
  136.     d[7][19] = d[19][7] = 583;
  137.     d[7][20] = d[20][7] = 612;
  138.  
  139.  
  140.  
  141.     d[8][9] = d[9][8] = 119;
  142.     d[8][10] = d[10][8] = 101;
  143.     d[8][11] = d[11][8] = 163;
  144.     d[8][12] = d[12][8] = 264;
  145.     d[8][13] = d[13][8] = 315;
  146.     d[8][14] = d[14][8] = 374;
  147.     d[8][15] = d[15][8] = 334;
  148.     d[8][16] = d[16][8] = 297;
  149.     d[8][17] = d[17][8] = 390;
  150.     d[8][18] = d[18][8] = 523;
  151.     d[8][19] = d[19][8] = 615;
  152.     d[8][20] = d[20][8] = 644;
  153.  
  154.  
  155.  
  156.     d[9][10] = d[10][9] = 89;
  157.     d[9][11] = d[11][9] = 200;
  158.     d[9][12] = d[12][9] = 257;
  159.     d[9][13] = d[13][9] = 352;
  160.     d[9][14] = d[14][9] = 411;
  161.     d[9][15] = d[15][9] = 214;
  162.     d[9][16] = d[16][9] = 247;
  163.     d[9][17] = d[17][9] = 308;
  164.     d[9][18] = d[18][9] = 486;
  165.     d[9][19] = d[19][9] = 578;
  166.     d[9][20] = d[20][9] = 638;
  167.  
  168.  
  169.     d[10][11] = d[11][10] = 112;
  170.     d[10][12] = d[12][10] = 168;
  171.     d[10][13] = d[13][10] = 262;
  172.     d[10][14] = d[14][10] = 321;
  173.     d[10][15] = d[15][10] = 261;
  174.     d[10][16] = d[16][10] = 195;
  175.     d[10][17] = d[17][10] = 310;
  176.     d[10][18] = d[18][10] = 426;
  177.     d[10][19] = d[19][10] = 519;
  178.     d[10][20] = d[20][10] = 548;
  179.  
  180.  
  181.  
  182.     d[11][12] = d[12][11] = 142;
  183.     d[11][13] = d[13][11] = 155;
  184.     d[11][14] = d[14][11] = 236;
  185.     d[11][15] = d[15][11] = 358;
  186.     d[11][16] = d[16][11] = 289;
  187.     d[11][17] = d[17][11] = 441;
  188.     d[11][18] = d[18][11] = 401;
  189.     d[11][19] = d[19][11] = 493;
  190.     d[11][20] = d[20][11] = 507;
  191.  
  192.  
  193.  
  194.     d[12][13] = d[13][12] = 149;
  195.     d[12][14] = d[14][12] = 205;
  196.     d[12][15] = d[15][12] = 319;
  197.     d[12][16] = d[16][12] = 228;
  198.     d[12][17] = d[17][12] = 299;
  199.     d[12][18] = d[18][12] = 258;
  200.     d[12][19] = d[19][12] = 350;
  201.     d[12][20] = d[20][12] = 380;
  202.  
  203.  
  204.  
  205.     d[13][14] = d[14][13] = 123;
  206.     d[13][15] = d[15][13] = 468;
  207.     d[13][16] = d[16][13] = 378;
  208.     d[13][17] = d[17][13] = 448;
  209.     d[13][18] = d[18][13] = 318;
  210.     d[13][19] = d[19][13] = 404;
  211.     d[13][20] = d[20][13] = 351;
  212.  
  213.     d[14][15] = d[15][14] = 524;
  214.     d[14][16] = d[16][14] = 434;
  215.     d[14][17] = d[17][14] = 504;
  216.     d[14][18] = d[18][14] = 434;
  217.     d[14][19] = d[19][14] = 504;
  218.     d[14][20] = d[20][14] = 451;
  219.  
  220.     d[15][16] = d[16][15] = 122;
  221.     d[15][17] = d[17][15] = 144;
  222.     d[15][18] = d[18][15] = 341;
  223.     d[15][19] = d[19][15] = 433;
  224.     d[15][20] = d[20][15] = 520;
  225.  
  226.     d[16][17] = d[17][16] = 131;
  227.     d[16][18] = d[18][16] = 254;
  228.     d[16][19] = d[19][16] = 346;
  229.     d[16][20] = d[20][16] = 432;
  230.  
  231.  
  232.     d[17][18] = d[18][17] = 271;
  233.     d[17][19] = d[19][17] = 364;
  234.     d[17][20] = d[20][17] = 434;
  235.  
  236.     d[18][19] = d[19][18] = 92;
  237.     d[18][20] = d[20][18] = 178;
  238.  
  239.     d[19][20] = d[20][19] = 124;
  240.    
  241. }
  242.  
  243.  
  244. void init() {
  245.     int i, j, g, lungime = N, M[N];
  246.  
  247.     for (i = 0; i < N; i++)
  248.         M[i] = i + 1; // M = {1, 2, 3, ..., 8}
  249.  
  250.     i = 0; // i este pozitia in vectorul config unde completam cu numere generate aleator
  251.  
  252.     time_t t;
  253.     srand((unsigned)(time(&t)));
  254.  
  255.     while (lungime > 0) {
  256.         g = rand() % lungime;  // pozitia din vectorul M a numarului care va fi adaugat la vectorul config pe pozitia i
  257.         config[i++] = M[g];
  258.         for (j = g; j < lungime - 1; j++)
  259.             M[j] = M[j + 1];  // scoatem pe M[g] din  multimea M
  260.         lungime--;
  261.     }
  262.  
  263.  
  264. }
  265.  
  266. int evaluare(int c[N]) {
  267.     int dist_tot = 0;
  268.     int i, j;
  269.     for (i = 0;i < N - 1; i++) {
  270.         dist_tot = dist_tot + d[c[i]][c[i + 1]];
  271.     }
  272.  
  273.     dist_tot = dist_tot + d[c[N - 1]][c[0]];
  274.        
  275.     return dist_tot;
  276.            
  277. }
  278.  
  279. void perturbare(int c[N]) {
  280.     int x, y, temp;
  281.  
  282.     x = rand() % N;
  283.     y = rand() % N;
  284.  
  285.     while (x == y) {
  286.         y = rand() % N;
  287.     }
  288.  
  289.     temp = c[x];
  290.     c[x] = c[y];
  291.     c[y] = temp;
  292.  
  293. }
  294.  
  295. void hillclimbing() {
  296.     init();
  297.     for (int k = 0; k < 1000; k++) {
  298.  
  299.         for (int i = 0; i < N; i++)
  300.             config1[i] = config[i];
  301.  
  302.         perturbare(config1);
  303.  
  304.         if (evaluare(config1) < evaluare(config))
  305.             for (int i = 0; i < N; i++)
  306.                 config[i] = config1[i];
  307.  
  308.     }
  309.    
  310.        
  311.  
  312.         for (int i = 0; i < N; i++)
  313.             cout << config[i];
  314.  
  315.         cout << " Evaluarea configuratiei este: " << evaluare(config) << endl;
  316.    
  317. }
  318.  
  319. void hillclimbingrestart() {
  320.     init();
  321.     int nrit = 0;
  322.     while (evaluare(config) != 0) {
  323.         nrit = 0;
  324.         init();
  325.         while ((evaluare(config) != 0) && (nrit < 1000)) {
  326.             for (int i = 0; i < N; i++)
  327.                 config1[i] = config[i];
  328.  
  329.             perturbare(config1);
  330.             nrit++;
  331.             if (evaluare(config1) < evaluare(config))
  332.                 for (int i = 0; i < N; i++)
  333.                     config[i] = config1[i];
  334.  
  335.             for (int i = 0; i < N; i++)
  336.                 cout << config[i];
  337.  
  338.             cout << " Evaluarea configuratiei este: " << evaluare(config) << endl;
  339.         }
  340.     }
  341. }
  342.  
  343. int main() {
  344.     int i, j, g;
  345.     distanta();
  346.  
  347.     /* init();
  348.     for (i = 0; i < N; i++)
  349.     cout << config[i];
  350.  
  351.     cout << " Evaluarea configuratiei este: " << evaluare(config);
  352.  
  353.     perturbare(config);
  354.     cout << endl;
  355.     for (i = 0; i < N; i++)
  356.     cout << config[i];
  357.  
  358.     cout << " Evaluarea configuratiei este: " << evaluare(config); */
  359.  
  360.      hillclimbing();
  361.     //hillclimbingrestart();
  362.     for (i = 0; i < N; i++)
  363.         cout << config[i];
  364.  
  365.     cout << " Evaluarea configuratiei este: " << evaluare(config);
  366.  
  367.     return 0;
  368. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!