快捷導(dǎo)航

C語(yǔ)言使用回溯法解旅行售貨員問(wèn)題與圖的m著色問(wèn)題

更新時(shí)間：2016年07月04日 16:13:24 作者：Hi_Aaron

回溯法即是在按條件搜索走不通的情況下退回再選擇其他路線的方法,這里我們來(lái)看C語(yǔ)言使用回溯法解旅行售貨員問(wèn)題與圖的m著色問(wèn)題的方法示例:

旅行售貨員問(wèn)題
1.問(wèn)題描述：

旅行售貨員問(wèn)題又稱TSP問(wèn)題，問(wèn)題如下：某售貨員要到若干個(gè)城市推銷商品，已知各城市之間的路程（或旅費(fèi)），他要選定一條從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市一遍最后回到駐地的路線，使總的路線（或總的旅費(fèi)）最小。數(shù)學(xué)模型為給定一個(gè)無(wú)向圖，求遍歷每一個(gè)頂點(diǎn)一次且僅一次的一條回路，最后回到起點(diǎn)的最小花費(fèi)。

2.輸入要求：

輸入的第一行為測(cè)試樣例的個(gè)數(shù)T（ T < 120 ），接下來(lái)有T個(gè)測(cè)試樣例。每個(gè)測(cè)試樣例的第一行是無(wú)向圖的頂點(diǎn)數(shù)n、邊數(shù)m（ n < 12，m < 100 ），接下來(lái)m行，每行三個(gè)整數(shù)u、v和w，表示頂點(diǎn)u和v之間有一條權(quán)值為w的邊相連。（ 1 <= u < v <= n，w <= 1000 ）。假設(shè)起點(diǎn)（駐地）為1號(hào)頂點(diǎn)。

3.輸出要求：

對(duì)應(yīng)每個(gè)測(cè)試樣例輸出一行，格式為"Case #: W"，其中'#'表示第幾個(gè)測(cè)試樣例（從1開始計(jì)），W為TSP問(wèn)題的最優(yōu)解，如果找不到可行方案則輸出-1。

4.樣例輸入：

5.樣例輸出：

Case 1: 36
Case 2: -1

6.解決方法：

//旅行售貨員問(wèn)題 （回溯）
#include<iostream> 
#define N 100 
using namespace std; 
int n,m,w,      //圖的頂點(diǎn)數(shù)和邊數(shù)
  graph[N][N],   //圖的加權(quán)鄰接矩陣
  c=0,       //當(dāng)前費(fèi)用
  bestc=-1,     //當(dāng)前最優(yōu)值
  x[N],      //當(dāng)前解
  bestx[N];    //當(dāng)前最優(yōu)解
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著色問(wèn)題
1.問(wèn)題描述
給定無(wú)向連通圖G和m種不同的顏色。用這些顏色為圖G的各頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。是否有一種著色法使G中每條邊的2個(gè)頂點(diǎn)著不同顏色，求有多少種方法為圖可m著色。

2.輸入要求：
輸入的第一個(gè)為測(cè)試樣例的個(gè)數(shù)T （ T < 120 ），接下來(lái)有T個(gè)測(cè)試樣例。每個(gè)測(cè)試樣例的第一行是頂點(diǎn)數(shù)n、邊數(shù)M和可用顏色數(shù)m（ n <= 10，M < 100，m <= 7 ），接下來(lái)M行，每行兩個(gè)整數(shù)u和v，表示頂點(diǎn)u和v之間有一條邊相連。（ 1 <= u < v <= n ）。

3.輸出要求：
對(duì)應(yīng)每個(gè)測(cè)試樣例輸出兩行，第一行格式為"Case #: W"，其中'#'表示第幾個(gè)測(cè)試樣例（從1開始計(jì)），W為可m著色方案數(shù)。

4.樣例輸入：

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;         //輸入測(cè)試個(gè)數(shù)
  while(textNum>0)
  {
    cin>>n;          //輸入頂點(diǎn)個(gè)數(shù)
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    a[i][j]=0;
    cin>>M>>m;         //輸入邊的個(gè)數(shù)、可用顏色數(shù)
    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;
}

您可能感興趣的文章: