C语言使用回溯法解旅行售货员问题与图的m着色问题

概述旅行售货员问题1.问题描述：旅行售货员问题又称TSP问题，问题如下：某售货员要到若干个城市推销商品，已知各城市之间的路程（或旅费），他要选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路线（

旅行售货员问题
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.样例输入：

25 81 2 51 4 71 5 92 3 102 4 32 5 63 4 84 5 43 11 2 10

5.样例输出：

Case 1: 36Case 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 ;   }   else   {     for(int i=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]);       }     }   } } int main(voID){  int i,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(int k=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++;  }      return 0;}

图的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.样例输入：

15 8 51 21 31 42 32 42 53 44 5

5.样例输出：

Case 1: 360

6.解决方法：

#include<iostream>using namespace std;#define N 100int m,n,M,a[N][N],x[N],textNum;int static sum=0;bool ok(int k){  for(int j=1;j<=n;j++)  if(a[k][j]&&(x[j]==x[k]))  return false;  return true;}voID backtrack(int t){  if(t>n)  {    sum++;    // for(int i=1;i<=n;i++)    //cout<<x[i]<<" ";    //cout<<endl;  }  else  for(int i=1;i<=m;i++)  {    x[t]=i;    if(ok(t))    backtrack(t+1);    x[t]=0;  }}int main(){  int i,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(int k=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++;  }      return 0;}

总结

以上是内存溢出为你收集整理的C语言使用回溯法解旅行售货员问题与图的m着色问题全部内容，希望文章能够帮你解决C语言使用回溯法解旅行售货员问题与图的m着色问题所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。