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 ;
  }
  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;
}
(0)

相关推荐

  • C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • C++实现八皇后问题的方法

    本文实例展示了C++实现八皇后问题的方法,是数据结构与算法中非常经典的一个算法.分享给大家供大家参考之用.具体方法如下: 一般在八皇后问题中,我们要求解的是一个8*8的国际象棋棋盘中,放下8个皇后且互相不能攻击的排列总数.皇后的攻击范围为整行,整列,以及其斜对角线. 由于皇后的攻击范围特性,注定我们每行只能放下一个皇后,于是我们要做的只是逐行放下皇后.八皇后问题是回溯法的典型问题.这里我们用的方法很简单: 从第一行开始逐个检索安全位置摆放皇后,一旦有安全位置则考虑下一行的安全位置.如果发现某行没

  • 采用C++实现区间图着色问题(贪心算法)实例详解

    本文所述算法即假设要用很多个教室对一组活动进行调度.我们希望使用尽可能少的教室来调度所有活动.采用C++的贪心算法,来确定哪一个活动使用哪一间教室. 对于这个问题也常被称为区间图着色问题,即相容的活动着同色,不相容的着不同颜色,使得所用颜色数最少. 具体实现代码如下: //贪心算法 #include "stdafx.h" #include<iostream> #define N 100 using namespace std; struct Activity { int n

  • 基于C++的农夫过河问题算法设计与实现方法

    本文实例讲述了基于C++的农夫过河问题算法设计与实现方法.分享给大家供大家参考,具体如下: 问题描述: 一个农夫带着-只狼.一只羊和-棵白菜,身处河的南岸.他要把这些东西全部运到北岸.他面前只有一条小船,船只能容下他和-件物品,另外只有农夫才能撑船.如果农夫在场,则狼不能吃羊,羊不能吃白菜,否则狼会吃羊,羊会吃白菜,所以农夫不能留下羊和白菜自己离开,也不能留下狼和羊自己离开,而狼不吃白菜.请求出农夫将所有的东西运过河的方案. 实现上述求解的搜索过程可以采用两种不同的策略:一种广度优先搜索,另一种

  • C++回溯法实例分析

    本文实例讲述了C++的回溯法,分享给大家供大家参考之用.具体方法分析如下: 一般来说,回溯法是一种枚举状态空间中所有可能状态的系统方法,它是一个一般性的算法框架. 解向量a=(a1, a2, ..., an),其中每个元素ai取自一个有限序列集Si,这样的解向量可以表示一个排列,其中ai是排列中的第i个元素,也可以表示子集S,其中ai为真当且仅当全集中的第i个元素在S中:甚至可以表示游戏的行动序列或者图中的路径. 在回溯法的每一步,我们从一个给定的部分解a={a1, a2, ..., ak}开始

  • C++三色球问题描述与算法分析

    本文实例讲述了C++三色球问题.分享给大家供大家参考,具体如下: /* * 作 者:刘同宾 * 完成日期:2012 年 11 月 15 日 * 版 本 号:v1.0 * * 输入描述: * 问题描述:三色球问题:若一个口袋中放有12个球,其中有3个红的.3个白的和6个黒的,问从中任取8个共有多少种不同的颜色搭配? * 提示: 设任取的红球个数为i,白球个数为j,则黒球个数为8-i-j,根据题意红球和白球个数的取值范围是0~3, * 在红球和白球个数确定的条件下,黒球个数取值应为8-i-j<=6.

  • 八皇后问题的相关C++代码解答示例

    八皇后问题即指在一个8*8的棋盘上放置8个皇后,不允许任何两个皇后在棋盘的同一行.同一列和同一对角线上.关键字:递归.上溯.通用技巧: 经观察发现,对8 x 8的二维数组上的某点a[i][j](0<=i,j<=7) 其主对角线(即左上至右下)上的每个点的i-j+7的值(范围在(0,14))均相等: 其从对角线(即右上至左下)上的每个点的i+j的值(范围在(0,14))均相等: 且每个主对角线之间的i-j+7的值均不同,每个从对角线之间的i-j+7的值亦不同: 如a[3][4]: 主:3-4+7

  • c++递归实现n皇后问题代码(八皇后问题)

    还是先来看看最基础的8皇后问题: 在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 扩展到N皇后问题是一样的.一看,似乎要用到二维数组.其实不需要.一维数组就能判断,比如Arr[i],就可以表示一个元素位于第i行第Arr[i]列--应用广泛的小技巧.而且在这里我们不用考虑去存储整个矩阵,如果Arr[i]存在,那么我们在打印的时候,打印到皇后位置的时候输出1,非皇后位输出0即可. 这种思路的实现方式网上大把,包括前面提到的那

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

    旅行售货员问题 1.问题描述: 旅行售货员问题又称TSP问题,问题如下:某售货员要到若干个城市推销商品,已知各城市之间的路程(或旅费),他要选定一条从驻地出发,经过每个城市一遍最后回到驻地的路线,使总的路线(或总的旅费)最小.数学模型为给定一个无向图,求遍历每一个顶点一次且仅一次的一条回路,最后回到起点的最小花费. 2.输入要求: 输入的第一行为测试样例的个数T( T < 120 ),接下来有T个测试样例.每个测试样例的第一行是无向图的顶点数n.边数m( n < 12,m < 100 )

  • C语言回溯法解八皇后问题(八皇后算法)

    八皇后问题(N皇后问题)的回溯法求解 一.问题描述 在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互攻击,求出所有的布棋方法,并推广到N皇后情况. 二.参考资料 啥文字都不用看,B站上有个非常详细的动画视频解说,上链接!!! Click Here! 三.源代码 #include<iostream> #include<vector> #include<string> using namespace std; void put_queen(int x, int

  • javascript递归回溯法解八皇后问题

    下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了. function NQueens(order) { if (order < 4) { console.log('N Queens problem apply for order bigger than 3 ! '); return; } var nQueens = []; var backTracking = false; rowLoop: for (var row=0; row<order; row++) { //若出现ro

  • Python基于回溯法子集树模板解决m着色问题示例

    本文实例讲述了Python基于回溯法子集树模板解决m着色问题.分享给大家供大家参考,具体如下: 问题 图的m-着色判定问题 给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色,是否有一种着色法使G中任意相邻的2个顶点着不同颜色? 图的m-着色优化问题 若一个图最少需要m种颜色才能使图中任意相邻的2个顶点着不同颜色,则称这个数m为该图的色数.求一个图的最小色数m的问题称为m-着色优化问题. 分析 解的长度是固定的,n.若x为本问题的一个解,则x[i]表示第i个节点的

  • 教你怎么用Java回溯算法解数独

    一.题干 输入一个9*9二维数组表示数独,已经填入的数字用1-9表示,待填入的数字用0表示,试写一个算法解出数独并输出. 二.思路 容易想到回溯法,即以人的思维的解数独,遍历数组,如果是空白就从1-9依次选一个数判断本行.列.3*3宫格内是否有重复,如果有就进行下一个数字的选择:如果该数暂时满足条件,那么进行下一个格子的选择,递归的终止条件是遍历完所有格子. 三.代码分段演示 输入数组 Scanner sc = new Scanner(System.in); int[][] board = ne

  • PHP实现基于回溯法求解迷宫问题的方法详解

    本文实例讲述了PHP实现基于回溯法求解迷宫问题的方法.分享给大家供大家参考,具体如下: 引言 最近在leetcode上看了些算法题,有些看着很简单的很常用的东西,竟然一下子想不出来怎么求解,比如说:实现sqrt函数,求数组的排列.如果高数学的不好,这些看似简单的问题,第一次碰到也会感觉很难求解,当然了,今天要说的是这样一个问题,求解迷宫的所有解,这个问题的求解用到了回溯法的思想,不了解这个思想的话,很多稍微复杂点的问题都很难解了. 问题描述 这个问题是在实在瞎逛的时候碰到的,具体哪里记不太清了.

  • 算法详解之回溯法具体实现

    理论辅助: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法.回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试.用回溯算法解决问题的一般步骤为: 1.定义一个解空间,它包含问题的解. 2.利用适于搜索的方法组织解空间. 3.利用深度优先法搜索解空间. 4.利用限界函数避免移动到不可能产生解的子空间. 问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性. 还是那个基调,不喜欢纯理论的东西,喜欢使用例子来讲诉理论,在算法系列总结:动态规划(

  • C语言八皇后问题解决方法示例【暴力法与回溯法】

    本文实例讲述了C语言八皇后问题解决方法.分享给大家供大家参考,具体如下: 1.概述: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上. 2.暴力法求解: #include<cstdio> #include<cmath> const int maxn=11; int count=0; //P为当前排列,hashTable记录整数x是否已经在

  • python 回溯法模板详解

    什么是回溯法 回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 无重复元素全排列问题 给定一个所有元素都不同的list,要求返回list元素的全排列. 设n = len(list),那么这个问题可以考虑为n叉树,对这个树进行dfs,这个问题里的回溯点就是深度(也就是templist的长度)为n时,回

  • Go语言基础结构体用法及示例详解

    目录 概述 语法 结构体定义的三种形式 第一种[基本的实例化] 第二种[指针类型的结构体] 第三种[取结构体的地址实例化,通过&的操作] 初始化结构体 键值对初始化结构体 值列表填充结构体 匿名结构体 访问结构体成员 结构体作为函数参数 结构体指针 添加结构体方法 总结 示例 概述 结构体是由一系列具有相同类型或不同类型的数据构成的数据集合 语法 定义结构体[标识自定义结构体的名称,在同一个包内不能重复] type 结构名 struct { 字段1: 字段1的值, 字段2: 字段2的值, ...

随机推荐