《高级人工智能》参考书目 马少平，朱小燕。人工智能。清华大学出版社。 蔡自兴，徐光祐。人工智能及其应用。清华大学出版社。

Presentation on theme: "《高级人工智能》参考书目 马少平，朱小燕。人工智能。清华大学出版社。 蔡自兴，徐光祐。人工智能及其应用。清华大学出版社。"— Presentation transcript:

1 《高级人工智能》参考书目 马少平，朱小燕。人工智能。清华大学出版社。 蔡自兴，徐光祐。人工智能及其应用。清华大学出版社。
陆汝钤。 人工智能(上、下册) 。科学出版社。 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年。

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

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

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

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

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

7 概述 到目前为止，在人工智能领域中已提出许多具体的搜索方法，概括起来，常见的有以下几种。 求任一解路的搜索策略 求最佳解路的搜索策略
回溯法(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.

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

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

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

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

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

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

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

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

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

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

18 递归过程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语言的形式

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

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

21 递归过程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

22 递归过程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); 过程返回解路径规则表（或局部解路径规则表）

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

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