目录

• 1.回溯算法
  1.1 回溯算法简介
  1.2 一般回溯方法
• 2.收费公路重建问题（通过考虑最大值策略，对可能性空间X_i进行了大幅度裁剪）
  2.1 问题描述
  2.2 一个例子
  2.3 收费公路重建算法
  2.4 算法分析
• 3.博弈
  3.1 问题描述
  3.2 极小极大策略
  3.3 极小极大策略用于更复杂的游戏——西洋跳棋、国际象棋
  3.4 α-β裁剪
• 4.三着色问题
  4.1 问题描述
  4.2 问题求解
• 5.八皇后问题
  5.1 问题描述
  5.2 考虑4皇后问题的解法
• 6.哈密尔顿回路问题
  6.1 问题描述
  6.2 问题求解

1.回溯算法

1.1 回溯算法简介

• 像大多数NP难问题一样，通过穷尽搜索数量巨大但有限多个可能性，可以获得一个解。而且，事实上对于所有这些问题都不存在用穷尽搜索之外的方法来解决问题。所以产生了开发系统化的搜索技术的需要，并且希望能够将搜索空间减少到尽可能小。
• 回溯法就是一种组织搜索的一般技术。回溯法可以被描述为有组织的穷举搜索，它常常可以避免搜索所有的可能性。
  一般适用于求解那些有潜在的大量解，但有限个数的解已经检查过的问题。

1.2 一般回溯方法

1）一般回溯方法概念
一般回溯方法应用到一类搜索问题中，这类问题的解由满足事先定义好的某个约束的向量(x₁, x₂, ..., x_i)组成。这里i是0到n之间的某个整数，其中n是一个取决于问题阐述的常量。
1-1） 对于一些问题，i是固定不变的
例如三着色和八皇后问题

1-2） 另一些问题中，i对于不同的解可能有所不同（可转换为统一的长度）

• 考虑定义如下的PARTITON问题中的一个变型。给定一个n个整数的集合X={x₁, x₂, ..., x_n}和整数y，找出和等于y的X的子集Y。比如说，如果X = {10, 20, 30, 40, 50, 60}和y = 60，则有三种不同的解，它们分别是{10, 20, 30}, {20,40}和{60}。设计一个回溯算法求解并不困难。
  这个问题可以用另一种方法明确表达，使得解释一种明显的长度为n的布尔向量，于是上面的三个解可以用布尔变量表示为{1, 1, 1, 0, 0, 0}, {0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1}。

2）一般回溯方法的描述

• 解向量中每个x_i都属于一个有限的线序集X_i
• 回溯法按词典序考虑笛卡尔积X₁ × X₂ × ... × X_n 。
  （开始）算法最初从空向量开始，然后选择X₁中最小的元素作为x₁，如果(x₁)是一个部分解，算法通过从X₂中选择最小的元素作为x₂继续，如果(x₁， x₂)是一个部分解，那么就包括X₃中最小的元素，否则x₂被置为X₂重的下一个元素。
  （一般情况）假定算法已经检测到为(x₁， x₂, ..., x_j)，它然后考虑向量v = (x₁， x₂, ..., x_j, x_{j + 1})，有以下情况：
  1.如果v表示问题的最后解，算法记录下它作为一个解，在仅希望获得一个解时终止，或者继续去找出其他解。
  2.（向前步骤）。如果v表示一个部分解，算法通过选择集合X_j+2中的最小元素向前。
  3.如果v既不是最终解，也不是部分解，则有两种子情况
  3-1.如果从集合X_j+1中还有其他的元素可选择，算法将x_{j + 1}置为X_j+1中的下一个元素。
  3-2.（回溯步骤）。如果从集合X_j+1中没有更多的元素可选择，算法通过将x_j置为X_j中的下一个元素回溯；如果从集合X_j中仍然没有其他的元素可以选择，算法通过将x_j-1置为X_j-1中的下一个元素回溯，依次类推。

3）（获得一个解）回溯算法的伪代码描述

• 通常如果需要使用回溯法来搜索一个问题的解，可以使用这两个原型算法之一作为框架，围绕它设计出专门为具体问题而裁剪出的算法来。

1）递归形式

递归回溯算法

2）迭代形式

迭代回溯算法

2.收费公路重建问题（通过考虑最大值策略，对可能性空间X_i进行了大幅度裁剪）

2.1 问题描述

根据N(N-1)/2个形如|x_i - x_j|（i≠j）的距离，重新构造这N个点集。
在物理学和分子生物学中都有应用。
重建问题没有人能够给出一个算法保证在多项式时间内完成计算。在最坏情形下可能要花费指数时间。

2.2 一个例子

D是距离集合，并设|D| = N(N-1)/2。
D = {1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10}
可知N = 6.

• step1.（x₁ = 0，x₆ = 10）算法开始置x₁ = 0。显然x₆ = 10。
  从D中删除x₆ - x₁ = 10。
  
• step2.（x₅ = 8）剩下的距离中最大是8，要么x₂ = 2，要么x₅ = 8。由对称性，断定这种选择是不重要的，可置x₅ = 8。
  从D中删除x₅ - x₁ = 8 和 x₆ - x₅ = 2。
  
• step3.（x₄ = 7或x₂ = 3）剩下距离中最大的是7，要么x₄ = 7，要么x₂ = 3（特别注意：已经排除了x₂ = 1，如果选定x₂ = 1，则|x₆ - x₁| = 9 > 7）。
  step3-1.考虑x₄ = 7。从D删除x₄ - x₁ = 7 ， x₅ - x₄ = 1和 x₆ - x₄ = 3。
  
  step3-2.考虑x₂ = 3。从D删除x₂ - x₁ = 3 ， x₅ - x₂ = 5和 x₆ - x₂ = 7。
  
• step4.首先考虑step3-1的情况，此时x₄ = 7。剩下距离中最大的距离是6，要么x₃ = 6，要么x₂ =4。
  
  step4-1.考虑x₃ = 6。那么x₄ - x₃ 1，不可能，因为1不再属于D。继续搜索。
  step4-2.考虑x₂ = 4。那么x₂ - x₀ = 4，x₅ - x₂ = 4，这也不可以，因为4在D中只出现一次。
  回溯考虑step3-2的情况。此时x₂ = 3。剩下距离中最大的距离是6，要么x₃ = 6，要么x₂ =4。
  
  step4-3.考虑x₃ = 4。不可能，该选择有两个4，而D中只有一个。
  step4-4.考虑x₄ = 6。唯一剩下的选择是x₃ = 5。正好可以。
  
  

收费公路重建问题的决策树

2.3 收费公路重建算法

算法的核心思路：

• 驱动代码，首先确定无争议的x₁，x_N和x_N-1
• 回溯步骤：以递归方式实现。传递同样的参数以及界Left和Right，x_Left，...，x_Right是视图放置的点的x坐标。

驱动代码
回溯步骤

2.4 算法分析

可以将D作为平衡二叉查找树保存（代码需要修改）。如果从未回溯，那么最多有O(N²)涉及到对D（平衡二叉查找树）的查找和删除操作。因此，在没有回溯的情况下，运行时间为O(N²logN)。

3.博弈

3.1 问题描述

• 考虑计算机用来进行战略游戏的策略，如西洋跳棋和国际象棋。以简单得多的三连游戏棋（tic-tac-toe）来进行表述。

• 三连棋的游戏规则：
  两人轮流在一有九格方盘上划加字或圆圈，谁先把三个同一记号排成横线、直线、斜线，即是胜者。

  
  tic-tac-toe

3.2 极小极大策略

• （赋值）更一般的策略是使用一个赋值函数来给一个位置的“好坏”定值。能使计算机获胜的位置+1；平局得0；使计算机输棋的位置-1.
• （终端位置）通过考察盘面能够确定这局输赢的位置叫做终端位置。
• （极小极大策略）如果一个位置不是终端位置，那么该位置的值通过递归地假设双方最优棋步而确定。下棋的一方（人）试图使这个位置的值极小化，而另一方（计算机）却要使它的值极大。
  FindCompMove计算机选择具有最大值的一步行棋。
  FindHumanMove行棋人在此基础上找出具有最小值的一步行棋。
• （后继位置）位置P的后继位置是通过从P走一步棋可以达到的任何位置P_s。
  如果当在某个位置P计算机要走棋，那么它递归地求出所有的后继位置的值。计算机选择具有最大值的一步行棋，这就是P的值。
  为了得到任意后继位置P_s的值，要递归地算出P_s的所有后继位置的值，然后选取其中最小的值。这个最小值代表行棋人一方最赞成的应招。

（draw在英语表示和棋）

• 第1行和第4行直接给和棋、赢棋赋值；其他情况，则该位置是非终端位置。
• Value应该包括所有可能后继位置的最大值，这就是5-13行的事情
  回溯在于第8行的Place(Board, i, Comp)和第10行Unplace(Board, i)。
• FindHumanMove递归调用FindCompMove。如果下棋人对一步棋的应招给计算机留下比计算机前面最佳棋步所得到的位置更好的位置，那么Value和BestMove将被更新。

3.3 极小极大策略用于更复杂的游戏——西洋跳棋、国际象棋

• （递归深度、求值函数）搜索到终端节点的全部棋步不可行，达到某个深度（层）之后只能停止搜索。递归停止出的结点则成为终端结点。这些终端结点的值由一个估计位置的值的函数计算出来了。
  求值函数对于成功是至关重要的，因为计算机的行棋选步是基于将这个函数极大化。最好的计算机下棋程序的求值函数惊人的复杂。
• （置换表）如果已经计算过，那么一个位置在第二次出现时就不必再重新计算，将这些值存储在散列表中。

3.4 α-β裁剪

3.4.1 博弈树（game tree）

• 博弈树：假象的棋局中用来给某些某个假设的位置求值的一些递归调用的迹。

  
  
• 上图中几乎有一半的终端节点没有被检验。以下两个裁剪将证明计算它们的值将不改变树根的值。

3.4.2 α裁剪

• 如图所示，D不需要求值。

• 实现α裁剪的方法，FindCompMove将它的尝试性的极大值α传递给FindHumanMove。如果FindHumanMove的尝试性的极小值低于这个值，那么FindHumanMove立即返回。

  
  α裁剪

3.4.3 β裁剪

• 如果所示，C不用求值。

• 实现β裁剪的方法，FindHumanMove将它的尝试性的极小值β传递给FindCompMove。如果FFindCompMove的尝试性的极大值大于这个值，那么FindCompMove立即返回。

  
  β裁剪
  β裁剪

4.三着色问题

4.1 问题描述

• 给出一个无向图G = (V, E)，需要用三种颜色之一为V中的每个顶点着色，三种颜色分别为1, 2, 3，使得没有两个邻接的顶点有同样的颜色。
• 一种着色可用n元组(c₁, c₂, ..., c_n)来表示，使c_i ∈ {1, 2, 3}，1 ≤ i ≤ n。
• 一个n个顶点图共有3ⁿ种可能的着色（合法的和非法的），所有可能的着色的集合可以用一棵完全的三叉树表示，称为搜索树。在这棵树中，从根到叶节点的每一条路径代表一种着色指派。（跟n个元素的全排列类似，只不过只有两种可能，大于和小于的决策树，参见排序算法总结）
  三结点的三着色搜索树

4.2 问题求解

回溯法求解三着色问题

回溯法的基本特征：

• 结点是用深度优先搜索的方法生成
• 不需要存储整棵搜索树，只需要存储根到当前活动结点的路径

4.2.1 递归算法（假设顶点集合是{1, 2, ..., n}）

• 回溯由graphcolor(k)中的for循环体现。

  
  
  

4.2.3 迭代算法

• 内层while循环实现前进（生成新结点）

• 外层while循环实现回溯的过程

  
  
  

4.2.4 时间复杂度

最坏情况下生成了O(3ⁿ)个结点，对于每个结点，都需要O(n)的时间来检查。因此，最坏情况为O(n3ⁿ)。

5.八皇后问题

5.1 问题描述

• 8皇后问题：如何在8 × 8的国际象棋棋盘上安排8个皇后，使得没有两个皇后能相互攻击？如果两个皇后处在同一行、同一列或同一条对角线上，则她们能互相攻击。
• n皇后问题：如何在n × n的国际象棋棋盘上安排n个皇后，使得没有两个皇后能相互攻击？ n ≥ 1。

5.2 考虑4皇后问题的解法

5.2.1 解空间——搜索空间

• （没有两个皇后在同一行）每行上有4个位置，就有4⁴种可能的布局，每种可能的布局可以用一个4分量的向量x = {x₁, x₂, x₃, x₄}描述。
• （没有两个皇后在同一行和同一列）搜索空间由4⁴减少到4!。

5.2.2 回溯法求解

• 算法尝试生成并以深度优先方式搜索一棵完全四叉有根树
  树根对应于没有放置皇后的情况；
  第一层的结点对应于皇后的第一行的可能放置情况；
  第二层的结点对应于皇后在第二行的可能放置情况；
  依此类推。
• 合法——表示一个不互相攻击的4个皇后的放置
  部分——表示一个不互相攻击的少于4个皇后的放置
• x_i与x_j相互攻击
  同一列——x_i = x_j
  同一对角线——x_i - x_j = i -j 或 j - i

回溯法求解4皇后问题的搜素树

6.哈密尔顿回路问题

6.1 问题描述

• 寻找无向图G=(V, E)中的哈密顿回路。
• 设无向图G=(V, E)，v₁v₂...v_n是G的一条通路，若G中每个顶点在该通路中出现且仅出现一次，则称该通路为哈密顿通路。若v₁=v_n，则称该通路为哈密尔顿回路。

6.2 问题求解

• 假定G=(V, E)的顶点集为V={0,1,...,n-1}。
• 按照回路中顶点的顺序，用n元向量X=(x₀, x₁, ..., x_n-1)来表示回路中的顶点编号，其中x_i ∈{0, 1, ..., n-1}。

• 用布尔数组c[n][n]来表示图的邻接矩阵，如果顶点i和j相邻接，则c[i][j]为真。则哈密顿回路满足如下约束：

  
  

回溯法步骤：

• step1.把顶点0作为回路中第一个顶点，搜索与顶点0相邻接的编号最小的顶点，作为它的后续顶点
• step2.假定在搜索过程中已经生成了通路l = x₀x₁...x_i-1
  寻找与x_i-1相邻接的并且不属于l的编号最小的顶点。如果搜索成功，就把这个顶点作为通路中的顶点x_i，然后继续搜索下一个顶点。
• step3.如果不成功，就把l中的x_i-1删除，从x_i-1的顶点编号加1的位置开始，继续搜索与x_i-2相邻接的并且不属于l的编号最小的顶点
• step4.当搜索到l中的顶点x_n-1时，如果x_n-1与x₀相邻接，则所生成的回路就是一条哈密顿回路；
  否则，把l中的x_n-1删除，继续回溯。最后，如果在回溯过程中，l中只剩下一个顶点x₀，则表明图中不存在哈密顿回路。（如果图中存在一个哈密顿回路，那么从任何一个顶点出发都能找到一个，如果回溯到只有一个顶点，则表明x₀与其相邻接的顶点的所有可能性都常识过了，都不能形成哈密顿回路，因此必然不存在。）

6.3 一个示例