โปรแกรม C++ เพื่อใช้อัลกอริทึมเพื่อนบ้านที่ใกล้ที่สุด

นี่คือโปรแกรม C++ ที่ใช้อัลกอริธึม Nearest Neighbor Algorithm ซึ่งใช้ในการนำปัญหาพนักงานขายที่เดินทางมาใช้เพื่อคำนวณต้นทุนขั้นต่ำที่จำเป็นในการเยี่ยมชมโหนดทั้งหมดโดยข้ามผ่านขอบเพียงครั้งเดียว

ฟังก์ชันที่จำเป็นและรหัสเทียม

อัลกอริทึม

Begin
   Initialize c = 0, cost = 1000;
   Initialize g[][].
   function swap() is used to swap two values x and y.
   function cal_sum() to calculate the cost which take array a[] and size of array as input.
   Initialize sum =0.
   for i = 0 to n
      compute s+= g[a[i %3]][a[(i+ 1) %3]];
   if (cost >s)
      cost = s
   function permute() is used to perform permutation:
   If there is one lement in array
      call cal_sum().
   else
      for j = i to n
         swap (a+i) with (a + j)
         cal_sum(a+1,n)
         swap (a+i) with (a + j)
End

โค้ดตัวอย่าง

#include<iostream>
using namespace std;

int c = 0, cost = 1000;
int g[3][3 ] = { {1,2,3},{4,5,8},{6,7,10}};

void swap(int *x, int *y) {
   int t;
   t = *x;
   *x = *y;
   *y = t;
}

void cal_sum(int *a, int n) {
   int i, s= 0;
   for (i = 0; i <= n; i++) {
      s+= g[a[i %3]][a[(i+ 1) %3]];
   }
   if (cost >s) {
      cost = s;
   }
}

void permute(int *a,int i,int n) {
   int j, k;
   if (i == n) {
      cal_sum (a,n);
   } else {
      for (j = i; j <= n; j++) {
         swap((a + i), (a + j));
         cal_sum(a+1,n);
         swap((a + i), (a + j));
      }
   }
}

int main() {
   int i, j;
   int a[] = {1,2,3};//take array elements
   permute(a, 0,2);
   cout << "minimum cost:" << cost << endl;
}

ผลลัพธ์

minimum cost:3