TSP-旅行商问题

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int num = 0;

int map[4][4] = {0,3,6,7,

			    5,0,2,3,

			    6,4,0,2,

		    3,7,5,0

		    };

vector<int> s;

void run(int x,int pre,int sum,int pass[5])

{

   int i,pass_flag = 1;

    //初始化副本

    int pass2[5];

    for(i = 0;i < 5;i++)

    {

        pass2[i] = pass[i];

        //cout << pass2[i] << endl;

    }

    //当前城市做上标记

    pass2[x] = map[pre][x];

//设计出口  pass中的数据都不是-1  说明到过4个城市

for(i = 0;i < 4;i++)

{

	if(pass2[i] == -1)

	{

		pass_flag = 0;

		break;

	}

}

if( pass_flag )

{

	//sum + 从最后一座城市返回起始城市

	sum += map[x][0];

	//将整个路程存放在向量s中

	s.push_back(sum);

	pass2[4] =  map[x][0];

	//输出路线

	cout << "路程方案" << ++num << endl;

	for(i = 1;i < 5;i++)

	{

		cout << pass2[i] << "\t" ;

	}

	cout << endl;

}

else

{

	//加上从上一个城市到达本城市需要的路程

	//sum += map[pre][x];

	for( i = 0;i < 4;i++ )

	{

		//判断下一个城市是否已经到达过

		if(pass2[i] == -1)

		{

			//没有达到过 便进行递归循环

			run(i,x,sum+map[x][i],pass2);

			//pass2[i] = 1;

		 }

	    }

    }

}

int main()

{

int x = 0;

int y = 0;

int pass[5] = {-1,-1,-1,-1,-1};

//当前所在城市 走过路程 已经走过的城市

run(x,x,0,pass);

sort(s.begin(),s.end());

cout << "最长：" << *(s.end()-1) << endl;

cout << "最短：" << *s.begin() << endl;

return 0;

}
巴特西

TSP-旅行商问题

最新文章

热门文章
