使用最近邻算法实现旅行商问题的 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 element 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输出结果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 << "最低成本：" << cost << endl; }
Comparing str1 and str2 using ==, Res: 0 Comparing str1 and str3 using ==, Res: 1 Comparing str1 and str2 using compare(), Res: -1024 Comparing str1 and str3 using compare(), Res: 0