Contoh Program Travelling Salesman Problem Dengan Bahasa C++

Contoh Program Travelling Salesman Problem Dengan Bahasa C++

Selamat malam sobat, kali ini saya mau berbagi artikel nih masih sama kok seputar pemrograman. nah ini adalah program sederhana TSP. saya membuat program ini dengan bahasa c++ bisa juga kok dengan bahasa program yg lain.
lansung saja nih ke coding dan hasilnya.

Contoh codingnya :

#include <stdio.h>

#include <conio.h>

#include <cstdlib>

#include <ctime>

#include <iostream>

using namespace std;

int alt[100], v[100];

int stck[100];

int que[100];

int sp,head,ta,a,n,x,j,path,mod,map[100][100];

int main()

{

printf("=================================================\n");

printf("Program Tugas Akhir Analisis & Strategi Algoritma\n");

printf("=================================================\n");

  printf("Masukkan banyak kota:");

  scanf( "%d",&n);

  printf("Jarak terjauh:");

  scanf( "%d",&mod);

  srand(1);

 for (a=0   ; a<n ; a++) {

    for (j=a+1 ; j<n ; j++) {

       map[a][j]= 1 + rand() % (mod);

       map[j][a]=map[a][j];

      }

 for (j=0 ; j<n ; j++) printf("%3d ",map[a][j]);

 printf("\n");

  }

  clock_t awal = clock();

 for (a=0 ; a<n ; a++) {

    que[a]=a;

  

  }

   path=mod*n;

   stck[0]=que[0];

   alt[0]=0;

   printf("running...\n");

   sp=0;

   head=0;

   ta=n-1;

   x=0;

 

   while(1) {

      while(sp<n-1 && x<path)  {

          sp++;

          head++; if (head==n) head=0;

          stck[sp]=que[head];

          x=x+map[stck[sp]][stck[sp-1]];

          alt[sp]=n-sp-1;

       }

      if (x+map[stck[sp]][stck[0]]<path) {

        path=x+map[stck[sp]][stck[0]];

        for (a=0 ; a<n ; a++) v[a]=stck[a]+1;

      }

      while (alt[sp]==0 && sp>=0) {

        ta++; if (ta==n) ta=0;

        que[ta]=stck[sp];

        x=x-map[stck[sp]][stck[sp-1]];

        sp--;

      }

      if (sp<0) break;

      ta++; if (ta==n) ta=0;

      que[ta]=stck[sp];

      x=x-map[stck[sp]][stck[sp-1]];

      alt[sp]=alt[sp]-1;

      head++; if (head==n) head=0;

      stck[sp]=que[head];

      x=x+map[stck[sp]][stck[sp-1]];

    

  }

 

  clock_t akhir = clock();

  printf("Jalur Terbaik=%d\n",path);

  for (a=0 ; a<n ; a++) printf("%d ",v[a]);

  printf("%d\n",stck[0]+1);

  double waktu = double(akhir - awal) / CLOCKS_PER_SEC;

  cout<<"Waktu Eksekusi: "<<waktu<<endl;

 

  getch();

}

Gambar hasilnya :

Mungkin itu saja yang dapat saya bagikan semoga bermanfaat yaaa dan jangan lupa kunjungi lagi galiilmu1.blogspot.co.id  sampai jumpa lagi hehehe

Baca Juga : Program Menampilkan Hasil Output Love Menggunakan Bahasa C