搜索问题_人工智能剖析

《搜索问题_人工智能剖析》由会员分享，可在线阅读，更多相关《搜索问题_人工智能剖析（152页珍藏版）》请在金锄头文库上搜索。

1、搜索问题,1,第三章 搜索问题,3.1 状态空间搜索概述 3.2 回溯策略 3.3 图搜索策略 3.4 盲目的图搜索过程 3.5 启发式图搜索过程,搜索与搜索问题,人类的实际搜索行为 人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。 根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索 。,搜索法的主要任务：确定以何种方式选择规则？ 求任一解路的搜索策略： backtracking、 Hill Climbing、Breadth-first、 Depth-first、Beam Search、 Bes

2、t-first (A). 求最佳解路的搜索策略：British Museum、Branch and Bound、 Dynamic Programming、Optimal search (A*). 求与或图解图的搜索策略： AO*、 Minimax、Alpha-beta Pruning、 Heuristic Pruning.,搜索方法的经典应用,8数码问题 传教士和野人问题 旅行商问题 4皇后问题 迷宫问题 博弈问题 ,搜索算法的输入是给定的问题，输出时表示为动作序列的方案。 一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段） 求解问题包括： 目标表示 搜索 执行,内容： 状态空间的搜索

3、问题。 搜索方式： 盲目搜索 启发式搜索 关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。,搜索问题,3.1 状态空间搜索概述,3.1.1 图的概念 图是节点及连接节点的弧的集合。 由方向性的弧连接的图是有向图。 节点深度的表示：根节点深度为0，其他节点深度dn+1=dn+1。 路径：N个有序节点组成的序列中，若每对相邻节点都表示一条弧，则称该序列为图中长度为N-1的一条路径。 路径耗散值：令C（ni，nj）为节点ni到节点nj这段路径（或弧线）的耗散值，一条路径的耗散值等于这条路径上所有弧线耗散值的总和。路径耗散值可按如下递归公式计算：C（ni，t）=C（ni，nj）+C（nj

4、，t） 节点的扩展：操作符（规则）作用到节点（对应于某一状态描述）上，生成其所有后继节点（新状态），并给出弧线的耗散值（相当于使用规则的代价），这个过程叫做扩展一个节点。,3.1.2 问题状态空间的图描述,图是最直观的描述问题状态空间的工具，属于显式描述。 图中的节点表示问题的状态，图中的弧表示状态之间的关系。 初始状态对应待求解问题的已知信息，是图的根节点。,3.1.3 问题状态空间的搜索,状态空间法将一个待定问题的求解过程定义为若干算子与搜索的有机结合体。 算子定义了对状态的操作，求解的目的在于找出从初始状态转换为某个（或某些）目标状态的一个（或一组）操作算子序列。 以上问题等价于在图中寻

5、找从根节点到某个（或某些）目标节点的一条（或一组）路径。,为提供对问题的形式描述，需要： 定义状态空间，包含问题相关对象的各种可能排列。对空间的定义不必枚举所有状态。 规定一个或多个属于该空间的初始状态。该状态用以描述问题求解过程开始时的状态。 规定一个或多个属于该空间的目标状态。该状态用以判断是否得到了问题的解。 规定一组规则。描述可使用的操作或算子。 将待求解问题转换成状态空间描述后，使用控制策略对规则进行选择性的应用，在问题状态空间内进行搜索，直到找出从初始状态到目标状态的一条（或一组）路径。,3.1.4 搜索的基本概念,状态空间图的搜索，是搜索满足条件的一个（或一组）操作算子序列的过程

6、，这个过程也是将一个隐式图中包含目的节点的某个子图变为显式的过程。这种搜索过程是状态空间问题求解的主要基础。,搜索过程的要点是： 从初始或目的状态出发，并将它作为当前状态。 扫描操作算子集合，将适用于当前状态的一些操作算子作用在其上得到新的状态，并建立新状态与父母节点的连接指针。 检查生成的新状态是否是结束状态，如果是，则沿着有关指针从结束状态反向到达开始状态，给出一个解；否则，将新状态作为当前状态，返回第2)步继续搜索。,搜索问题,S0,Sg,有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。,搜索需考虑的问题,盲目搜索 只是可

7、以区分出哪个是目标状态。 一般是按预定的搜索策略进行搜索。 没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。,启发式搜索 是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。,3.2 回溯策略,回溯策略是一种尝试状态空间中各种不同路径的技术。 带回溯策略的搜索从初始状态出发，不停地、试探地寻找路径直到找到目标节点或“不可解节点”“死胡同”。 找到目标节点，退出搜索，返回解路径。 遇到不可解节点时，回溯到路径中最近的父节点上，查看该节点是否还有其他子节点未被扩展，如有则沿这些子节点继续搜索。 可以看出，这

8、种求解过程呈现出递归过程的性质。求解过程在每个节点上的检查遵循着递归方式。 递归法是回溯策略的一种最直接的实现方法。,回溯搜索策略,例：四皇后问题 在方格的棋盘内，放置四个皇后 使任意两个皇后不在同一行、同一列、同一对角线（斜线）上 要求：找出所有的摆法,回溯搜索策略,状态描述： 单个皇后位置的描述： 用(i,j)表示皇后在第i行j列 系统状态的描述 四个皇后 (i1,j1), (i2,j2), (i3,j3), (i4,j4),( ),( ),Q,(1,1),( ),Q,Q,(1,1),(1,1) (2,3),( ),Q,(1,1),(1,1) (2,3),( ),Q,Q,(1,1),(1,

9、1) (2,3),(1,1) (2,4),( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),Q,(1,1) (2,4) (3.2),( ),Q,Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),( ),Q,(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2)

10、,( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),Q,(1,2) (2,4) (3,1),( ),(1,1),(1,1) (2,3),(1,1) (2,4),(1,1) (2,4) (3.2),Q,(1,2),Q,(1,2) (2,4),Q,(1,2) (2,4) (3,1),Q,(1,2) (2,4) (3,1) (4,3),递归的思想,递归的思想

11、（续）,当前状态,目标状态g,递归过程伪码描述中用到的一些符号的含义：,变量： DATA=当前状态； RULES=规则集合序列表； R=当前调用规则； RDATA=新生成的状态； PATH=当前解路径表。 常量： NIL=空表； FAIL=回溯点标记； LOOP=循环标号。,谓词： TERM(DATA)；(DATA满足结束条件) DEADEND(DATA)；(DATA是非法状态) NULL(RULES)。(规则集合序列表空) 函数： RETURN 返回自变量的值； APPRULES 求可应用的规则表； FIRST 从表中取表头的一个元素； TAIL 除去表头的一个元素后得到新表； GEN 调用

12、规则生成新状态； CONS 在表头插入新元素，构造新表； BACKTRACK(RDATA) 递归过程作用于新状态。,BACKTRACK（DATA） DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。,回溯搜索算法,递归过程BACKTRACK(DATA),1. if TERM (DATA), return NIL； / 当DATA满足终止条件时，返回空表. if DEADEND (DATA), renturn FAIL； /当DATA状态不合法时，必须回溯。 3. RULES APPRULES(DATA) /DATA状态的可用规则加入规则集合序列表。

13、4. LOOP: if NULL(RULES), return FAIL； /如果规则集合序列表空，必须回溯。 5. R FIRST(RULES)； /读规则集合序列表的第一条规则到变量R。 6. RULES TAIL(RULES)； /从规则集合序列表删除被选中的规则。 7. RDATA GEN（R，DATA）； /被选中的规则作用于当前状态。 8. PATHBACKTRACK(RDATA)； /对新状态递归调用本过程 9. if PATH =FAIL, go LOOP； /如果递归失败，则用另一条规则 10. return CONS(R,PATH)； /否则把R加在解路径表中，向上传递成功

14、的 规则表，过程返回解路径规则表（或局部解 路径子表）,回溯搜索算法,解决办法： 对搜索深度加以限制 记录从初始状态到当前状态的路径,存在问题及解决办法,问题： 深度问题,死循环问题,对于可能出现重复状态且搜索深度无限的问题，必须设置深度范围限制及防止出现重复状态引起死循环这两个回溯点。 改进的算法如下 BACKTRACK1(DATALIST):,1 DATA FIRST(DATALIST) 2 if MEMBER(DATA,TAIL(DATALIST), return FAIL / / 有环路，回溯 3 if TERM(DATA), return NIL / / 到达目标，成功返回 4 if

15、 DEADEND(DATA), return FAIL / / 到达不合理状态，回溯 5 if LENGTH(DATALIST) BOUND, return FAIL / / 已到深度限制，回溯 6 RULES APPRULES(DATA) / / 得出可应用的规则集 7 LOOP: if NULL(RULES), return FAIL / / 进入死胡同，回溯 8 R FIRST(RULES) / / 取出第一条可应用规则 9 RULES TAIL(RULES) 10 RDATA GEN(R, DATA) / / 运用规则，生成新状态 11 RDATALIST CONS(RDATA, DATALIST) 12 PATH BACKTRACK1(RDATALIST) / / 递归 13 if PATH=FAIL, go LOOP 14 return CONS(R, PATH),问题的引出 回溯搜索：只保留从初始状态到当前状态的一条路径。 不能找出全部解,回溯搜索策略的问题,问题的引出 回溯搜索：只保