实现最近邻居算法的C ++程序
这是一个实现最近邻居算法的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 << "最低费用:" << cost << endl; }
输出结果
最低费用:3