实现最近邻居算法的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