《高级人工智能》参考书目 马少平，朱小燕。人工智能。清华大学出版社。 蔡自兴，徐光祐。人工智能及其应用。清华大学出版社。 陆汝钤。 人工智能(上、下册) 。科学出版社。 Stuart Russell, Peter Norvig. Artificial Intelligence – A Modern Approach (2rd Edition). Prentice Hall Series in Artificial Intelligence. 影印版，清华大学出版社 中文版（姜哲等译）， 人民邮电出版社 Andries P. Engelbrecht. Computational Intelligence: An Introduction (2 Edition). Wiley Publishing, Inc, 2009. 谭营等译。计算智能导论（第2版）。清华大学出版社，2010年。

第Ⅱ部分 问题求解 第3章 用搜索法对问题求解 罗文坚 中国科大 计算机学院

本章内容 3.1 问题求解Agent 3.2 问题实例 3.3 通过搜索求解 3.4 无信息搜索策略 3.5 有信息（启发式）的搜索策略 3.6 启发式函数

3.4 无信息的搜索 概述 宽度优先搜索 代价一致搜索 深度优先搜索 深度有限搜索 迭代深度优先搜索 双向搜索 无信息的搜索策略的比较

概述 人类的思维过程，可以看作是一个搜索的过程。 各种各样的智力游戏。 比如，传教士和野人过河问题。 有3个传教士和3个野人来到河边准备渡河，河岸有一条船，每次最多可供二人乘渡。问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，在河的两岸以及船上的野人数目总是不超过传教士的数目（但允许在河的某一岸只有野人而没有传教士）？ 究竟什么方案才能在所规定的约束条件下顺利过河？ 所用方案的步骤是否最少？也就是说，是最优的吗？ 如果不是最优方案，如何才能找到最优方案？ 在计算机上又如何实现这样的搜索？

概述 搜索策略的主要任务是确定如何选择规则的方式。 有两种基本方式： 一种是不考虑给定问题所具有的特定知识，系统根据事先确定好的某种固定排序，依次调用规则或随机调用规则，这实际上是盲目搜索的方法，一般统称为无信息引导的搜索策略。 另一种是考虑问题领域可应用的知识，动态地确定规则的排序，优先调用较合适的规则使用，这就是通常称为启发式搜索策略或有信息引导的搜索策略。

概述 到目前为止，在人工智能领域中已提出许多具体的搜索方法，概括起来，常见的有以下几种。 求任一解路的搜索策略 求最佳解路的搜索策略 回溯法(backtracking) 深度优先法(depth-first) 宽度优先搜索法(breadth-first) …… 求最佳解路的搜索策略 最佳图搜索法(A*) 动态规划法(dynamic programming) 分支界限法(branch and bound) …… 求与或关系解图的搜索法 一般与或图搜索法(AO*) α-β剪枝法(alpha-beta pruning) 极大极小法(minimax) 启发式剪枝法(heuristic pruning) …… 爬山发（hill climbing） 限定范围搜索法（beam search）：也叫“集束搜索”，an optimization of best-first search。In beam search, only a predetermined number of best partial solutions are kept as candidates. 好的优先搜索法（best first）：Best-first search is a graph search which orders all partial solutions (states) according to some heuristic which attempts to predict how close a partial solution is to a complete solution (goal state). 大英博物馆法（British Museum）：One procedure for finding the shortest path through a net is to find all possible paths and to select the best from them.

3.4 无信息的搜索 概述 广度优先搜索 代价一致搜索 深度优先搜索 深度有限搜索 迭代深度优先搜索 双向搜索 无信息的搜索策略的比较

四皇后问题 下面以四皇后问题为例来说明回溯策略。 一个4×4的国际象棋棋盘上，一次一个地摆布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允许出现一枚棋子，即棋子间不许相互俘获。 下图给出棋盘的几个状态，其中a，b满足目标条件，c，d，e为不合法状态，即不可能构成满足目标条件的中间状态。

四皇后问题 综合数据库：DATA＝L（表），L的元素为ij ，1≤i, j≤4。 例：a，b分别记为（12 24 31 43）和（13 21 34 42），c，d，e分别记为（11 21），（11 22），（11 23 31）等等。 规则集：if 1≤i≤4 且 Length( DATA )＝i-1 then APPEND( DATA (ij) ) （1≤j≤4） 共16条规则，每条规则Rij表示满足前提条件下，在ij处放一棋子。 产生式系统的综合数据库是指对问题状态的一种描述，这种描述必须便于在计算机中实现，因此它实际上就是人工智能系统中所使用的数据结构，不同于软件工程中数据库这一术语的概念。计算机程序设计中常用的数据结构类型，如向量、集合、数组、符号串、树、表格乃至文件都可以作为综合数据库。

四皇后问题(续) 当规则序列以R11, R12, R13, R14, R21, … 这种固定排序方式调用BACKTRACK时，四皇后问题搜索过程如下 共回溯22次，主过程结束时返回规则表（R12, R24, R31, R43）。

四皇后问题(续) 在回溯策略中，通过引入一些与问题有关的信息可以加快搜索到解的速度。 当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置数是固定的 在最长对角线方向所影响的棋盘位置数则是不同的 尽量优先选择所影响的棋盘位置数少的位置 当一个皇后放到棋盘上后，不管它放在棋盘的什么位置，它所影响的行和列方向上的棋盘位置数是固定的，因此在行、列方面没有什么信息可以利用。但在不同的位置，在对角线方向所影响的棋盘位置数则是不同的，可以想象，如果当把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留有的余地就大，找到解的可能行也大；反之留有的余地就小，找到解的可能行也小。

四皇后问题(续) 可定义一个对角线函数diag( i，j )。该函数可计算出过棋盘上ij单元的最长的对角线长度，通过比较不同单元的diag( i，j )函数值来决定规则的排序。 若diag( i，k ) ＜ diag( i，j ) ，则为（Rik，Rij），即对角线短的单元，相应的规则排在前面； 若diag( i，k)＝diag (i，j)，则仍为（Rij ， Rik ）。 最长的对角线长度：考虑同一行的可以略去。

四皇后问题(续) 可定义一个对角线函数diag( i，j )。该函数可计算出过棋盘上ij单元的最长的对角线长度，通过比较不同单元的diag( i，j )函数值来决定规则的排序。 由此可计算得规则序列为: R12, R13, R11, R14, R21, R24, R22, R23, R31, R34, R32, R33, R42, R43, R41, R44。 最长的对角线长度：考虑同一行的可以略去。

四皇后问题(续) 规则序列：R12, R13, R11, R14, R21, R24, R22, R23, R31, R34, R32, R33, R42, R43, R41, R44 利用这样的规则排序方法后，只回溯2次就找到了目标。 动态排序搜索树

深度优先搜索 深度优先搜索：总是扩展搜索树的当前边沿中最深的节点。 对于当前节点，每次产生该节点的所有后继节点，从中选择一个往下搜索。 回溯搜索：深度优先搜索的一种变形。 每次只产生一个后继节点而不是所有节点。

回溯策略 回溯策略 Backtracking strategies，属于盲目搜索 首先将规则给出一个固定的排序，在搜索时，对当前状态（在搜索开始时，当前状态是开始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可应用规则，应用于当前状态，得到新的状态重新设置为当前状态，并重复以上搜索。 如果当前状态无规则可用，或者所有规则都已经被试探过仍未找到问题的解，则将当前状态的前一个状态（即直接生成该状态的状态）设置为当前状态。 重复以上搜索，直到找到问题的解，或者试探了所有可能后仍找不到问题的解为止。 回溯策略有多种实现方法，其中递归法是一种最直接的实现方法。

递归过程BACKTRACK BACKTRACK(DATA) IF TERM(DATA), RETURN NIL; TERM取真表示找到目标，则过程返回NIL IF DEADEND(DATA), RETURN FAIL; DEADEND取真，该状态不合法，则过程返回FAIL，必须回溯 RULES:=APPRULES(DATA); APPRULES计算当前DATA的可用规则集，依据某种原则（任意排列或按启发式准则）排列后赋给RULES LOOP: IF NULL(RULES) RETURN FAIL; NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯 R:=FIRST(RULES); 取第一条可用规则 RULES:=TAIL(RULES); 删去第一条规则，减少可应用规则表的长度 RDATA:=GEN(R, DATA); 调用规则R作用于当前状态，生成新状态 PATH:=BACKTRACK(RDATA); 对新状态调用本递归过程 IF PATH=FAIL, GO LOOP; 当PATH=FAIL时，递归调用失败，则转移调用另一规则进行测试 RETURN CONS(R, PATH); 过程返回解路径规则表（或局部解路径规则表） LISP语言的形式

递归过程BACKTRACK 在回溯算法BACKTRACK中，设置了两个回溯点： 一个是当遇到非法状态时回溯。 一个是当试探了一个状态的所有子状态后，仍然找不到解时回溯。 这个简单的BACKTRACK过程只设置两个回溯点，可用于求解N－皇后这类性质的问题。 存在问题： 有些问题的某一个（或某些）分支具有无穷多个状态，算法可能会落入某一个“深渊”，永远也回溯不回来。 在某一个（或某些）分支上有环路，搜索会在这个环路中一直进行下去，同样也回溯不出来，从而找不到问题的解。

递归过程BACKTRACK 解决办法：增加两个回溯点 一个是用一个常量BOUND来限制算法所能够搜索的最大深度。当当前状态的深度达到了限制深度时，算法将进行回溯，从而可以避免落入“深渊”。 将过程的参数用从初始状态到当前状态的表来替代原来的当前状态。当新的状态产生时，查看是否已经在该表中出现了。如果出现过，则表明有环路存在，算法将进行回溯。

递归过程BACKTRACK1 BACKTRACK1( DATALIST ) DATA:=FIRST(DATALIST); 设置DATA为当前状态 IF MEMBER(DATA, TAIL(DATALIST)), RETURN FAIL; 出现环路，回溯 IF TERM(DATA), RETURN NIL; TERM取真表示找到目标，则过程返回NIL IF DEADEND(DATA), RETURN FAIL; DEADEND取真，该状态不合法，则过程返回FAIL，必须回溯 IF LENGTH(DATALIST)>BOUND, RETURN FAIL; 搜索深度过大，回溯 RULES:=APPRULES(DATA); APPRULES计算当前DATA的可用规则集，依据某种原则（任意排列或按启发式准则）排列后赋给RULES

递归过程BACKTRACK1（续） …… LOOP: IF NULL(RULES) RETURN FAIL; NULL取真，即规则用完未找到目标，过程返回FAIL，必须回溯 R:=FIRST(RULES); 取第一条可用规则 RULES:=TAIL(RULES); 删去第一条规则，减少可应用规则表的长度 RDATA:=GEN(R, DATA); 调用规则R作用于当前状态，生成新状态 RDATALIST:=CONS(RDATA,DATALIST); 将新的状态加入DATALIST PATH:=BACKTRACK1(RDATALIST); 对新状态调用本递归过程 IF PATH=FAIL, GO LOOP; 当PATH=FAIL时递归调用失败，则转移调用另一规则进行测试 RETURN CONS(R, PATH); 过程返回解路径规则表（或局部解路径规则表）

递归过程BACKTRACK1 推广的回溯算法可应用于一般问题的求解。 但这两个算法只描述了回溯一层的情况，即第n层递归调用失败则控制返回到第n-1层继续搜索。 实际上，也可以利用启发式信息，分析失败原因，在回溯到合适的层次上，即多层回溯。 造成深层搜索失败往往在于浅层原因引起

小结 深度优先搜索 回溯搜索