《3.用搜索方法进行问题求解概要》由会员分享，可在线阅读，更多相关《3.用搜索方法进行问题求解概要（38页珍藏版）》请在金锄头文库上搜索。
1、第三章、用搜索法对问题求解,1.问题求解Agent 2.问题实例 3.对解的搜索 4.无信息的搜索策略 5.避免重复状态,1.问题求解Agent,Agent在罗马尼亚城市Arad度假，假设它有张第二天飞离Bucharest的机票，而且机票是不能退的。 目标：前往Bucharest 任务：找出能够使它达到目标状态的动作序列 Q：决策所要考虑的行动和状态的种类？ A：在开车从一个主要城镇到另一个城镇的层次上考虑行动。 Agent设计的三步骤：形式化、搜索、执行。,简化的罗马尼亚地图,问题求解Agent的环境特性,可观察的 离散的 静态的 完成问题形式化和求解的时候不再考虑环境可能的变化 确定性的
2、问题的解是行动的单一序列 在问题求解过程中感知信息不起作用,一个简单的问题求解Agent,注意：我们假定总能找到解；Agent在执行行动序列时忽略感知。,问题的形式化定义,初始状态，例如In(Arad) 对问题可采纳的可能行动的描述，后继函数SUCCESSOR-FN(x)=set of all pairs 例如, In(Arad) 的一个后继状态是 . 状态空间图、路径 目标测试：具体vs.抽象 路径耗散函数：为每条路径分配一个数值化的耗散值。 以上四个要素作为问题求解算法的输入,问题的解,解是从初始状态到目标状态的路径 解的质量由路径耗散函数度量 最优解是路径耗散函数值最小的解,问题实例：真
3、空吸尘器,状态：Agent位置及灰尘位置。2*4=8个状态 初始态：任一状态都可作为初始态。 后继函数：Agent左右移动 目标测试：检测所有位置是否干净 路径耗散：每步的耗散值为1,问题实例：八角数码游戏,状态：8个棋子及其空格在棋盘上9个格子的分布 初始态：任一状态都可作为初始态，但要到达一特定的目标态，只有一半的状态可作为起点。 后继函数：用来产生通过4个行动（把空格向左、右、上、下移动）可到达的状态 目标测试：是否与目标状态一致 路径耗散：每步的耗散值为1,传教士与野人问题（M&C）,问题：有N个传教士，N个野人渡河，只有一条船且每次至多可坐K个人。 约束条件： MC 任何时刻两岸、船
4、上都必须满足传教士人数不少于野人数 （M=0时除外，既没有传教士） M+CK 船上人数限制在K以内 求解：传教士与野人全部安全渡河到对岸的解决方案。,传教士与野人问题（M&C）,状态：三元组（ML，CL，BL）表示左岸状态 初始态：（3，3，1）传教士、野人与船均在左岸 后继函数：Pmc：从左岸划向右岸； Qmc：从右岸划向左岸 目标测试：是否全部达到右岸 路径耗散：每步的耗散值为1,（3，3，1）,（2，2，0） （3，2，0） （3，1，0）,（3，2，1）,（3，0，0）,（3，1，1）,（1，1，0）,（2，2，1）,（0，2，0）,（0，3，1）,（0，1，0）,（0，2，1） （0
5、，1，1） （1，1，1）,（0，0，0）,P11,P02,Q10,Q01,状态空间图 状态空间图是一个有向图，图中的节点代表状态，节点之间的连线代表规则，箭头代表状态的转换方向。,问题实例：旅行问题,考虑访问罗马尼亚地图中的每个城市至少一次，要求以Bucharest为起点和终点。 每个状态必须包括当前城市和所有已访问过的城市 （典型的）路径耗散：里程数,一些很有意义的搜索问题,VLSI 布局 机器人导航: 机器人可在连续的空间上运动，而且可能的行动和状态集都是无限的。 蛋白质设计 Internet 搜索,搜索技术：显式搜索树,基本做法：先追随一个选择，搁置其它的，等到万一发现第一个选择不能通
6、向问题的解时再考虑。,一般的生成搜索树算法的描述,状态空间、搜索树、节点,一个状态空间可以有无数条路径，即搜索树可有无数个节点。 例如，从Arad到Sibiu的路径可包括重复出现的节点。 节点的数据结构 State Parent-Node Action Path-Cost（从初始状态到达该节点） Depth（从初始状态到达该节点）,边缘的基本操作,MAKE-QUEUE(element, )用给定的元素创建一个队列 EMPTY?(queue)当且仅当队列中没有元素时返回为真 FIRST(queue)返回队列中的第一个元素 REMOVE-FIRST(queue)返回FIRST(queue)并将它从
7、队列中删除 INSERT(element, queue)在队列中插入一个元素并返回结果队列 INSERT-ALL(element, queue)在队列中插入一个元素集合并返回结果队列,形式化的一般的树搜索算法,度量问题求解的性能,完备性：有解时能否保证找到解 最优性 时间复杂度：根据搜索过程中产生的节点数目来度量 空间复杂度：在执行搜索的过程中需要的内存，取决于储存的最大节点数。 时间与空间的复杂度往往要与问题难度的某种度量一起考虑,问题难度的度量：状态空间图的大小,分支因子b：任何节点的后继的最大个数 d：最浅的目标节点的深度 m：状态空间中任何路径的最大长度,3.2 图搜索策略 图搜索的实
8、质是从问题空间中找出一张包含目标节点的子图。 PROCEDRUE GRAPHSEARCH 1 GG0 (G0 S)，OPEN (S) S：初始状态 2 CLOSED ( ) 3 LOOP：if OPEN ( ) then EXIT(FAIL) 4 n FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED) 5 if GOAL(n) THEN EXIT(SUCCESS) 6 mi EXPAND(n) ，G ADD(mi,G) mi不含n的先辈节点 7 OPEN ADD(mj,OPEN) mj不在OPEN，CLOSED中 标记每个mj到n节点的指针 确定是否需要修改已在O
9、PEN，CLOSED中的每个节点到n的指针 确定是否需要修改已在CLOSED中的每个节点的后继节点原来的指针 8 按照某种方式重新排列OPEN表中的节点， GO LOOP,讨论： 1 OPEN中的节点是尚未扩充的节点 2 CLOSED的节点是已经扩充过的节点 3 G中的每个节点都唯一地指向一个父节点 4 mi mj mk ml 其中： mi是当前被扩充的全部节点 mj是新扩充的节点 mk是已经在OPEN中的节点 ml是已经在CLOSED中的节点 5 n是当前被选中的节点，它是OPEN表中排列在最前面的一个节点。 6 该算法对于连通图及树都适用。,例：,n=1,S,2,3,4,5,6,当前节点,
10、ml节点,讨论： 空心节点是已经在OPEN中的节点，如：1，4，5 实心节点是已经在CLOSED中的节点，如：S，2，3 扩充节点2后，对其原来搜索路径进行修改，由原来指向节点3改为指向节点1 对后继节点4的搜索路径进行修改，由原来指向节点6改为指向节点2,表示图本身的连接关系,搜索路径,修改后的搜索图如下：,n=1,S,2,3,4,5,6,下面给出两种对OPEN表中节点按照某种规则排列的算法： 深度优先算法 宽度优先算法,宽度优先算法,将待扩展节点按先入先出排队,宽度优先搜索（bfs） 1.当分支因子有限时，搜索是完备的 2.如果路径耗散是节点深度的非递减函数，则解是最优的。 3.假设每个状
11、态都有b个后继，解的深度是d，则找到解时，所访问过的节点数为O(bd+1)。,一致代价搜索,bfs算法的引伸：扩展路径耗散值最低的节点,S,D,A,E,B,C,F,t,八城市地图示意图,4,3,5,2,5,4,4,4,3,深度优先算法 1. 总是扩展搜索树的当前扩展分支(边缘)中最深的节点 2. 搜索直接伸展到搜索树的最深层，直到那里的节点没有后继节点 3. 那些没有后继节点的节点扩展完毕就从边缘中去掉 4. 然后搜索算法回退下一个还有未扩展后继节点的上层节点继续扩展,深度优先搜索过程,深度优先搜索算法分析,1.对内存的需求很少 2.有可能错误地选择一条分支而且沿着一条很长的路径（甚至是无限）
12、走下去。 非最优 非完备 在最坏情况下，dfs所生成的节点数是O(bm),深度有限搜索,深度优先搜索的无边界问题可以通过提供一个预先设定的深度限制l来解决,深度有限搜索,深度优先搜索的无边界问题可以通过提供一个预先设定的深度限制l来解决 深度=l的节点当作无后继节点看待 虽然解决了无限路径问题，但如果ld则深度优先搜索也不是最优的 时间复杂度O(bl) 空间复杂度O(bl) 深度优先搜索可看作是一种特例即l= 有时深度有限搜索基于问题本身的知识，如状态空间的直径即问题求解的最大步数 但对于大多数问题，不到问题解决时是无法知道求解步数的限制,迭代深入深度优先搜索,如果每次改变限制深度，多次调用深
13、度有限搜索算法，就得到了迭代深入深度优先搜索算法 其深度限制依次为0/1/2这样，当搜索到达最浅的目标节点深度时就可以发现目标节点 这种搜索结合了宽度优先和深度优先两种算法的优点 分支因子有限时是完备的 / 路径耗散是节点深度的非递增函数时是最优的 空间需求为O(bd) / 时间复杂性为O(bd),讨论 迭代深入搜索中因为多次重复搜索，因此部分状态被多次生成，看起来很浪费 但是因为在分支因子比较平衡的搜索树中，多数节点都在最底层(即叶子节点)，所以上层节点的多次生成影响不是很大 / 与广度优先搜索相比，效率还是更高 一般来讲，当搜索空间很大而解的深度未知时，迭代深入搜索是一个首选的无信息搜索方法,38,无信息搜索策略比较,关于A/B/C/D的解释： A如果b有限则是完备的 B单步耗散e则是完备的 C如果单步耗散都是相同的则是最优的 D两个方向上都使用广度优先搜索,
