2.3 收费公路重建算法

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

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

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

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

  
  

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

（draw在英语表示和棋）

• 第1行和第4行直接给和棋、赢棋赋值；其他情况，则该位置是非终端位置。
• FindHumanMove递归调用FindCompMove。如果下棋人对一步棋的应招给计算机留下比计算机前面最佳棋步所得到的位置更好的位置，那么Value和BestMove将被更新。

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

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

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

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

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

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

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

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

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

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

  
  
  

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

• 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!。

• 算法尝试生成并以深度优先方式搜索一棵完全四叉有根树
  树根对应于没有放置皇后的情况；
  第一层的结点对应于皇后的第一行的可能放置情况；
  第二层的结点对应于皇后在第二行的可能放置情况；
  
• 合法——表示一个不互相攻击的4个皇后的放置
  部分——表示一个不互相攻击的少于4个皇后的放置

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

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

  
  

• step1.把顶点0作为回路中第一个顶点，搜索与顶点0相邻接的编号最小的顶点，作为它的后续顶点
寻找与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₀与其相邻接的顶点的所有可能性都常识过了，都不能形成哈密顿回路，因此必然不存在。）