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，,8，每个纸片都可以移进相邻的空格，8 数码难题的初始状态和目标状态分别列
3、出如下，问如何把这个问题由初始状态移向目标状态？,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 65 8 2,1 3 7 4 65 8 2,1 4 3 7 65 8 2,1 2 3 7 8 65 2,1 2 3 7 65 8 2,1 3 7 4 65 8 2,1 3 7 4 65 8 2
4、,1 4 3 1 7 65 8 2,1 4 3 5 7 68 2,1 4 3 7 8 6 5 2,1 4 3 7 8 65 2,1 4 37 6 35 8 2,1 4 3 7 6 25 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 的排列.,旅行推销员问题的搜索空间,E,A,D,C,B,C,D,E,A,E,D,A,D,C,E,A,E,100,125,100,75,150,1
5、75,425,225,325,275,375,300,250,1.1 回溯策略 回溯策略的主要思想:只保留从初始状态到当前状态的一条解路径,给变换状态的规则给出一个排序方法,对当前状态使用规则产生新的状态,不断地向前延伸解路径.当没有规则可用,或向前延伸的状态都是无解状态(称为死点,deadend)时,沿解路径后退到前一个状态(回溯),重新开始搜索,直至找到解或宣布失败.回溯策略是一种穷尽的搜索方法.,2.1 回溯算法Backtracking Strategies 递归过程A simple recursive procedure 输入:问题的初始状态.The input:the initial
6、 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 procedure BACKTRCK(DATA)1 if TERM(DATA),return NIL;2 if DEADEND(DATA),return FAIL;3 RULES
7、 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 get the list of rules using the function APPRULES,we need to order the rules in the lists.The ordering is very
8、 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 trymore rules,the efficiency of the system is poor.The Example of Backtracking procedure.The 4 queen problem,*,*,*,在利用AP
9、PRUKES 得到规则表之后,需要对表中的规则排序,把好的规则放在表的前面优先使用,这个排序对算法的效率有很大影响.,The problem representation the global database:4*4 array the rule:Rij If i=1:there are no queen in the array 1 i=4:There is a queen in the row i-1 then put a queen in the row i,column jWe order the rules according to the column.我们用Rij表示在棋盘的第
10、 i 行第 j 列放一个王后.按行的增加顺序依次放皇后,在规则的排序上依列的上升次序排序.Termination condition:there are 4 queens in the chess board,they can not kill each other.终止条件:4 皇后都放到棋盘上,且不能互相杀死.,Order of rules:R11,R12,R13,R14,R21,R22,R23,R24,deadend,deadend,deadend,deadend,deadend,deadend,deadend,deadend,deadend,deadend,There many bac
11、ktrack,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).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)d
12、iag(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 function 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
13、,2.1 Backtracking Strategies A simple recursive procedure The input of the procedure,DATA:the initial state.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 procedure BACKTRCK(DATALIST
14、)1 DATA FIRST(DATALIST);2 if MEMBER(DATA,TAIL(DATALIST),return FAIL;3 if TERM(DATA),return NIL;4 if 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 R(DATA);11 RDATALIST CONS(RDATA
15、,DATALIST);12 PATH BACKTRACK(RDATALIST);13 if PATH=FAIL,go LOOP;14 return CONS(R,PATH),1.2 图搜索策略graph-search strategies 回溯算法只包含一条探索路径,如果发现deadend节点或无规则可用时要退回来,因此可能产生把探索过的节点擦掉后又重新产生的现象.在图搜索算法中.将所有搜索过的状态用一个图(搜索图)记录下来,图的弧反映状态之间的关系.在图中选择节点加以扩展,直至把搜索图扩展到充分大,包含解路径在内.,The main idea of graph search,In the b
16、acktracking procedure,we preserve only a pathfrom the initial state to the current 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 relatio
17、n of their sequences.When we find some node(state)in the graph is suited 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,有向图中的有关概念，父亲节点，儿子节点，叶节点，路径，回路，有向树。,用有向图表示问题的状态空间是一种很自然的方式，节点代表状态描述，弧代表状态之间的转移。但是，问题的状
18、态描述与有向图又有许多本质上的不同，需要引起我们注意：1。图论中研究的有向图是有限的，我们可以把有向图全部画出来。而人工智能中描述问题的有向图一般说来是无限的，或者说虽然有限，但是非常大，我们不可能将其画出来。2。图论中的问题求解是在对图完全了解的情况下进行。而我们对状态空间搜索解的过程是边产生图边求解，这里所产生的图是表示状态空间的无限图的显式部分，从求解的效率 考虑，就有把这个无限图的显式部分向哪个方向以何种方式扩展的问题。,Motivation:the limitation of backtracking procedureSometimes,after analyzing we nee
19、d to reproduce some states again.,DB1,DB2,DB3,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,问题的状态和它们之间的关系可以用一个图隐含地加以描述.状态用图的节点表示,状态之间
20、的关系用图中的弧表示.the states and their relations 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 i
21、mplicitly defined by production 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
22、 procedure GRAPHSEARCH input:the production system(the initial nose,production rule,goal node)output:the solution path from the initial node to a goal node,Procedure GRAPHSEARCHG=s,OPEN=(s);G为搜索图,初始化为问题的初始状态s,建立OPEN表,初始化为只含初始状态s.CLOSED=(),建立CLOSED表,初始化为空表.LOOP:IF OPEN=(),THEN EXIT(FAIL)n=FIRST(OPEN)
23、,REMOVE(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表中的节点按某种原则重新排序.9.GO L
24、OOP.,对 GRAPHSEARCH算法的几点说明:两个图,G:搜索图,它是记录算法访问过的所有节点的图,初始化为问题的初始状态s,在搜索过程中不断地扩展.T:G的有向支撑树,与G有同样的节点,由指针定义.记录由该节点到s的最短路径,在搜索过程中需要不断调整.2.两个表:OPEN和CLOSED,OPEN表记录搜索图的前沿,CLOSED表记录已经扩展过的节点.3.树T的指针的建立和调整.树T中节点的指针记录从该节点到初始节点s的最短路径,随着算法的进行,图的扩展,这些指针需要不断地调整.对新产生的节点,为其建立指针.对OPEN和CLOSED表中的节点,需要考虑调整其指针,对于CLOSED表中节点
25、,还需要考虑调整其后继节点的指针.,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 nodesas the graph G,his arc(only one outgoing arc from
26、 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,from which,we select a node to expand.CLOSED the interior no
27、des 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 need to consider to readjust their pointers.For the nodes of CLOSED,we ne
28、ed 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 无信息的图搜索过程 深度优先和宽度优先 深度优先和宽度优先的思想在数据结构中已经讲过,在数据结构中是作为树的遍历的方法讲的,人工智能中在状态空间中搜索解的过程也类似于遍历.所不同的是这里搜索的是图而不是树.所以这里我们只讨论与解有关的问题 宽度优先在搜索解的过程中总是在探索了层数小于或等于n的节点之
29、后才进入到n+1层节点的探索,所以这中方法获得的解具有最短的解路径.但如果图的分枝系数很高,或者解路径很长,效率会很低.深度优先可以很快地使实验解路径延伸到很长,如果刚好在延伸的过程中遇到解,这种方法的效率会很高,但不能保证找到有最短的解路径.甚至即使在原问题有解的时候,也会发生会在错误的方向上无限延伸下去而找不到解的情况,深度优先算法Procedure DEPTH-FIRTST SEARCH1 G=s,OPEN=(s),CLOSED=().2 LOOP:IF OPEN=(),THEN EXIT(FAIL)n=FIRST(OPEN);4 IF GOAL(n)THEN EXIT(SUCCESS)
30、;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,P3,T,S,K,K,L,M,N,goal,为保证深度优先算法在问题有解的情况下总能找到解,需要增加深度限制,而且深度限制必须超过解的长度.,1.4 启发式搜索4。0 简介 heuristicOf or relatin
31、g to a usually speculative formulation serving as a guide in the investigation or solution of a problem:探索的,做为调查或解决问题的向导的一种通常为推测性系统阐述 回溯式搜索，深度优先和宽度优先都不使用领域知识，效率很低。启发式搜索使用关于领域的信息指导，使搜索向着有利于获得解的方向进展。如果应用得好，可以明显地缩小搜索空间，提高搜索效率 例如，在九宫游戏中使用启发式搜索，就可以显著地减少搜索空间,MIN,MAX,在九宫游戏中使用启发式搜索：使用启发函数 h(s)=MAX 已投下的子可以占据
32、的行，列和对角线数,MIN,MAX,5,4,4,3,2,4,3,4,4,4,5,启发式搜索算法 最佳优先搜索。根据启发函数对尚为探索的节点进行排序，把最有希望的节点排再前面，在扩展节点时把最有希望的节点拿出来考虑。最佳优先搜索算法 function best-first-search 算法保存 2 个表，一个是open表，记录已经产生但尚未探索的节点，另一个是closed 表，记录已经探索过的节点，算法把新产生的节点加入到open 表中，然后按启发函数值将它们排序，把最有希望的节点排在前面，选出来加以测试和扩展,启发式搜索算法A评价函数 依据领域知识，对状态空间的状态的好坏程度的度量。通常使用
33、的评价函数为：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算法Procedure A1 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 31 6 47 5,2 8 31 6
