सी ++ प्रोग्राम निकटतम पड़ोसी एल्गोरिदम को लागू करने के लिए

यह निकटतम नेबर एल्गोरिथम को लागू करने के लिए एक C++ प्रोग्राम है, जिसका उपयोग ट्रैवलिंग सेल्समैन की समस्या को लागू करने के लिए किया जाता है, ताकि केवल एक बार किनारों को पार करके सभी नोड्स पर जाने के लिए आवश्यक न्यूनतम लागत की गणना की जा सके।

आवश्यक कार्य और छद्म कोड

एल्गोरिदम

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