亲宝软件园·资讯

展开

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

Hi_Aaron 人气:0
想了解C语言使用回溯法解旅行售货员问题与图的m着色问题的相关内容吗,Hi_Aaron在本文为您仔细讲解C语言解旅行售货员与图的m着色问题的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:C语言,算法,回溯,下面大家一起来学习吧。

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

1
5 8 5
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5

5.样例输出:

Case 1: 360

6.解决方法:

#include<iostream>
using namespace std;
#define N 100
int 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,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(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;
}

加载全部内容

相关教程
猜你喜欢
用户评论