第1章搜索问题ppt课件.ppt

《第1章搜索问题ppt课件.ppt》由会员分享，可在线阅读，更多相关《第1章搜索问题ppt课件.ppt（73页珍藏版）》请在三一文库上搜索。

1、第 1 章 搜索问题,什么是状态空间？ 回溯策略。 图搜索策略 无信息的图搜索策略 启发式图搜索策略 A*算法。 A*算法的性质。 搜索算法的讨论。,状态空间,计算机对传统的问题求解方法带来了根本性的改变。 传统方法， 由专家给出公式， 使用者的任务是理解公式， 应用公式。 有些问题用传统方法描述很困难, 例如本节的几个例子 公式的推导需要很高的水平， 与实际问题相差较远，对应用者要求很高。 2. 计算机利用自己强大的计算能力和存储能力, 采用”猜”的方式, 试探法. 能解决问题的领域更广, 更结合实际.,例 智力游戏问题：传教士与野人渡河问题,传教士与野人渡河问题：有 3 个传教士带 3 个

2、野人渡河，河的岸边有一条船， 每次最多可载 2 人，要求无论在河的哪一边，野人的数目不能超过传教士的数目，问为安全起见， 应如何安排传教士与野人渡河？ 一种较为简单的表示方式3 元向量（x, y, z） x: 河此岸的传教士数， y: 河此岸的野人数。 x,y 取值范围0，1，2，3 z: 船在此岸，z取值范围0，1,初始状态： （3，3，1） 目标状态： （0，0，0）,2,8,3,1,6,4,7,5,1,2,3,8,6,4,7,5,初始状态Initial 目标状态 Goal,例 设有 8 数码难题如下:在 33 的框架中有 8 个标有数字的硬纸片， 这些硬纸片上标的数字分别是 1， 2，

3、, 8， 每个纸片都可以移进相邻的空格， 8 数码难题的初始状态和目标状态分别列出如下，问如何把这个问题由初始状态移向目标状态？,2,8,3,1,6,4,7,5,1,2,3,8,6,4,7,5,Initial Goal,8 数码难题（8-puzzle）的矩阵描述,对于8 数码难题， 我们选用直接的矩阵描述，解题过程中的任何一个中间情况都对应一个 3*3的矩阵， 用0,1，2，, 8这9个数的一个排列依次去充填这个矩阵的各个单元,就是求解问题的一个可能的情况, 共有 9!种。,1 4 3 7 6 5 8 2,1 3 7 4 6 5 8 2,1 4 3 7 6 5 8 2,1 2 3 7 8 6

4、5 2,1 2 3 7 6 5 8 2,1 3 7 4 6 5 8 2,1 3 7 4 6 5 8 2,1 4 3 1 7 6 5 8 2,1 4 3 5 7 6 8 2,1 4 3 7 8 6 5 2,1 4 3 7 8 6 5 2,1 4 3 7 6 3 5 8 2,1 4 3 7 6 2 5 8,例 旅行推销员问题,A,B,D,C,E,75,100,125,125,50,100,50,75,125,100,125,问题表示, 形式为(A*)的字符串和(A*A)的字符串。 其中*为B,C, D, E 的排列. 问题的节，形式为(A*A)的字符串, 其中*为B,C, D, E 的排列.,旅行

5、推销员问题的搜索空间,E,A,D,C,B,C,D,E,A,E,D,A,D,C,E,A,E,100,125,100,75,150,175,425,225,325,275,375,300,250,1.1 回溯策略 回溯策略的主要思想: 只保留从初始状态到当前状态的一条解路径, 给变换状态的规则给出一个排序方法, 对当前状态使用规则产生新的状态, 不断地向前延伸解路径. 当没有规则可用, 或向前延伸的状态都是无解状态(称为死点,deadend)时, 沿解路径后退到前一个状态(回溯), 重新开始搜索, 直至找到解或宣布失败. 回溯策略是一种穷尽的搜索方法.,2.1 回溯算法Backtracking S

6、trategies 递归过程A simple recursive procedure 输入: 问题的初始状态. . The input: the initial state. 输出:一个规则表. 应用这个规则表可以把初始状态变为目标状态. 否则回答FAIL. The output of the procedure, a list of rules, using it we can get the goal from the initial state. If the procedure can not find the solution, it return FAIL.,Recursive p

7、rocedure BACKTRCK(DATA) 1 if TERM(DATA), return NIL; 2 if DEADEND(DATA), return FAIL; 3 RULES APPRULES(DATA);,4 LOOP: if NULL(RULES), return FAIL; 5 R FIRST(RULES); 6 RULES TAIL(RULES); 7 RDATA R(DATA); 8 PATH BACKTRACK( RDATA); 9 if PATH = FAIL , go LOOP; 10 return CONS( R, PATH),In step 3, after g

8、et the list of rules using the function APPRULES, we need to order the rules in the lists. The ordering is very important. If the “better” rule is put in the front of the list, it can be used firstly, the efficiency of the system is high. If the “worse” rule is put in the front, the system needs to

9、try more rules, the efficiency of the system is poor. The Example of Backtracking procedure. The 4 queen problem,*,*,*,在利用APPRUKES 得到规则表之后, 需要对表中的规则排序, 把好的规则放在表的前面优先使用, 这个排序对算法的效率有很大影响.,The problem representation the global database: 4*4 array the rule: Rij If i= 1 : there are no queen in the array

10、1 i= 4: There is a queen in the row i-1 then put a queen in the row i, column j We order the rules according to the column. 我们用Rij表示在棋盘的第 i 行第 j 列放一个王后. 按行的增加顺序依次放皇后, 在规则的排序上依列的上升次序排序. Termination condition: there are 4 queens in the chess board, they can not kill each other. 终止条件: 4 皇后都放到棋盘上, 且不能互相

11、杀死.,Order of rules: R11, R12, R13, R14,R21, R22, R23,R24,deadend,deadend,deadend,deadend,deadend,deadend,deadend,deadend,deadend,deadend,There many backtrack,NIL (),(R43),(R31,R43),(R24,R31,R43),(R12,R24,R31,R43),We can use more informed rule ordering using function diag(i,j) 我们可以采用含有较多信息的函数diag(i,j

12、) . Diag(i,j) = the length of the longest diagonal passing through cell(i,j) diag(i,j) 是通过单元(i, j)的最长对角线的长度, 我们按diag(i,j)排序, we order Rmn before Rij, if diag(m,n) diag(i,j) Rin before Rij, If diag(i,n) = diag(i,j) and nj Homework: Solve the 4 queens problem by using backtracking procedure and functi

13、on diag BACKTRACK1: to avoid cycle 1. The argument of the procedure is changed, from a single state to a list of state. 2. Use MEMBER function to check cycle. 3. Add depth bound,2.1 Backtracking Strategies A simple recursive procedure The input of the procedure, DATA : the initial state. The output

14、of the procedure, a list of rules, using it we can get the goal from the initial state. If the procedure can not find the solution, it return FAIL.,Recursive procedure BACKTRCK(DATALIST) 1 DATA FIRST(DATALIST); 2 if MEMBER(DATA, TAIL(DATALIST), return FAIL; 3 if TERM(DATA), return NIL; 4 if DEADEND(

15、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 R(DATA); 11 RDATALIST CONS( RDATA, DATALIST); 12 PATH BACKTRACK( RDATALIST); 13 if PATH = FAIL , go LOOP; 14 return CONS( R, PATH

16、),1.2 图搜索策略graph-search strategies 回溯算法只包含一条探索路径, 如果发现deadend节点或无规则可用时要退回来, 因此可能产生把探索过的节点擦掉后又重新产生的现象. 在图搜索算法中.将所有搜索过的状态用一个图(搜索图)记录下来, 图的弧反映状态之间的关系.在图中选择节点加以扩展, 直至把搜索图扩展到充分大, 包含解路径在内.,The main idea of graph search,In the backtracking procedure, we preserve only a path from the initial state to the cu

17、rrent state, so sometimes we need to product some states again after the states were removed. However, in graph search method, We preserve a graph in the memory, the graph include all the states we passed through and the relation of their sequences. When we find some node(state) in the graph is suit

18、ed to expand for search, we expand it, continue our searching, until a solution is finded.,图论与状态空间表示 有向图 G是一个偶对(N, E), 其中 N 是节点集合，E是有向弧的集合。,D,E,C,B,A,有向图中的有关概念，父亲节点， 儿子节点， 叶节点，路径， 回路， 有向树。,用有向图表示问题的状态空间是一种很自然的方式， 节点代表状态描述， 弧代表状态之间的转移。 但是， 问题的状态描述与有向图又有许多本质上的不同， 需要引起我们注意： 1。 图论中研究的有向图是有限的，我们可以把有向图全部画

19、出来。而人工智能中描述问题的有向图一般说来是无限的， 或者说虽然有限， 但是非常大，我们不可能将其画出来。 2。图论中的问题求解是在对图完全了解的情况下进行。而我们对状态空间搜索解的过程是边产生图边求解， 这里所产生的图是表示状态空间的无限图的显式部分， 从求解的效率 考虑， 就有把这个无限图的显式部分向哪个方向以何种方式扩展的问题。,Motivation: the limitation of backtracking procedure Sometimes, after analyzing we need to reproduce some states again.,DB1,DB2,DB3

20、,DB4,R1,R2,R3,2.2 graph-search strategies,Motivation: the limitation of backtracking procedure Sometimes, after analyzing we need to reproduce some states again.,DB1,DB4,R2,DB1,DB2,DB4,R1,R2,DB1,DB2,DB3,DB4,R1,R2,R3,问题的状态和它们之间的关系可以用一个图隐含地加以描述. 状态用图的节点表示, 状态之间的关系用图中的弧表示. the states and their relation

21、s are defined by a graph implicitly: states nodes rule applications arcs 但是, 我们也应该注意到它们之间的区别: However, generally the graph is endless , We can not draw the graphsin ordinary way.,Starting from the initial state, we generate an sub-graph(an explicit part of the graph implicitly defined by production

22、system), then we select the node in the sub-graph to expand it, if the sub-graph does not contain the goal node, we continue to expand it, until the sub-graph is large enough to include the goal node , and we find the solution path from the initial node to the goal node. The procedure GRAPHSEARCH in

23、put : the production system(the initial nose, production rule, goal node) output: the solution path from the initial node to a goal node,Procedure GRAPHSEARCH G=s, OPEN=(s); G为搜索图, 初始化为问题的初始状态s, 建立OPEN表,初始化为只含初始状态s. CLOSED = (),建立CLOSED表,初始化为空表. LOOP: IF OPEN=(), THEN EXIT(FAIL) n=FIRST(OPEN), REMOV

24、E(n, OPEN), ADD(n, CLOSED); 称n为当前节点. IF GOAL(n) THEN EXIT(SUCCESS); 由n循指针返回s, 可以获得解路径. EXPAND(n)mi, G=ADD(mi, G), 子节点集mi中不包含n的父辈节点.,7 标记和修改指针 ADD(mj, OPEN), 并标记mj连接到n的指针, mj是未在OPEN和CLOSED中出现过的子节点. 计算是否需要修改mk, ml到n的指针; mk是出现在OPEN表中的子节点, ml是出现在CLOSED表中的子节点, Mi=MjMkMl 计算是否需要修改mi到其后记节点的指针. 8.对OPEN表中的节点按

25、某种原则重新排序. 9.GO LOOP.,对 GRAPHSEARCH算法的几点说明: 两个图, G: 搜索图, 它是记录算法访问过的所有节点的图,初始化为问题的初始状态s, 在搜索过程中不断地扩展. T: G的有向支撑树, 与G有同样的节点, 由指针定义. 记录由该节点到s的最短路径, 在搜索过程中需要不断调整. 2. 两个表: OPEN和CLOSED, OPEN表记录搜索图的前沿, CLOSED表记录已经扩展过的节点. 3. 树T的指针的建立和调整. 树T中节点的指针记录从该节点到初始节点s的最短路径, 随着算法的进行, 图的扩展, 这些指针需要不断地调整. 对新产生的节点, 为其建立指针.

26、 对OPEN和CLOSED表中的节点, 需要考虑调整其指针, 对于CLOSED表中节点, 还需要考虑调整其后继节点的指针.,Notes about the procedure GRAPHSEARCH 1. Two graphs: G: The explicit part of the graph generated by the production system, its initial node is the initial state, it is expanded constantly. T: the directed support tree of G, it has same no

27、des as the graph G, his arc(only one outgoing arc from a node) direct the shortest path from one node to another node. The arcs are marked by pointers. In order to preserve the character, the procedure need to readjust the arcs of the tree constantly.,2. Two list: OPEN the frontier nodes of graph G,

28、 from which, we select a node to expand. CLOSED the interior nodes of graph G, the node have been expanded. 3. The establishment and readjustment of the pointers of tree T. For the newly generated nodes, we need to establish the pointer for them. For the nodes in the lists on OPEN and CLOSED , we ne

29、ed to consider to readjust their pointers. For the nodes of CLOSED, we need to consider the readjustment of their descendants, for the adjustment of the nodes of CLOSED may influence their descendants pointers,s,1,2,1,2,1.3 无信息的图搜索过程 深度优先和宽度优先 深度优先和宽度优先的思想在数据结构中已经讲过, 在数据结构中是作为树的遍历的方法讲的, 人工智能中在状态空间中搜

30、索解的过程也类似于遍历. 所不同的是这里搜索的是图而不是树.所以这里我们只讨论与解有关的问题 宽度优先在搜索解的过程中总是在探索了层数小于或等于n的节点之后才进入到n+1层节点的探索, 所以这中方法获得的解具有最短的解路径.但如果图的分枝系数很高, 或者解路径很长,效率会很低. 深度优先可以很快地使实验解路径延伸到很长, 如果刚好在延伸的过程中遇到解, 这种方法的效率会很高, 但不能保证找到有最短的解路径. 甚至即使在原问题有解的时候, 也会发生会在错误的方向上无限延伸下去而找不到解的情况,深度优先算法 Procedure DEPTH-FIRTST SEARCH 1 G=s, OPEN=(s)

31、, CLOSED = (). 2 LOOP: IF OPEN=(), THEN EXIT(FAIL) n=FIRST(OPEN); 4 IF GOAL(n) THEN EXIT(SUCCESS); 5 REMOVE(n, OPEN), ADD(n, CLOSED); 6 EXPAND(n)mi, G=ADD(mi, G); ADD(mi, OPEN), 并标记mi到n的指针, 把不在OPEN和 CLOSED 中的节点放在最前面, 使深度大的节点可以优先扩展. 8 GO LOOP,使用 DEPTH-FIRST-SEARCH搜索的例,D6,C4,B4,A5,H3,G4,F5,E5,O2,J,I,K

32、,P3,T,S,K,K,L,M,N,goal,为保证深度优先算法在问题有解的情况下总能找到解, 需要增加深度限制, 而且深度限制必须超过解的长度.,1.4 启发式搜索 4。0 简介 heuristic Of or relating to a usually speculative formulation serving as a guide in the investigation or solution of a problem: 探索的,做为调查或解决问题的向导的一种通常为推测性系统阐述 回溯式搜索， 深度优先和宽度优先都不使用领域知识， 效率很低。 启发式搜索使用关于领域的信息指导， 使

33、搜索向着有利于获得解的方向进展。如果应用得好，可以明显地缩小搜索空间， 提高搜索效率 例如， 在九宫游戏中使用启发式搜索， 就可以显著地减少搜索空间,MIN,MAX,在九宫游戏中使用启发式搜索： 使用启发函数 h(s) = MAX 已投下的子可以占据的行， 列和对角线数,MIN,MAX,5,4,4,3,2,4,3,4,4,4,5,启发式搜索算法 最佳优先搜索。 根据启发函数对尚为探索的节点进行排序， 把最有希望的节点排再前面， 在扩展节点时把最有希望的节点拿出来考虑。 最佳优先搜索算法 function best-first-search 算法保存 2 个表， 一个是open表， 记录已经产生

34、但尚未探索的节点， 另一个是closed 表， 记录已经探索过的节点， 算法把新产生的节点加入到open 表中， 然后按启发函数值将它们排序， 把最有希望的节点排在前面， 选出来加以测试和扩展,启发式搜索算法A 评价函数 依据领域知识， 对状态空间的状态的好坏程度的度量。 通常使用的评价函数为： f(n)=g(n)+h(n) g*(n) 初始节点到节点 n 的距离. h*(n) 节点 n 到目标节点g 的距离. f*(n)=g*(n)+h*(n), 从初始节点到目标节点 g 的距离. f(n),g(n),h(n)分别是 f*(n), g*(n), h*(n)的估计值.,A算法 Procedur

35、e A 1 G=s, OPEN=(s), CLOSED = (). 2 LOOP: IF OPEN=(), THEN EXIT(FAIL) 3 n=FIRST(OPEN); 4 IF 4 IF GOAL(n) THEN EXIT(SUCCESS); 5 REMOVE(n, OPEN), ADD(n, CLOSED); EXPAND(n)mi, G=ADD(mi, G); 建立和调整指针, 计算各节点的f 值. 并按各点的f值调整指针. 7 把OPEN表中的节点按f值从小到大排序. 8 GO LOOP,2 8 3 1 6 4 7 5,2 8 3 1 6 4 7 5,2 8 3 1 4 7 6 5

36、,2 8 3 1 6 4 7 5,4,1+5=6,1+3=4,1+5=6,1 2 3 8 4 7 6 5,目标状态,h 值是偏离目标位置的块数W(n),2 8 3 1 6 4 7 5,2 8 3 1 6 4 7 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 7 8 4 6 5,8 3 2 1 4 7 6 5,2 8 3 7 1 4 6 5,

37、1,2,3,4,5,Goal node,6,s4,A6,B4,C6,D5,E5,F6,G6,H7,I5,J7,K5,L5,M7,7,初始化. Open = s4; closed = 1. 测试s4, Open = B4, A6, C6; closed = s4 2. 测试B4, Open = D5, E5,A6, C6, F6; closed = s4, B4 3. 测试D5, Open = E5,A6, C6, F6,G6, H7; closed = s4, B4, D5 4. 测试E5, Open = I5,A6, C6, F6,G6, H7, J7; closed = s4, B4, D

38、5,E5 5. 测试I5, Open = K5,A6, C6, F6,G6, H7, J7; closed = s4, B4, D5,E5, I5 6. 测试K5, Open = L5,A6, C6, F6,G6, H7, J7, M7; closed = s4, B4, D5,E5, I5,K5 7. L = goal, 成功找到了解,2 8 3 1 6 4 7 5,2 8 3 1 6 4 7 5,2 8 3 1 4 7 6 5,2 8 3 1 6 4 7 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2 8 3 1 4 7 6 5,2 3 1 8 4 7 6 5,2

39、3 1 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 8 4 7 6 5,1 2 3 7 8 4 6 5,8 3 2 1 4 7 6 5,2 8 3 7 1 4 6 5,1,2,3,4,5,Goal node,6,4,4,6,4,6,5,5,6,6,7,5,7,5,5,7,7,2 8 3 1 6 4 7 5,2 8 3 1 6 4 7 5,Closed表中的节点,open表中的节点,选择节点 D 扩展时的 Open表和closed 表,2. 爬山法 f(n)=h(n),分支界限法 f(n)=g(n) 4. 动态规划法 对分支界限法的改进, 如果有多条到达某一节点的路径, 只保

40、留费用最小的一条.,分支界限法,s,D,A,E,F,t,B,C,3,2,5,3,4,5,4,4,设有 7 城市, 城市之间的距离如图, 求从s到t的最短通路,分支界限法,s,D,A,1,g=0,2,g=3,3,g=4,分支界限法,s,D,A,1,g=0,2,g=3,3,g=4,D,B,5,g=7,6,g=8,分支界限法,s,D,A,1,g=0,2,g=3,3,g=4,D,B,5,g=7,6,g=8,E,A,7,g=9,4,g=6,分支界限法,s,D,A,1,g=0,2,g=3,3,g=4,D,B,5,g=7,6,g=8,E,A,7,g=9,4,g=6,B,g=11,g=13,F,10,9,分支

41、界限法,s,D,A,1,g=0,2,g=3,3,g=4,D,B,5,g=7,6,g=8,E,A,7,g=9,4,g=6,E,C,g=11,g=12,11,12,10,9,B,g=11,g=13,F,分支界限法,s,D,A,1,g=0,2,g=3,3,g=4,D,B,5,g=7,6,g=8,E,A,7,g=9,4,g=6,E,C,g=11,g=12,B,E,g=10,g=11,B,g=13,F,D,F,B,F,A,C,t,g=14,g=16,g=15,g=14,g=15,g=15,g=13,11,12,8,10,9,动态规划法,s,D,A,1,g=0,2,g=3,3,g=4,D,B,5,g=7,

42、6,g=8,E,A,7,g=9,4,g=6,E,C,B,g=11,F,g=10,t,g=14,g=13,11,12,10,9,5. 最佳图搜索算法A* 在启发式搜索中使用评估函数 f(n) = g(n) + h(n) 其中， g(n) 是从初始状态到 n 费用； h(n)是从 n 到目标的启发式估计费用 把使用这种估值函数的启发式程序叫做A算法。 如果状态空间的图搜索问题存在解路径， 搜索算法 f 一定能找到该问题的最优解路径， 则称算法 f 是可采纳的。 如果在A算法中使用的启发函数满足 h(n) h*(n) 则称之为 A* 算法。,A*算法是可采纳的 若存在从初始节点s到目标节点t的路径，

43、 则A*算法必能找到最佳解路径。 例如， 在宽度优先搜索中， h(n) 0，满足 h(n) h*(n) ， 是可采纳的。 和前面举例的f(n) = g(n) + h(n)中， h(n)取为偏离目标位置的块数， 满足h(n) h*(n) ，也是可采纳的。,单调性 在算法 A 中， g(n)是 g*(n) 的估计值， 定义为在已经产生的节点中从初始节点到 n 的最短路径的费用， 在算法进行的过程中， 我们需要不断地计算， 比较和调整这条最短路径， 这要消耗大量的计算时间，因而也影响算法的效率，如果能对启发函数增加某些限制条件， 使得在这种限制条件下，理论上就可以证明 g(n) 就是 g*(n),

44、则为获得 g(n)所需要的计算就可以省略了。 这个条件就是单调性。 定义： 单调性 启发函数单调的条件是： 1。 对于所有的状态ni和nj， 其中nj是ni的后继 h(ni) - h(nj) cost(ni, nj) cost(ni, nj)是节点ni和nj之间的实际最小费用 2。 h(goal) = 0,启发函数的比较 设有两个算法， 分别使用两个启发函数 算法1， f1(n) = g1(n) + h1(n) 算法2， f2(n) = g2(n) + h2(n) 哪一个更好一些呢？ 定义 信息度 对于两个A*启发式函数h1(n)和 h2(n)， 如果对于搜索空间中的所有的节点 n, 都有 h

45、1(n) h2(n) 则称h2(n) 比 h1(n)有更高的信息度。 如果h2(n) 比 h1(n)有更高的信息度， 则算法2所扩展的节点一定会被算法1所扩展， 换句话说， 算法2所扩展的节点比算法1扩展的节点少。,A*算法的应用举例. (1) 8 数码问题 h(n) = P(n), P(n)为每一方块与目标位置的距离的总和. (2) 传教士与野人问题 h(n)=0 h(n)=M+C h(n)=M+C-2B,传教士与野人渡河问题：有 N 个传教士带 N 个野人渡河，河的岸边有一条船， 每次最多可载 K 人，要求无论在河的哪一边，或是在船上，野人的数目不能超过传教士的数目，问为安全起见， 应如何安排传教士与野人渡河？ N=5， K=3。,2 8 3