图的m着色问题回溯法

图的m着色问题

1．问题描述

给定无向量图G顶点和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G图中每条边的两个顶点着不同的颜色。这个问题是图的m 可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色问题。2．算法设计

一般连通图的可着色法问题并不仅限于平面图。给定图G=（V，E）和m种颜色，果这个图不是m可着色，给出否定回答，如果这个图是m的可着色的，找出所有不同的着色法。

下面根据回朔法的递归描述框架backtrack设计图的m着色算法。用图的邻接矩阵a表示无向量连通图G=（V，E）。若（i，j）属于图G=（V，E）的边集E，则a[i][j]=1，否则a[i][j]=0。整数1，2，…，m用来表示m种不同颜色。顶点i所有颜色用x[i]表示，数组x[1：n]是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第I （1<=i<=n）层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。

在算法backtrack中，当i>n时，算法搜索至叶结点，得到新的m着色方案，当前找到的m着色方案数sum增1。

当I

3.图的m着色的回朔算法的程序:

/*********************************

*程序名：图的m着色法

*

* 版本：V J++6.0*

*开发日期：2005.10.25

*

*简要说明：此程序实现给定无向量图顶点和m种不同的颜色。用这些颜色为图的各顶点着色，每个顶点着一种颜色，

*

* 并使图中每条边的两个顶点着色不同。求有多少个图色的方法？

***********************************/

import java.io.*;//引入java.io包中的所有类

/*******************************************

*函数名:Class1

*

*传入值: 顶点数n，颜色数m

*

*输出值: 当前解x，着色方案sum

*

*简要说明:定义主类和输入输出，并调用定义类Coloring

*******************************************/

public class Class1//定义主类，并调用定义类Coloring

{

public static void main( String args[] )

{

Coloring myColor = new Coloring(3,3);//为Coloring类创建一个新对象

System.out.println( "sum=" + myColor.mColoring(3) );//输出着色方案最后结果

InputStreamReader in;//使运行结果的显示暂停

BufferedReader reader;

in = new InputStreamReader(System.in);

reader = new BufferedReader(in);

String s = "";

try

{

s = reader.readLine();

}

catch( IOException e)

{

System.out.println();

System.exit(0);

}

System.out.println("The End!");

}

}

/*******************************************

*函数名:Coloring

*

*传入值: 当前解x，着色方案sum

*

*输出值:当前解x，着色方案sum

*

*简要说明:图的可着色方法的回朔算法

*******************************************/

class Coloring//定义类，表示图的m着色问题

{

int n,m;//图的顶点数，可用颜色数

boolean[][] a;//图的邻接矩阵

int[] x;//当前解

long sum;//当前可找到的m着色方案数

Coloring(int newn,int newm)//定义构造函数，为对象的各属性赋初值{

n = newn;

m = newm;

sum = 0;

x = new int[n+5];

a = new boolean[n+5][m+5];

}

public long mColoring(int mm)//显示每次搜索后总搜索结果

{

m = mm;

sum=0;

backtrack(1);

return sum;

}

public void backtrack(int t)//对解空间树进行搜索

{

if ( t > n )//搜索解空间树至叶节点

{

sum++;

for ( int i=1; i <= m; i++ )

{

System.out.print(x[i]+"->");

}

System.out.println();

}

else//搜索解空间树的内结点

{

for ( int i=1; i <= m; i++ )

{

x[t]=i;//保存填充的颜色

if ( ok(t) )

{

backtrack(t+1);

}

}

}

}

private boolean ok( int k )//检查颜色可用性

{

for ( int j=1; j <= n; j++ )

{

if ( a[k][j] && (x[j]==x[k]) )

{

return false;

}

else

{

;

}

}

return true;

}

}

4.比对程序

5.算法效率

图的m可着色回朔法的计算时间上界可以通过解空间树中内结点个数估计. 图的可着色问

n-1

题的解空间数中内结点个数是∑mi. 对于每一个内结点,在最坏情况下,用方法ok检查当前

t=0

扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn). 因此,回朔法总的时间耗费是

n-1

∑mi (mn)=mn(m^-1)/(m-1)=O(nm^)

t=0

回溯法论文-回溯法的分析与应用

沈阳理工大学算法实践与创新论文

摘要 对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。 回溯法是一种常用的重要的基本设计方法。它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。圆排列描述的是在给定n个大小不等的圆 C1,C2,…,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的 K值。符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。 在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。 关键词: 回溯法图的着色问题符号三角形问题图排列问 题

目录 第1章引言 (1) 第2章回溯法的背景 (2) 第3章图的着色问题 (4) 3.1 问题描述 (4) 3.2 四色猜想 (4) 3.3 算法设计 (5) 3.4 源代码 (6) 3.5 运行结果图 (10) 第4章符号三角形问题 (11) 4.1 问题描述 (11) 4.2 算法设计 (11) 4.3 源代码 (12) 4.4 运行结果图 (16) 第5章圆的排列问题 (17) 5.1 问题描述 (17) 5.2 问题分析 (17) 5.3 源代码 (18) 5.4 运行结果图 (22) 结论 (23) 参考文献 (24)

图着色

算法设计课程设计 题目图着色问题 姓名学号 专业年级 指导教师职称 2014年 12月 4日

图的m着色问题 1 摘要 (3) 2 图的着色问题 (4) 2.1 图的着色问题的来源 (4) 2.2 图的着色问题的描述 (4) 3算法的基本思想 (4) 3.1 求极小覆盖法----布尔代数法 (4) 3.2 穷举法－Welch Powell着色法 (4) 3.3 回溯法 (4) 3.4 贪心法 (4) 3.5 蚁群算法 (5) 4算法步骤 (5) 4.1 求极小覆盖法----布尔代数法 (4) 4.2 穷举法－Welch Powell着色法 (4) 4.3 回溯法 (4) 4.4 贪心法 (4) 4.5 蚁群法 (4) 5 理论分析（复杂度比较）、实验性能比较 (7) 5.1 复杂度分析 (4) 5.2 实验性能比较 (4) 6 心得体会 (8) 7参考文献 (8) 8 附录 (8)

摘要 图论是近年来发展迅速而又应用广泛的一门新兴学科，已广泛应用于运筹学、网络理论、信息论、控制论、博奕论以及计算机科学等各个领域。一般说来，图的着色问题最早起源于著名的“四色问题”，染色问题不但有着重要的理论价值，而且，它和很多实际问题有着密切联系，例如通讯系统的频道分配问题，更有着广泛的应用背景. 本文首先讨论了人工智能的状态搜索方法在图着色中的具体应用，并用可视化方法展示了低维的着色空间和约束的具体意义。 关键词：图着色 c++代码 2、图的着色问题 2.1图的着色问题的来源 1852年，毕业于伦敦大学的弗南西斯·格思里(Francis Guthrie)在一家科研单位从事地图着色工作时，发现“任何一张地图似乎只用四种颜色就能使具有共同边界的国家着上不同的颜色。” 用数学语言来表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这就是源于地图着色的四色猜想问题。这里所指的相邻区域，是指有一整段边界是公共边界。如果两个区域只相遇于一点或有限多点，就不叫相邻。因为用相同的颜色给它们着色不会引起混淆。 用四种颜色着色的世界地图： 采用四种颜色着色的美国地图： 2.2图的着色问题的描述 （一）图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。 （二）通常所说的着色问题是指下述两类问题：

算法设计与分析复习题目及答案(1)

分治法1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间） 分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).

回溯法实验(最大团问题)

算法分析与设计实验报告第七次附加实验

} } 测试结果 当输入图如下时： 当输入图如下时： 1 2 3 4 5 1 2 3 4 5

当输入图如下时： 1 2 3 4 5

附录： 完整代码（回溯法） //最大团问题回溯法求解 #include using namespace std; class Clique { friend void MaxClique(int **,int *,int ); private: void Backtrack(int i); int **a; //图的邻接矩阵 int n; //图的顶点数 int *x; //当前解 int *bestx; //当前最优解 int cn; //当前顶点数 int bestn; //当前最大顶点数 }; void Clique::Backtrack(int i) { //计算最大团 if(i>n) //到达叶子节点 { for(int j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn;

cout<<"最大团：（"; for(int i=1;i=bestn) { //修改一下上界函数的条件，可以得到 x[i]=0; //相同点数时的解 Backtrack(i+1); } } void MaxClique(int **a,int *v,int n) { //初始化Y Clique Y; Y.x=new int[n+1]; Y.a=a; Y.n=n; https://www.wendangku.net/doc/7a11236965.html,=0; Y.bestn=0; Y.bestx=v; Y.Backtrack(1); delete [] Y.x; cout<<"最大团的顶点数："<

用回溯法求解图的m着色问题

实验二用回溯法求解图的m着色问题 一、实验目的 1 2、使用回溯法编程求解图的m着色问题。 二、实验原理 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树搜索。否则，进入该子树，继续按深度优先的策略进行搜索。 回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可结束。 回溯法从开始结点(根结点)出发，以深度优先搜索的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。 三、问题描述 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。若一个图最少需要m种颜色才能使图中任何一条边连接的2个顶点着有不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。设计一个算法，找出用m种颜色对一个图进行着色的不同方案。 四、算法设计与分析 用邻接矩阵a来表示一个无向连通图G=(V,E)。用整数1,2,…,m来表示m种不同的颜色。x[i]表示顶点i所着的颜色来，则问题的解向量可以表示为n元组x[1:n]。问题的解空间可表示一棵高度为n+1的完全m叉树。解空间树的第i层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一，第n+1层结点均为叶结点。 在回溯算法Backtrack中，当i>n时，表示算法已搜索至一个叶结点，得到一个新的m着色方案，因此当前已找到的可m着色方案数sum增1。当i≤n时，当前扩展结点Z是解空间树中的一个内部结点。该结点有x[i]=1,2,…,m。对当前扩展结点Z的每一个儿子结点,由函数Ok检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。 五、实验结果 源程序： #include using namespace std;

染色问题的计数方法

染色问题的计数方法 河北张家口市第三中学王潇 与染色问题有关的试题新颖有趣,其中包含着丰富的数学思想,染色问题,解题方法技巧性强且灵活多变,故这类问题有利于培养学生的创新思维能力,分析问题与观察问题的能力,有利于开发学生的智力。 一、区域染色问题 1.根据乘法原理，对各个区域分步染色，这是处理这类问题的基本的方法。 例1要用四种颜色给四川、青藏、西藏、云南四省（区）的地图染色（图1）每一省（区）一种颜色，只要求相邻的省（区）不同色，则不同染色的方法有多少种？ 分析先给西 藏 青海 云南 四川 四川染色有4种方 法，再给青海染色有3种方法，接着给西藏染色有2种方法，最后给云南染色有2种方法，根据乘法原理，不同的染色方法共有4×3×2×2＝48种 2.根据共用了多少种颜色分类讨论，分别计算出各种情形的种数，再用加法原理求出不同年拾方法种数。 例2 （2003年全国高考题）如图2，一个地区分为5个行政区域，现给地图着色，要求相邻区域不得使用同一颜色，

现有4种颜色可供选择，则不同的着色方法共有多少种？ 分析 依题意至少要 12 3 4 5图2选用3种颜色。 （1） 当选用三种颜色时，区域2与4必须同色， 区域3与5必须同色，有34A 种。 （2） 当用四种颜色时，若区域2与4同色，则区 域3与5不同色，有44 A 种；若区域3与5同色，则区域2与4不同色，有44 A 种，故用四种颜色时共有244A 种。 由加法原理可知满足题意的着色方法共有3 4A ＋244 A ＝24＋2×24＝72种。 3 根据某两个不相邻区域是否同色分类讨论，从某两个不相邻区域同色与不同色入手，分别计算出两种情形 的种数，再用加法原理求出不同染色方法数。 例3 用红、黄、蓝、白、黑五种颜色涂在“田”字形的四 个小方格内（图3），每格涂一种颜色，相邻的两格涂不同的 颜色，如果颜色可以反复使用，共有多少种不同的涂色方法？ 12 34 图3 （1）四格涂不同的颜色，方法数为45A ；

算法设计与分析复习题目及答案doc

分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。 实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。 不可以使用分治法求解的是（0/1背包问题）。 动态规划 下列不是动态规划算法基本步骤的是（构造最优解） 下列是动态规划算法基本要素的是（子问题重叠性质）。 下列算法中通常以自底向上的方式求解最优解的是（动态规划法） 备忘录方法是那种算法的变形。（动态规划法） 最长公共子序列算法利用的算法是（动态规划法）。 矩阵连乘问题的算法可由（动态规划算法B）设计实现。 实现最大子段和利用的算法是（动态规划法）。 贪心算法 能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题， 不能解决的问题：N皇后问题，0/1背包问题 是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。 回溯法 回溯法解旅行售货员问题时的解空间树是（排列树）。 剪枝函数是回溯法中为避免无效搜索采取的策略 回溯法的效率不依赖于下列哪些因素（确定解空间的时间）

分支限界法 最大效益优先是（分支界限法）的一搜索方式。 分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。 分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆） 优先队列式分支限界法选取扩展结点的原则是（结点的优先级） 在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法 ). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法 )之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 （2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 （最优子结构性质）是贪心算法与动态规划算法的共同点。 贪心算法与动态规划算法的主要区别是（贪心选择性质）。 回溯算法和分支限界法的问题的解空间树不会是( 无序树 ). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ）

地图着色问题

一、需求分析 1、问题描述 现在有一张地图，为了便于区别各个地图上的板块，地图上相 邻的颜色块应该是不同的颜色。现在的任务是给定一张地图，要对其进行着色，相邻的板块之间的颜色不能相同，输出最后 的着色的方案。 2、基本分析 功能一：为了程序的灵活性，可以让程序自由建立图 功能二：为建好的图进行着色。 3、输入输出 输入一张图的信息，正确输入边数和顶点数，输入边的关系（两 个顶点之间的），颜色只要四种，分别用数字1到4表示。 输出时根据每个顶点不同的标号输出着色的结果。 二、概要设计 1、设计思路 给定四种颜色，从选定的第一个顶点开始着色，先是第一种颜 色，如果这个颜色与这个顶点的其他邻接顶点颜色不重复，则 这个顶点可以使用此颜色，程序开始对下一个顶点着色；如果 着色重复，则使用下一种颜色重复上述过程。着色过程就是一 个递归的过程，直到所有的顶点都有着色后结束着色过程

结束

2、数据结构设计： 因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构是邻接矩阵，考虑用邻接表是因为一般的地图的某一 个顶点并不会与很多的顶点邻接，如果用邻接矩阵就能符合实 际的需求，虽然占用稍大的空间，但是增强了程序的实际使用 性。 抽象数据类型定义如下： 数据对象是点和边（vex&adj） 数据关系是颜色分布以及边的相邻的两个顶点 基本操作： CreatGrouph(&G); 创建一张需要操作的无向图G Destroy(Graph &G); 初始条件：无向图G存在 操作结果：销毁图G LocateVex(&G,i) 初始条件：无向图G存在 操作结果：若在图G中存在顶点i，则返回该顶点在图中的位置，否则返回其他信息 Trycolor(current &G,store[]) 初始条件：无向图G存在，在图中有第current个顶点

用回溯法分析着色问题

算法设计与分析课程设计 题目：用回溯法分析着色问题 学院：理学院 专业：信息与计算科学 班级：09信科二班 姓名：蔡秀玉 学号: 200910010207

用回溯法分析着色问题 目录 1 回溯法 (3) 1.1回溯法的概述 (3) 1.2 回溯法的基本思想 (3) 1.3 回溯法的一般步骤 (3) 2 图的m着色问题 (3) 2.1图的着色问题的来源 (3) 2.2通常所说的着色问题 (3) 2.3图的着色问题描述 (3) 2.4回溯法求解图着色问题 (5) 2.5图的m可着色问题的回溯算法描述 (6) 2.5.1回溯算法 (6) 2.5.2 m着色回溯法递归 (8) 2.5.3 m着色回溯法迭代 (9) 2.5.4例题利用回溯法给图着色 (11) 2.6复杂度分析着色回溯法迭代 (12)

§1 回溯法 1.1回溯法的概述 回溯法是一种系统地搜索问题解的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。 1.2回溯法的基本思想 回溯法的基本思想是，在确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。 1.3回溯法的一般步骤 用回溯法解题的一般步骤： （1）针对所给问题，定义问题的解空间； （2）确定易于搜索的解空间结构； （3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。 §2 图的m着色问题 2.1图的着色问题的来源 图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得

回溯法

第8章回溯法 (1) 8.1概述 (1) 8.1.1 问题的解空间树 (1) 8.1.2 回溯法的设计思想 (2) 8.1.3 回溯法的时间性能 (3) 8.1.4 一个简单的例子——素数环问题 (4) 8.2图问题中的回溯法 (5) 8.2.1 图着色问题 (5) 8.2.2 哈密顿回路问题 (8) 8.3组合问题中的回溯法 (10) 8.3.1 八皇后问题 (10) 8.3.2 批处理作业调度问题 (13) 习题8 (16)

第8章回溯法 教学重点回溯法的设计思想；各种经典问题的回溯思想教学难点批处理作业调度问题的回溯算法 教学内容 和 教学目标 知识点 教学要求 了解理解掌握熟练掌握问题的解空间树√ 回溯法的设计思想√ 回溯法的时间性能√ 图着色问题√ 哈密顿回路问题√ 八皇后问题√ 批处理作业调度问题√ 8.1 概述 回溯法（back track method）在包含问题的所有可能解的解空间树中，从根结点出发，按照深度优先的策略进行搜索，对于解空间树的某个结点，如果该结点满足问题的约束条件，则进入该子树继续进行搜索，否则将以该结点为根结点的子树进行剪枝。回溯法常常可以避免搜索所有的可能解，所以，适用于求解组合数较大的问题。 8.1.1 问题的解空间树 复杂问题常常有很多的可能解，这些可能解构成了问题的解空间（solution space），并且可能解的表示方式隐含了解空间及其大小。用回溯法求解一个具有n个输入的问题，一般情况下，将问题的可能解表示为满足某个约束条件的等长向量X=(x1, x2, …, x n)，其中分量x i（1≤i≤n）的取值范围是某个有限集合S i={a i,1, a i,2, …, a i,r i }，所有可能的解向量构成了问题的解空间。例如，对于有n个物品的0/1背包问题，其可能解由一个等长向量{x1, x2, …, x n}组成，其中x i=1（1≤i≤n）表示物品i装入背包，x i=0表示物品i没有装入背包，则解空间由长度为n的0/1向量组成。当n=3时，其解空间是：

水文地质图着色原则2018

水文地质图的着色原则 水文地质图的着色原则 1、颜色是最醒目、最直观的信息。对地质、矿产来说，最重要的是地层的时代 和成因。因此，不同地质时代的地层和不同成因的第四系，采取用不同的颜色来区分，参阅GB 6390—86《地质图用色标准》。 2、对水文地质来说，重要的是区分4种不同的含水岩体（松散岩类含水岩体、 碎屑岩类含水岩体、可溶岩类含水岩体、块状岩类含水岩体）和它们的富水性。 3、目前，各勘查单位编制的水文地质图，多按地质图的着色标准进行着色，其 颜色不能直观地反映不同的含水岩体和它们的富水性。 4、水文地质图、水文地质柱状图、水文地质剖面图的着色标准，建议参考《中 华人民共和国水文地质图集》的着色原则，采用黄、褐、蓝、红4种颜色代表松散岩类孔隙水含水岩体、碎屑岩类裂隙水含水岩体、可溶岩类岩溶水含水岩体、块状岩类火成岩裂隙水含水岩体。上述4种颜色由浅至深分为4种色调，反映含水层弱、中、强、极强4级富水性。保留地层时代的界限和代号。含水层的富水性分级，可以参照下表： 含水层富水性分级弱中强极强 泉水流量（L/s）<11～1010～100>100 管井出水量（m3/d）<100100～10001000～10000>10000钻孔单位涌水量（L/s.m）<0.10.1～11～10>10 5、变质岩中的板岩、片岩按碎屑岩类含水岩体着色；白云岩、大理岩按可溶岩 类含水岩体着色；片麻岩、混合岩按块状岩类含水岩体着色。 6、水文地质剖面图潜水位以上透水不含水的岩层不着色，隔水层可以用黑色正 交的网格表示。 7、根据上述简明的着色原则，除了地层的时代以外，颜色可以区分4种不同含 水岩体的地下水、4级不同的含水层富水性、含水层潜水位以上的包气带以及地下水的隔水层。 1

2019年六年级奥数题：染色问题(A)

2019年六年级奥数题：染色问题(A) (编者按:由于内容本身的限制,本讲不设填空题) 1.某影院有31排,每排29个座位.某天放映了两场电影,每个座位上都坐了一个观众.如果要求每个观众在看第二场电影时必须跟他(前、后、左、右)相邻的某一观众交换座位,这样能办到吗?为什么? 2.如图是一所房子的示意图,图中数字表示房间号码,每间房子都与隔壁的房间相通.问能否从1号房间开始,不重复的走遍所有房间又回到1号房间? 3.在一个正方形的果园里,种有63棵果树、加上右下角的一间小屋,整齐地排列成八行八列(见图 (a)).守园人从小屋出发经过每一棵树,不重复也不遗漏(不许斜走),最后又回到小屋,行吗?如果有80棵果树,连小屋在内排成九行九列(图(b))呢? (a) (b) 4.国际象棋(下图)去掉对角上两格后,是否可以用31个21 )把象棋盘上的62个小格完全盖住? 5.如果在中国象棋盘上放了多于45只马,求证:至少有两只马可以“互吃”.

6.空间6个点,任三点不共线,对以它们为顶点的线段随意涂以红色或蓝色,是否必有两个同色三角形? 7.如图,把正方体分割成27个相等的小正方体,在中心的那个小正方体中有一只甲虫,甲虫能从每个小正方体走到与这个正方体相邻的6个小正方体中的任一个中去.如果要求甲虫能走到每个小正方体一次,那么甲虫能走遍所有的正方体吗? 8.中国象棋的马走“日”字,车走横线或竖线,下图是半张中国象棋盘,试回 一只马从起点出发,跳了n 步又回到起点.证明:n 一定是偶数. 9.中国象棋的马走“日”字,车走横线或竖线,下图是半张中国象棋盘,试回 一只马能否跳遍这半张棋盘,每一点都不重复,最后一步跳回起点? 10.中国象棋的马走“日”字,车走横线或竖线,下图是半张中国象棋盘,试回

太原理工大学软件学院算法设计与分析复习题目及答案

一、选择题 1、二分搜索算法是利用（A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（B）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．最长公共子序列算法利用的算法是（B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 13．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 14.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解

m着色问题

图的m着色问题 问题描述： 给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m 可着色的。图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。 编程任务： 对于给定的无向连通图G和m种不同的颜色，编程计算图的所有不同的着色法。 数据输入： 由文件input.txt给出输入数据。第1行有3个正整数n，k和m，表示给定的图G 有n 个顶点和k条边，m种颜色。顶点编号为1，2，…，n。接下来的k行中，每行有2个正整数u,v，表示图G的一条边(u,v)。 结果输出: 程序运行结束时，将计算出的不同的着色方案数输出到文件output.txt中。 输入文件示例输出文件示例 input.txt output.txt 58448 12 13 14 23 24 25 34 45

/*图的m着色问题求解程序（回溯算法）*/ #include #include #include class color {private: int n,//图的顶点个数 m,//可用颜色数 **a,//图的邻接矩阵，用来表示一个无向连通图G *x;//当前解 long sum;//当前已找到的可m着色方案数 public: color(); int ok(int k); void backtrack(int t); void op(); ~color(); }; /*构造函数的定义*/ color::color() {int k;//边数 int i,j; int v1,v2;//构成边的两顶点 ifstream fin("input.txt",ios::nocreate); if(!fin) {cerr<<"文件不存在"; exit(0);} fin>>n>>k>>m;//读入顶点数、颜色数和边数if(!(a=new int*[n+1])) {cerr<<"insufficient memory!"<>v1>>v2; a[v1][v2]=a[v2][v1]=1;//对有连接的两个顶点v1,v2表示的边a[v1][v2]或a[v2][v1]赋值 } if(!(x=new int[n+1])) {cerr<<"insufficient memory!"<

图的m着色问题回溯法

图的m着色问题 1．问题描述 给定无向量图G顶点和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G图中每条边的两个顶点着不同的颜色。这个问题是图的m 可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的两个顶点着不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色问题。2．算法设计 一般连通图的可着色法问题并不仅限于平面图。给定图G=（V，E）和m种颜色，果这个图不是m可着色，给出否定回答，如果这个图是m的可着色的，找出所有不同的着色法。 下面根据回朔法的递归描述框架backtrack设计图的m着色算法。用图的邻接矩阵a表示无向量连通图G=（V，E）。若（i，j）属于图G=（V，E）的边集E，则a[i][j]=1，否则a[i][j]=0。整数1，2，…，m用来表示m种不同颜色。顶点i所有颜色用x[i]表示，数组x[1：n]是问题的解向量。问题的解空间可表示为一棵高度为n+1的完全m叉树。解空间树的第I （1<=i<=n）层中每一结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一。第n+1层结点均为叶结点。 在算法backtrack中，当i>n时，算法搜索至叶结点，得到新的m着色方案，当前找到的m着色方案数sum增1。 当I

回溯算法(解决着色问题)

实验四回溯算法 一、实验目的 1)理解回溯算法的基本原理，掌握使用回溯算法求解实际问 题。 二、方法原理 回溯法是一种类似穷举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回退，尝试别的路径。 三、实验设备 PC机一台，C语言、PASCAL语言、Matlab任选 四、掌握要点 搜索到解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯；否则进入该子树，继续按深度优先的策略进行搜索。 五、实验内容 实验内容：（二选一）1）编写程序实现4后问题的求解；2）编写程序实现用3种颜色为图2着色问题；

图2 六、实验要求 1)认真分析题目的条件和要求，复习相关的理论知识，选择适当的解决方案和算法； 2)编写上机实验程序，作好上机前的准备工作； 3)上机调试程序，并试算各种方案，记录计算的结果（包括必要的中间结果）； 4)分析和解释计算结果； 5)按照要求书写实验报告； 源代码：着色问题 #i n c l u d e #i n c l u d e #d e f i n e T R U E1 #d e f i n e F A L S E0 #d e f i n e M A X5 #d e f i n e C O L O R C O U N T3

i n t T F(i n t c o l o r,i n t i n d e x,i n t m[][M A X],i n t p[]){ f o r(i n t i=0;i

数据结构课程设计地图着色问题

课程设计报告 课程设计题目：地图着色问题专业：xxxxxxxxx 班级：xxxxxxxxx 姓名：xxxxxxxxx

一：需求分析： 1)已知中国地图，对各省进行着色，要求相邻省所使用的颜色不同，并保证使 用的颜色总数最少； 2)将各省进行编号，然后利用无向图个顶点之间的边来表示各省的相邻关系； 3)演示程序以用户和计算机的对话方式进行； 4)最后对结果做出简单分析。 二：概要设计 一：设计思路 把34个省看成34个顶点，从选定的第一个顶点开始着色，先试第一种颜色，如果这个颜色与这个顶点的其他邻接顶点的颜色不重复，则这个顶点就是用这种颜色，程序开始对下一个顶点着色；如果着色重复，则使用下一种颜色重复上面的操作。着色过程就是一个递归的过程，直到所有的顶点都处理完后结束着色。 二：数据结构设计 因为这个程序是对图的操作，所以程序采用的逻辑结构是图状，存储结构选用邻接表，考虑用邻接表是因为一般的地图的某一个顶点并不会与很多的顶点相邻接，如果用邻接矩阵会浪费很多的存储空间，所以我选择的邻接表来存储。 其中： typedef struct ArcNode { int x; （表示与当前顶点所表示省份相邻的省份的位置信息） struct ArcNode *next; （指向下一个弧结点） }ArcNode; （表示省份之间相邻关系的弧结点） typedef struct { char *name; （顶点所表示的省份的名称） int color; （省份的颜色，用数字表示不同的颜色） ArcNode *firstnext; （指向第一个弧） }shengfen[35]; 2 三：详细设计 该程序一共包含三个模版：分别为初始化模版、着色模版和输出模版。 1.初始化模块

图节点着色问题中的禁忌搜索算法

图节点着色问题中的禁忌搜索算法 09-03-25 作者：编辑：校方人员 图节点着色问题是组合最优化中典型的非确定多项式(NP)完全问题，也是图论中研究得最久的一类问题。目前解决该问题的算法很多，如回溯算法、分支界定法、Welsh-Powell算法、神经网络、遗传算法以及模拟退火算法等。综合比较各种算法，前两种算法是精确算法，但时间复杂性太大；后三种属于近似算法，虽然时间复杂性可接受，能够得到较好的近似解，但算法本身过于复杂，算法效率难以保证。 本文采用禁忌搜索算法，它同时拥有高效性和鲁棒性。禁忌搜索是一种全局逐步寻优的人工智能算法，它常能有效的应用于一些典型NP问题，如TSP。但禁忌搜索存在一些参数较难设置，这也是应用于通信系统时研究的热点。本文提出针对着色问题的禁忌搜索的具体设计方案，较好的设置了参数，并优化了数据结构，通过实验比较得到了较好的效果。最后提出通过领域简单的变化，禁忌搜索能较好的用于一般算法难以实现的List着色问题。 1图节点着色问题 图的着色问题可分为边着色、顶点着色、List着色和全着色，其中最主要的

给定一个无向图G=(V,E)，其中V是节点集V={1,2,…n}，E是边集，其中(i,j)表示有连接(i,j)的一条边。若，且V i内部的任何两个节点没有E中的边直接相连，则称(V1,V2,…,V n)为V的一个划分。图的节点着色问题可以描述为：求一个最小的k，使得(V1,V2,…,V n)为V的一个划分。 通常的解决着色问题的算法采用蛮力法、贪婪法、深度优先或广度优先等思想可以得到最优解，但时间复杂性太大，如回溯法，其计算时间复杂性为指数阶的；有的在多项式时间内能得到可行解，但不是最优解，如Welsh-Powell算法和贪婪算法。Welsh-Powell算法只能保证最多使用(为图中顶点的最大度)种颜色给一个图正常着色，而由Brooks定理，对于既不是完全图又不是奇圈的简单连通图，所需的颜色数。故通常的算法在解决图节点着色问题这样的NP完全问题时，存在很大的瓶颈，难以得到满意的结果。而对于像遗传算法和神经网络这样复杂的启发式算法，通常算法本身复杂性较大，并且算法效率难以分析，最终得到的是近似解，其是否最优解也不能保证。

图的染色问题

图的染色问题 应锡娜06990213@https://www.wendangku.net/doc/7a11236965.html, （浙江师范大学初阳学院，浙江金华321004） 摘要：本文介绍了图染色问题的提出、应用及意义，主要对已取得的研究成果及当今的研究状况进行了阐述。 关键词：图；染色；色数 一、引言 图染色问题起源于著名的“四色猜想”[1]问题。早在一百多年前的1852年，英国Guthrie提出了用四种颜色就可对任意一张地图进行染色的猜想。即对世界地图或任何一个国家的行政区域地图，最多用四种颜色就可以对其染色，使得凡是相邻的国家或相邻的区域都着以不同的颜色。 二、研究与发展 “四色猜想”提出后，一些数学家着手研究这个猜想，力图给出证明。时隔二十七年后，1879年Kempe给出了“四色猜想”的第一个证明，又过了十一年，1980年Hewood发现Kempe的证明是错误的。但他指出，Kempe的证明方法虽然不能证明“四色猜想”，却可以证明用五种颜色就够了。此后，“四色猜想”一直成为数学家们感兴趣而未能解决的世界数学难题。直到1976年6月美国数学家伊利诺斯大学教授Appel与Haken宣布：他们用计算机证明了“四色猜想”是正确的。因此，从1976年以后，就把“四色猜想”改称为“四色定理”了。[2] 值得指出的是，Appel与Haken的证明，计算机运行了1200个小时。诚然用计算机证明数学难题实在是一个伟大的尝试或创举，但是，世界数学家们仍期待着用常规的数学方法证明“四色定理”。目前仍有许多数学家在潜心研究，寻求常规的证明方法。 地图的特点在于，多个区域位于同一平面上，每个区域可以是毫无规则的各种形状，任意两个区域可以有公共边界，但不能有公共区域。于是人们开始研究所谓“平面图”。人们把地图中的每一个区域称为一个“面”，地图染色就是对“面”染色。进一步研究之后人们把地图中的每个区域的“面”视为一个点，若两个“面”相邻接，即地图中的两个区域有一段或几段公共边界，则在表示这两个区域的点之间连线，该连线可以是直线也可以是任意形状的曲线，并称之为边。如此，就可以把一张地图改画为一个平面上的图，人们把该图称为地图的对偶图。其特点是：所有的点及边均处在同一平面上，并且任意两条边除端点外可以不交叉，人们称这样的图为平面图。例如图1的对偶图如图2所示。

地图着色问题

地图着色问题 说明：任何平面区域图都可以用四种颜色着色，使相邻区域颜色互异。这就是四色定理。 要求给定区域图排出全部可能的四着色方案。 区域相邻关系用矩阵表示，每个区域又一个序号，（从0七连续排列）adj【i】【j勘硎厩 騣，j相邻。数组cilir记录每个区域上着的色，用1.2.3.4表示。 程序应包括四个函数： coloring对所给邻接矩阵找着全部着色方案 色乐的：对区域i在指定的颜色范围内选出可选颜色或报告失败（失败返回－1） 辞令次日卡：判断对区域i在指定的颜色c是否可用 八寸卡：选色失败时或完成一种着色方案时进行回溯 另外可定义output函数，每次输出一种着色方案 /* 递归算法： void Coloring(区域 n) 1. 令颜色集ClrSet={ 没有被区域n的邻居区域使用的颜色 }. 2. 如果ClrSet是空集，返回. 3. 对ClrSet中的每种颜色c，作循环： 3.1 为区域n着色c。 3.2 如果所有区域都已着色(n是最后一个区域)，那么显示/保存着色结果. 3.3 否则对下一个尚未着色的区域(n+1)，调用Coloring(n+1). 4. 把区域n变为没有着色的区域. -------------------------------------------------------- */ template class CColoring { private: typedef int node_type; typedef int color_type; typedef std::set node_set; typedef std::vector color_array; public: void operator()(const int _Matrix[node_count][node_count]) {