Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<stdlib.h>
- #include<conio.h>
- #include<time.h>
- #define N 20
- using namespace std;
- int *config;
- int d[N][N];
- int confper[N];
- void initConfig() {
- config = new int[N];
- for (int i = 0;i < N;i++) {
- config[i] = 0;
- }
- }
- void init() {
- initConfig();
- int *M = new int[N];
- int lungime_M = N;//lungime_M a vectorului M
- int i;//indicele de configuratie
- for (int i = 0; i < N; i++) {
- M[i] = i + 1;
- }
- i = 0;
- while (lungime_M > 0) {
- int g = rand() % lungime_M;
- config[i++] = M[g];
- for (int index = g; index < lungime_M - 1; index++) {
- M[index] = M[index + 1];//scoate elementul M[g] din lista
- }
- lungime_M--;
- }
- }
- void distanta() {
- d[1][2] = d[2][1] = 596;
- d[1][3] = d[3][1] = 550;
- d[1][4] = d[4][1] = 574;
- d[1][5] = d[5][1] = 555;
- d[1][6] = d[6][1] = 538;
- d[1][7] = d[7][1] = 394;
- d[1][8] = d[8][1] = 426;
- d[1][9] = d[9][1] = 419;
- d[1][10] = d[10][1] = 330;
- d[1][11] = d[11][1] = 282;
- d[1][12] = d[12][1] = 161;
- d[1][13] = d[13][1] = 126;
- d[1][14] = d[14][1] = 248;
- d[1][15] = d[15][1] = 436;
- d[1][16] = d[16][1] = 349;
- d[1][17] = d[17][1] = 406;
- d[1][18] = d[18][1] = 213;
- d[1][19] = d[19][1] = 278;
- d[1][20] = d[20][1] = 225;
- d[2][3] = d[3][2] = 67;
- d[2][4] = d[4][2] = 135;
- d[2][5] = d[5][2] = 250;
- d[2][6] = d[6][2] = 304;
- d[2][7] = d[7][2] = 331;
- d[2][8] = d[8][2] = 170;
- d[2][9] = d[9][2] = 216;
- d[2][10] = d[10][2] = 271;
- d[2][11] = d[11][2] = 333;
- d[2][12] = d[12][2] = 434;
- d[2][13] = d[13][2] = 485;
- d[2][14] = d[14][2] = 544;
- d[2][15] = d[15][2] = 369;
- d[2][16] = d[16][2] = 429;
- d[2][17] = d[17][2] = 463;
- d[2][18] = d[18][2] = 660;
- d[2][19] = d[19][2] = 752;
- d[2][20] = d[20][2] = 815;
- d[3][4] = d[4][3] = 183;
- d[3][5] = d[5][3] = 298;
- d[3][6] = d[6][3] = 352;
- d[3][7] = d[7][3] = 303;
- d[3][8] = d[8][3] = 146;
- d[3][9] = d[9][3] = 148;
- d[3][10] = d[10][3] = 219;
- d[3][11] = d[11][3] = 305;
- d[3][12] = d[12][3] = 388;
- d[3][13] = d[13][3] = 457;
- d[3][14] = d[14][3] = 516;
- d[3][15] = d[15][3] = 326;
- d[3][16] = d[16][3] = 387;
- d[3][17] = d[17][3] = 420;
- d[3][18] = d[18][3] = 618;
- d[3][19] = d[19][3] = 710;
- d[3][20] = d[20][3] = 768;
- d[4][5] = d[5][4] = 115;
- d[4][6] = d[6][4] = 169;
- d[4][7] = d[7][4] = 278;
- d[4][8] = d[8][4] = 147;
- d[4][9] = d[9][4] = 263;
- d[4][10] = d[10][4] = 249;
- d[4][11] = d[11][4] = 311;
- d[4][12] = d[12][4] = 412;
- d[4][13] = d[13][4] = 463;
- d[4][14] = d[14][4] = 463;
- d[4][15] = d[15][4] = 478;
- d[4][16] = d[16][4] = 444;
- d[4][17] = d[17][4] = 538;
- d[4][18] = d[18][4] = 671;
- d[4][19] = d[19][4] = 763;
- d[4][20] = d[20][4] = 792;
- d[5][6] = d[6][5] = 52;
- d[5][7] = d[7][5] = 239;
- d[5][8] = d[8][5] = 263;
- d[5][9] = d[9][5] = 378;
- d[5][10] = d[10][5] = 350;
- d[5][11] = d[11][5] = 273;
- d[5][12] = d[12][5] = 415;
- d[5][13] = d[13][5] = 429;
- d[5][14] = d[14][5] = 394;
- d[5][15] = d[15][5] = 593;
- d[5][16] = d[16][5] = 531;
- d[5][17] = d[17][5] = 646;
- d[5][18] = d[18][5] = 674;
- d[5][19] = d[19][5] = 766;
- d[5][20] = d[20][5] = 780;
- d[6][7] = d[7][6] = 217;
- d[6][8] = d[8][6] = 316;
- d[6][9] = d[9][6] = 417;
- d[6][10] = d[10][6] = 327;
- d[6][11] = d[11][6] = 256;
- d[6][12] = d[12][6] = 399;
- d[6][13] = d[13][6] = 406;
- d[6][14] = d[14][6] = 353;
- d[6][15] = d[15][6] = 575;
- d[6][16] = d[16][6] = 509;
- d[6][17] = d[17][6] = 691;
- d[6][18] = d[18][6] = 651;
- d[6][19] = d[19][6] = 743;
- d[6][20] = d[20][6] = 758;
- d[7][8] = d[8][7] = 160;
- d[7][9] = d[9][7] = 200;
- d[7][10] = d[10][7] = 116;
- d[7][11] = d[11][7] = 113;
- d[7][12] = d[12][7] = 232;
- d[7][13] = d[13][7] = 268;
- d[7][14] = d[14][7] = 293;
- d[7][15] = d[15][7] = 358;
- d[7][16] = d[16][7] = 292;
- d[7][17] = d[17][7] = 407;
- d[7][18] = d[18][7] = 490;
- d[7][19] = d[19][7] = 583;
- d[7][20] = d[20][7] = 612;
- d[8][9] = d[9][8] = 119;
- d[8][10] = d[10][8] = 101;
- d[8][11] = d[11][8] = 163;
- d[8][12] = d[12][8] = 264;
- d[8][13] = d[13][8] = 315;
- d[8][14] = d[14][8] = 374;
- d[8][15] = d[15][8] = 334;
- d[8][16] = d[16][8] = 297;
- d[8][17] = d[17][8] = 390;
- d[8][18] = d[18][8] = 523;
- d[8][19] = d[19][8] = 615;
- d[8][20] = d[20][8] = 644;
- d[9][10] = d[10][9] = 89;
- d[9][11] = d[11][9] = 200;
- d[9][12] = d[12][9] = 257;
- d[9][13] = d[13][9] = 352;
- d[9][14] = d[14][9] = 411;
- d[9][15] = d[15][9] = 214;
- d[9][16] = d[16][9] = 247;
- d[9][17] = d[17][9] = 308;
- d[9][18] = d[18][9] = 486;
- d[9][19] = d[19][9] = 578;
- d[9][20] = d[20][9] = 638;
- d[10][11] = d[11][10] = 112;
- d[10][12] = d[12][10] = 168;
- d[10][13] = d[13][10] = 262;
- d[10][14] = d[14][10] = 321;
- d[10][15] = d[15][10] = 261;
- d[10][16] = d[16][10] = 195;
- d[10][17] = d[17][10] = 310;
- d[10][18] = d[18][10] = 426;
- d[10][19] = d[19][10] = 519;
- d[10][20] = d[20][10] = 548;
- d[11][12] = d[12][11] = 142;
- d[11][13] = d[13][11] = 155;
- d[11][14] = d[14][11] = 236;
- d[11][15] = d[15][11] = 358;
- d[11][16] = d[16][11] = 289;
- d[11][17] = d[17][11] = 441;
- d[11][18] = d[18][11] = 401;
- d[11][19] = d[19][11] = 493;
- d[11][20] = d[20][11] = 507;
- d[12][13] = d[13][12] = 149;
- d[12][14] = d[14][12] = 205;
- d[12][15] = d[15][12] = 319;
- d[12][16] = d[16][12] = 228;
- d[12][17] = d[17][12] = 299;
- d[12][18] = d[18][12] = 258;
- d[12][19] = d[19][12] = 350;
- d[12][20] = d[20][12] = 380;
- d[13][14] = d[14][13] = 123;
- d[13][15] = d[15][13] = 468;
- d[13][16] = d[16][13] = 378;
- d[13][17] = d[17][13] = 448;
- d[13][18] = d[18][13] = 318;
- d[13][19] = d[19][13] = 404;
- d[13][20] = d[20][13] = 351;
- d[14][15] = d[15][14] = 524;
- d[14][16] = d[16][14] = 434;
- d[14][17] = d[17][14] = 504;
- d[14][18] = d[18][14] = 434;
- d[14][19] = d[19][14] = 504;
- d[14][20] = d[20][14] = 451;
- d[15][16] = d[16][15] = 122;
- d[15][17] = d[17][15] = 144;
- d[15][18] = d[18][15] = 341;
- d[15][19] = d[19][15] = 433;
- d[15][20] = d[20][15] = 520;
- d[16][17] = d[17][16] = 131;
- d[16][18] = d[18][16] = 254;
- d[16][19] = d[19][16] = 346;
- d[16][20] = d[20][16] = 432;
- d[17][18] = d[18][17] = 271;
- d[17][19] = d[19][17] = 364;
- d[17][20] = d[20][17] = 434;
- d[18][19] = d[19][18] = 92;
- d[18][20] = d[20][18] = 178;
- d[19][20] = d[20][19] = 124;
- }
- int Evaluare(int *c) {
- int dist_tot = 0;
- for (int i = 0;i < N - 1;i++) {
- dist_tot += d[c[i]][c[i+1]];
- dist_tot += d[c[N - 1]][c[0]];
- }
- return dist_tot;
- }
- void Afisare() {
- for (int i = 0;i < N;i++)
- cout << config[i] << " ";
- }
- int *Perturbare(int *c) {
- int x, y;
- x = rand() % N;
- y = rand() % N;
- while (x == y) {
- y = rand() % N;
- }
- int temp = c[x];
- c[x] = c[y];
- c[y] = temp;
- return c;
- }
- void HillClimbing() {
- init();
- for (int i = 0;i < N;i++) {
- confper[i] = config[i];
- }
- int nr_pasi = 0;//umarul pasilor care nu duc la o solutie mai buna
- cout << "init ";
- Afisare();
- cout << "\nevaluarea configuratiei este " << Evaluare(config);
- for (int i = 0; i <10000; i++) {
- if (nr_pasi < 20) {
- int *config1 = Perturbare(confper);
- if (Evaluare(config1) < Evaluare(config)) {
- for (int j = 0;j < N;j++) {
- config[j] = config1[j];
- }
- }
- else {
- nr_pasi++;
- }
- }
- else break;
- }
- }
- void main() {
- initConfig();
- time_t t;
- srand((unsigned)(time(&t)));
- distanta();
- init();
- Afisare();
- cout << "\nevaluarea configuratiei este " << Evaluare(config);
- HillClimbing();
- for (int i = 0;i < N;i++) {
- cout << config[i] << " ";
- }
- cout << "\nnevaluarea configuratiei este " << Evaluare(config);
- _getch();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement