12-10.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
#define n 10
typedef int DataType;
DataType	bestc;
DataType	*bestx,a[n][n],x[n];
DataType	cc;
void Swap(DataType *a,DataType *b)
{
		DataType *t=a;
		*a=*b;
		*b=*t;
}
void tSP(int i)
{// 旅行商问题的回溯算法
	int j;
	if (i == n) {// 位于一个叶子的父节点
		// 通过增加两条边来完成旅行
		if (a[x[n-1]][x[n]]!=0&&a[x[n]][1]!=0&&
			(cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc ==0)) 
		{// 找到更优的旅行路径
			for(j = 1; j <= n; j++)
				bestx[j] = x[j];
			bestc=cc+a[x[n-1]][x[n]] + a[x[n]][1];}
		}
		else {// 尝试子树
			for (j = i; j <= n; j++)
				//能移动到子树x [ j ]吗?
				if (a[x[i-1]][x[j]] !=0&&
					(cc+a[x[i-1]][x[i]]<bestc||bestc == 0)) 
				{//能搜索该子树
					Swap(&x[i], &x[j]);
					cc += a[x[i-1]][x[i]];
					tSP(i+1);
					cc -= a[x[i-1]][x[i]];
					Swap(&x[i], &x[j]);
				}
		}
}
DataType TSP(int v[])
{// 用回溯算法解决旅行商问题
	// 返回最优旅游路径的耗费，最优路径存入v [ 1 : n ]
	//初始化
	int x[n+1],i;
	// x 是排列
	for (i = 1; i <= n; i++)
		x[i] = i;
	bestc=0;
	bestx=v; // 使用数组v来存储最优路径
	cc = 0;
	// 搜索x [ 2 : n ]的各种排列
	tSP(2);
	return bestc;
}
void main()
{
	int v[n];
	//初始化v[n],*bestx,a[n][n],x[n]
	TSP(v);
}