यह नियरेस्ट नेबर एल्गोरिदम को लागू करने के लिए एक C++ प्रोग्राम है जिसका उपयोग ट्रैवलिंग सेल्समैन प्रॉब्लम को लागू करने के लिए किया जाता है ताकि सभी नोड्स को विजिट करने के लिए आवश्यक न्यूनतम लागत की गणना की जा सके, एजेस को केवल एक बार पार करके।
आवश्यक फंक्शन्स और स्यूडोकोड्स
एल्गोरिदम
Begin c = 0, cost = 1000 इनिशियलाइज़ करें; g[][] इनिशियलाइज़ करें। function swap() दो मानों x और y को स्वैप करने के लिए उपयोग किया जाता है। function cal_sum() लागत की गणना करने के लिए जो ऐरे a[] और ऐरे के आकार को इनपुट के रूप में लेता है। sum =0 इनिशियलाइज़ करें। for i = 0 to n s+= g[a[i %3]][a[(i+ 1) %3]] की गणना करें; if (cost >s) cost = s function permute() परम्यूटेशन करने के लिए उपयोग किया जाता है: यदि ऐरे में एक एलिमेंट है cal_sum() कॉल करें। अन्यथा 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};//ऐरे एलिमेंट्स लें permute(a, 0,2); cout << "minimum cost:" << cost << endl; }आउटपुट
minimum cost:3
