• 一、算法介绍
• 二、3-着色问题
  • 1、问题描述
  • 2、分析过程
• 三、8-皇后问题
  • 1、问题描述
  • 2、分析过程
• 四、Hamilton回路问题
  • 1、问题描述
  • 2、分析过程
• 五、子集和问题
  • 1、问题描述
  • 2、分析过程

一、算法介绍

1、普遍地适用于解决需要检测有限但是大量的可能的解的组合问题。

2、基本框架：深度优先搜索，从顶点逐层遍历；针对当前节点，遍历取值范围，若为合法部分解，则递归进入下一层，否则更换本层的其他顶点；若本层顶点遍历完后，均无合法部分解，则回溯到上一层。

二、3-着色问题

1、问题描述

给定一个无向图G=<V,E>，需要对其中的每一个顶点着1、2、3三种颜色之一，使得任意两个相邻顶点不是同种颜色。

输入：图G=<V,E>，三种颜色

输出：若存在合法的着色方案，输出所有解向量c=<c1,c2,...,cn>, 1<=ci<=3,表示第i个顶点的着色。

2、分析过程

1、针对n个顶点的图，以深度优先的策略进行搜索，对当前节点着色，判断是否合法，若合法则进行下一层，若不合法，则变换当前节点的着色。

2、若遍历颜色后，均不合法，则回溯到当前节点的父节点，变换着色。（回溯过程）

3、若从根到叶子的着色方案合法，输出合法解。

三、8-皇后问题

1、问题描述

经典8-皇后问题：在一个8*8的棋盘上放置8个皇后，使得任意两个皇后之间不能相互攻击。若两个皇后同处于1行、1列或者1个斜线上，则可以相互攻击。

n-皇后问题：对任意的n>1，有n个皇后，放置在n*n的棋盘上，使其任意两个不能相互攻击。

输入：棋盘规模n

输出：棋盘合法布局，x=<x1,x2,...,xn>

2、分析过程

1、由于不能同处于一行或者一列，则棋盘上每行每列均只能放置一个皇后。

2、可以用向量x=<x1,x2,...,xn>表示棋盘上第i行的皇后放置的列的位置，一个x即为一个解。由于不能同列，则x实际上是x1,x2,...,xn的一个排列。

3、利用深度优先搜索，树根表示为放置任何皇后。第一层表示第一行的皇后放置的列的位置，第二层表示第二行的皇后放置的列的位置，依次类推。

4、从根节点开始遍历，逐层监测对应列放置的位置，若监测到该行的合法位置则继续下一行，否则回溯到上一层。

四、Hamilton回路问题

1、问题描述

在一个无向图G=<V,E>中，寻求中顶点s出发，经过G中每一个顶点一次，最后回到顶点d的回路。

输入：具有n个顶点的无向图G=<V,E>，起始顶点s。

输出：合法Hamilton回路，向量x=<x1,x2,...,xn>

2、分析过程

1、以起始顶点s为根节点，按深度优先原则搜索。

2、逐次遍历当前顶点的相邻顶点，判断是否可以扩展成下一个分量。

3、若可以扩展，则递归进入下一层；若与当前顶点相邻的顶点均不能扩展，则回溯到上一层。

五、子集和问题

1、问题描述

1、在一个整数集合A={a1,a2,...,an}中，寻找一个子集合A`中元素的和等于给定元素C。

输入：整数集合A={a1,a2,...,an}，整数值C

输出：向量x=<x1,x2,...,xn>,xi=0或者1，表明a1是否属于子集合。

2、分析过程

1、从根节点开始，按深度优先搜索；

2、对当前节点，分别用0、1检测是否构成合法的部分解；

3、若是，则进入下一层；若0和1均不能构成合法部分解，则回溯到上一层。