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 58 125 147 159 2310 243 256 348 454 31 1210
5.样例输出：
Case1:36 Case2:-1
6.解决方法：
//旅行售货员问题（回溯）
#include<iostream>
#defineN100
usingnamespacestd;
intn,m,w,//图的顶点数和边数
graph[N][N],//图的加权邻接矩阵
c=0,//当前费用
bestc=-1,//当前最优值
x[N],//当前解
bestx[N];//当前最优解
voidbacktrack(intk);
voidswap(int&a,int&b);
voidswap(int&a,int&b)
{
inttemp=a;
a=b;
b=temp;
}
voidbacktrack(intk)
{
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(inti=1;i<=n;i++)
{
bestx[i]=x[i];
}
}
return;
}
else
{
for(inti=k;i<=n;i++)
{
if(graph[x[k-1]][x[i]]!=-1&&(c+graph[x[k-1]][x[i]]<bestc||bestc==-1))
{
swap(x[i],x[k]);
c+=graph[x[k-1]][x[k]];
backtrack(k+1);
c-=graph[x[k-1]][x[k]];
swap(x[i],x[k]);
}
}
}
}
intmain(void)
{
inti,j,tmp=1,testNum;
cin>>testNum;
while(tmp<=testNum)
{
cin>>n>>m;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
graph[i][j]=-1;
for(intk=1;k<=m;k++)
{
cin>>i>>j>>w;
graph[i][j]=w;
graph[j][i]=w;
}
for(i=1;i<=n;i++)
{
x[i]=i;
bestx[i]=i;
}
backtrack(2);
cout<<"Case"<<tmp<<":"<<bestc<<endl;
bestc=-1;
c=0;
tmp++;
}
return0;
}
图的m着色问题
1.问题描述
给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色，求有多少种方法为图可m着色。
2.输入要求：
输入的第一个为测试样例的个数T（T<120），接下来有T个测试样例。每个测试样例的第一行是顶点数n、边数M和可用颜色数m（n<=10，M<100，m<=7），接下来M行，每行两个整数u和v，表示顶点u和v之间有一条边相连。（1<=u<v<=n）。
3.输出要求：
对应每个测试样例输出两行，第一行格式为"Case#:W"，其中'#'表示第几个测试样例（从1开始计），W为可m着色方案数。
4.样例输入：
1 585 12 13 14 23 24 25 34 45
5.样例输出：
Case1:360
6.解决方法：
#include<iostream>
usingnamespacestd;
#defineN100
intm,n,M,a[N][N],x[N],textNum;
intstaticsum=0;
boolok(intk)
{
for(intj=1;j<=n;j++)
if(a[k][j]&&(x[j]==x[k]))
returnfalse;
returntrue;
}
voidbacktrack(intt)
{
if(t>n)
{
sum++;
//for(inti=1;i<=n;i++)
//cout<<x[i]<<"";
//cout<<endl;
}
else
for(inti=1;i<=m;i++)
{
x[t]=i;
if(ok(t))
backtrack(t+1);
x[t]=0;
}
}
intmain()
{
inti,j,z=1;
cin>>textNum;//输入测试个数
while(textNum>0)
{
cin>>n;//输入顶点个数
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
a[i][j]=0;
cin>>M>>m;//输入边的个数、可用颜色数
for(intk=1;k<=M;k++)//生成图的邻接矩阵
{
cin>>i>>j;
a[i][j]=1;
a[j][i]=1;
}
/*for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
cout<<a[i][j]<<"";
cout<<endl;}*/
for(i=0;i<=n;i++)
x[i]=0;
backtrack(1);
cout<<"Case"<<z<<":"<<sum<<endl;
sum=0;
textNum--;
z++;
}
return0;
}