C语言使用回溯法解旅行售货员问题与图的语言使用回溯法解旅行售货员问题与图的m着色问题着色问题
旅行售货员问题旅行售货员问题
1.问题描述:问题描述:
旅行售货员问题又称TSP问题,问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定
一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线(或总的旅费)最小。数学模型为给定一个无向图,求
遍历每一个顶点一次且仅一次的一条回路,最后回到起点的最小花费。
2.输入要求:输入要求:
输入的第一行为测试样例的个数T( T < 120 ),接下来有T个测试样例。每个测试样例的第一行是无向图的顶点数n、边数
m( n < 12,m < 100 ),接下来m行,每行三个整数u、v和w,表示顶点u和v之间有一条权值为w的边相连。( 1 <= u < v
<= n,w <= 1000 )。假设起点(驻地)为1号顶点。
3.输出要求:输出要求:
对应每个测试样例输出一行,格式为”Case #: W”,其中’#’表示第几个测试样例(从1开始计),W为TSP问题的最优解,如果
找不到可行方案则输出-1。
4.样例输入:样例输入:
2
5 8
1 2 5
1 4 7
1 5 9
2 3 10
2 4 3
2 5 6
3 4 8
4 5 4
3 1
1 2 10
5.样例输出:样例输出:
Case 1: 36
Case 2: -1
6.解决方法:解决方法:
//旅行售货员问题 (回溯)
#include<iostream>
#define N 100
using namespace std;
int n,m,w, //图的顶点数和边数
graph[N][N], //图的加权邻接矩阵
c=0, //当前费用
bestc=-1, //当前最优值
x[N], //当前解
bestx[N]; //当前最优解
void backtrack(int k);
void swap(int &a,int &b);
void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
void backtrack(int k)
{
if(k==n)
{
if( (c+graph[x[n-1]][x[n]]+graph[x[n]][1]<bestc||bestc==-1) && graph[x[n-1]][x[n]]!=-1 && graph[x[n]][1]!=-1 )
{
bestc=c+graph[x[n-1]][x[n]]+graph[x[n]][1];
for(int i=1;i<=n;i++)
{
bestx[i]=x[i];
}
}
return ;
}
评论0