学步园

问题：某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。

以上图为例：售货员要从1开始经过2，3，4又返回1。

给我的感觉就是一个排列问题。在进行计算排列的同时要判断是否该排列有必要进行下去，因为可能在中途就可以判断这样肯定得不到我们想要的结果，此时采用回溯。

代码实现：

/*
*	售货员问题----回溯处理
*	日期:	2013-11-07 
*/
#include<iostream>
using namespace std;

#define MAX  1024

int N=4;//可以自己输入，这里我就指定了，并且在init()中设定了所有点的Cost[][];
int Cost[MAX][MAX];//记录任意两点的运费或代价
int bestCost=MAX;//记录目前最少运费或代价
int currentCost;//当前运费或代价
int current[MAX];//当前路径
int best[MAX];//记录最佳路径

void swap(int& a,int& b)
{
	int temp=a;
	a=b;
	b=temp;
}

void backtrack(int t)//其实就是一个排列问题。。。
{
	int j;
	if(t==N)//到了最后一层。。
	{
		if(Cost[current[t-1]][current[t]]+Cost[current[t]][1]+currentCost<bestCost)
		{
			bestCost=Cost[current[t-1]][current[t]]+Cost[current[t]][1]+currentCost;
			for(j=1;j<=N;j++)
			{
				best[j]=current[j];
			}
		}
	}
	
	for(j=t;j<=N;j++)//排列。。。
	{
		swap(current[t],current[j]);
		if(Cost[current[t-1]][current[t]]+currentCost<bestCost)//其实currentCost就是包括了1-->(t-1)的代价或运费
		{
			currentCost+=Cost[current[t-1]][current[t]];
			backtrack(t+1);//递归回溯
			currentCost-=Cost[current[t-1]][current[t]];
		}
		swap(current[t],current[j]);
	}
}

void init()
{
   	 Cost[1][1]=0;
	 Cost[1][2]=30;
	 Cost[1][3]=6;
	 Cost[1][4]=4;

	 Cost[2][1]=30;
	 Cost[2][2]=0;
	 Cost[2][3]=5;
	 Cost[2][4]=10;

	 Cost[3][1]=6;
	 Cost[3][2]=5;
	 Cost[3][3]=0;
	 Cost[3][4]=20;

	 Cost[4][1]=4;
	 Cost[4][2]=10;
	 Cost[4][3]=20;
	 Cost[4][4]=0;
}
void main()
{
	 init();

	 int i;
	 for(i=1;i<=N;i++)
	 {
		 current[i]=i;
	 }

	 backtrack(2);//树的第一层已经找到了，所以从第二层开始

	 cout<<"最少的运费为:"<<bestCost<<endl;
	 cout<<"最佳路径为: ";
	 for(i=1;i<=N;i++)
	 {
		 cout<<best[i]<<"->";
	 }
	 cout<<best[1]<<endl;
}