人工智能搜索问题(PPT 73页)35452.pptx

《人工智能搜索问题(PPT 73页)35452.pptx》由会员分享，可在线阅读，更多相关《人工智能搜索问题(PPT 73页)35452.pptx（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、,更结合实际.人工智能吉林大学珠海学院计算机科学与技术系例 智力游戏问题：传教士与野人渡河问题 传教士与野人渡河问题：有 3 个传教士带 3 个野人渡河，河的岸边有一条船，每次最多可载 2 人，要求无论在河的哪一边，野人的数目不能超过传教士的数目，问为安全起见，应如何安排传教士与野人渡河？一种较为简单的表示方式3 元向量（x,y,z）x:河此岸的传教士数，y:河此岸的野人数。x,y 取值范围0，1，2，3 z:船在此岸，z取值范围0，1 人工智能吉林大学珠海学院计算机科学与技术系初始状态：（3，3，1）目标状态：（0，0，0）2831 647512386475初始状态Initial 目标状态

3、Goal例 设有 8 数码难题如下:在 33 的框架中有 8 个标有数字的硬纸片，这些硬纸片上标的数字分别是 1，2，,8，每个纸片都可以移进相邻的空格，8 数码难题的初始状态和目标状态分别列出如下，问如何把这个问题由初始状态移向目标状态？人工智能吉林大学珠海学院计算机科学与技术系2831 647512386475Initial Goal8 数码难题（8-puzzle）的矩阵描述 对于8 数码难题，我们选用直接的矩阵描述，解题过程中的任何一个中间情况都对应一个 3*3的矩阵，用0,1，2，,8这9个数的一个排列依次去充填这个矩阵的各个单元,就是求解问题的一个可能的情况,共有 9!种。人工智能吉

4、林大学珠海学院计算机科学与技术系1 4 3 7 65 8 21 3 7 4 65 8 21 4 3 7 65 8 21 2 3 7 8 65 21 2 3 7 65 8 2 1 3 7 4 65 8 21 3 7 4 65 8 21 4 3 1 7 65 8 21 4 3 5 7 68 21 4 3 7 8 6 5 21 4 3 7 8 65 21 4 37 6 35 8 21 4 3 7 6 25 8 人工智能吉林大学珠海学院计算机科学与技术系例 旅行推销员问题ABDCE75100125125501005075125100125问题表示,形式为(A*)的字符串和(A*A)的字符串。其中*为B

5、,C,D,E 的排列.问题的节，形式为(A*A)的字符串,其中*为B,C,D,E 的排列.人工智能吉林大学珠海学院计算机科学与技术系旅行推销员问题的搜索空间EADCBCDEAEDADCEAE10012510075150175425225325275375300250人工智能吉林大学珠海学院计算机科学与技术系1.1 回溯策略 回溯策略的主要思想:只保留从初始状态到当前状态的一条解路径,给变换状态的规则给出一个排序方法,对当前状态使用规则产生新的状态,不断地向前延伸解路径.当没有规则可用,或向前延伸的状态都是无解状态(称为死点,deadend)时,沿解路径后退到前一个状态(回溯),重新开始搜索,直

6、至找到解或宣布失败.回溯策略是一种穷尽的搜索方法.人工智能吉林大学珠海学院计算机科学与技术系 2.1 回溯算法Backtracking Strategies 递归过程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 procedu

7、re 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 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

8、=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 important.If the “better”rule is put in the front of the list,it can be used firstly,the efficiency of the system is

9、 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 *在利用APPRUKES 得到规则表之后,需要对表中的规则排序,把好的规则放在表的前面优先使用,这个排序对算法的效率有很大影响.人工智能吉林大学珠海学院计算机科学与技术系The problem representation the global data

10、base: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表示在棋盘的第 i 行第 j 列放一个王后.按行的增加顺序依次放皇后,在规则的排序上依列的上升次序排序.Termination condition:there are 4 queens in the chess bo

11、ard,they can not kill each other.终止条件:4 皇后都放到棋盘上,且不能互相杀死.人工智能吉林大学珠海学院计算机科学与技术系Order of rules:R11,R12,R13,R14R21,R22,R23,R24deadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadend deadendThere many backtrackNIL ()(R43)(R31,R43)(R24,R31,R43)(R12,R24,R31,R43)人工智能吉林大学珠海学院计算机科学与技术系We can use more

12、 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)diag(i,j)Rin before Rij,If diag(i,n)=diag(i,j)and n BOUND,return FAIL;6 RULES

13、 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)人工智能吉林大学珠海学院计算机科学与技术系1.2 图搜索策略graph-search strategiesgraph-search

14、strategies 回溯算法只包含一条探索路径,如果发现deadend节点或无规则可用时要退回来,因此可能产生把探索过的节点擦掉后又重新产生的现象.在图搜索算法中.将所有搜索过的状态用一个图(搜索图)记录下来,图的弧反映状态之间的关系.在图中选择节点加以扩展,直至把搜索图扩展到充分大,包含解路径在内.人工智能吉林大学珠海学院计算机科学与技术系The main idea of graph searchIn the backtracking procedure,we preserve only a pathfrom the initial state to the current state,s

15、o 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 suited to expand for sea

16、rch,we expand it,continue our searching,until a solution is finded.人工智能吉林大学珠海学院计算机科学与技术系图论与状态空间表示 有向图 G是一个偶对(N,E),其中 N 是节点集合，E是有向弧的集合。DECBA有向图中的有关概念，父亲节点，儿子节点，叶节点，路径，回路，有向树。人工智能吉林大学珠海学院计算机科学与技术系用有向图表示问题的状态空间是一种很自然的方式，节点代表状态描述，弧代表状态之间的转移。但是，问题的状态描述与有向图又有许多本质上的不同，需要引起我们注意：1。图论中研究的有向图是有限的，我们可以把有向图全部画出来

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

18、 DB2 DB3 DB4R1R2R3人工智能吉林大学珠海学院计算机科学与技术系2.2 graph-search strategies2.2 graph-search strategiesMotivation:the limitation of backtracking procedure Sometimes,after analyzing we need to reproduce some states again.DB1 DB4R2人工智能吉林大学珠海学院计算机科学与技术系 DB1 DB2 DB4R1R2 DB1 DB2 DB3 DB4R1R2R3人工智能吉林大学珠海学院计算机科学与技术系问

19、题的状态和它们之间的关系可以用一个图隐含地加以描述.状态用图的节点表示,状态之间的关系用图中的弧表示.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 st

20、ate,we generate an sub-graph(an explicit part of the graph implicitly 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

21、the solution path from the initial node to the goal node.The 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 GRAPHSEARCH1G=s,OPEN=(s);G为搜索图,初始化为问题的初始状态s,建立OPEN表,初

22、始化为只含初始状态s.2.CLOSED=(),建立CLOSED表,初始化为空表.3.LOOP:IF OPEN=(),THEN EXIT(FAIL)4.n=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);称n为当前节点.5.IF GOAL(n)THEN EXIT(SUCCESS);由n循指针返回s,可以获得解路径.6.EXPAND(n)mi,G=ADD(mi,G),子节点集mi中不包含n的父辈节点.人工智能吉林大学珠海学院计算机科学与技术系 7 标记和修改指针 ADD(mj,OPEN),并标记mj连接到n的指针,mj是未在OPEN和CLOSED中出现过的子节点.

23、计算是否需要修改mk,ml到n的指针;mk是出现在OPEN表中的子节点,ml是出现在CLOSED表中的子节点,Mi=MjMkMl 计算是否需要修改mi到其后记节点的指针.8.对OPEN表中的节点按某种原则重新排序.9.GO LOOP.人工智能吉林大学珠海学院计算机科学与技术系对 GRAPHSEARCH算法的几点说明:1.两个图,2.G:搜索图,它是记录算法访问过的所有节点的图,初始化为问题的初始状态s,在搜索过程中不断地扩展.3.T:G的有向支撑树,与G有同样的节点,由指针定义.记录由该节点到s的最短路径,在搜索过程中需要不断调整.4.2.两个表:OPEN和CLOSED,OPEN表记录搜索图的

24、前沿,CLOSED表记录已经扩展过的节点.5.3.树T的指针的建立和调整.6.树T中节点的指针记录从该节点到初始节点s的最短路径,随着算法的进行,图的扩展,这些指针需要不断地调整.对新产生的节点,为其建立指针.对OPEN和CLOSED表中的节点,需要考虑调整其指针,对于CLOSED表中节点,还需要考虑调整其后继节点的指针.人工智能吉林大学珠海学院计算机科学与技术系Notes about the procedure GRAPHSEARCH 1.Two graphs:G:The explicit part of the graph generated by the production syste

25、m,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 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 p

26、rocedure 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 nodes of graph G,the node have been expanded.3.The establishment and readjustment of the pointers of tree T.For the n

27、ewly 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 need to consider the readjustment of their descendants,for the adjustment of the nodes of CLOSED may influence their

28、descendants pointers 人工智能吉林大学珠海学院计算机科学与技术系s12人工智能吉林大学珠海学院计算机科学与技术系12人工智能吉林大学珠海学院计算机科学与技术系1.3 1.3 无信息的图搜索过程无信息的图搜索过程 深度优先和宽度优先深度优先和宽度优先 深度优先和宽度优先的思想在数据结构中已经讲过,在数据结构中是作为树的遍历的方法讲的,人工智能中在状态空间中搜索解的过程也类似于遍历.所不同的是这里搜索的是图而不是树.所以这里我们只讨论与解有关的问题 宽度优先在搜索解的过程中总是在探索了层数小于或等于n的节点之后才进入到n+1层节点的探索,所以这中方法获得的解具有最短的解路径.但

29、如果图的分枝系数很高,或者解路径很长,效率会很低.深度优先可以很快地使实验解路径延伸到很长,如果刚好在延伸的过程中遇到解,这种方法的效率会很高,但不能保证找到有最短的解路径.甚至即使在原问题有解的时候,也会发生会在错误的方向上无限延伸下去而找不到解的情况,人工智能吉林大学珠海学院计算机科学与技术系深度优先算法Procedure DEPTH-FIRTST SEARCH1 G=s,OPEN=(s),CLOSED=().2 LOOP:IF OPEN=(),THEN EXIT(FAIL)3 n=FIRST(OPEN);44 IF GOAL(n)THEN EXIT(SUCCESS);55 REMOVE(

30、n,OPEN),ADD(n,CLOSED);66 EXPAND(n)mi,G=ADD(mi,G);7 ADD(mi,OPEN),并标记mi到n的指针,把不在OPEN和 8 CLOSED 中的节点放在最前面,使深度大的节点可以优先扩展.98 GO LOOP人工智能吉林大学珠海学院计算机科学与技术系使用 DEPTH-FIRST-SEARCH搜索的例D6C4B4A5H3G4F5E5O2JIKP3TSKKLMNgoal人工智能吉林大学珠海学院计算机科学与技术系为保证深度优先算法在问题有解的情况下总能找到解,需要增加深度限制,而且深度限制必须超过解的长度.人工智能吉林大学珠海学院计算机科学与技术系 1.

31、4 1.4 启发式搜索启发式搜索4 4。0 0 简介简介 heuristic heuristicOf or relating to a usually speculative formulation serving as a guide in the investigation or solution of a problem:探索的,做为调查或解决问题的向导的一种通常为推测性系统阐述 回溯式搜索，深度优先和宽度优先都不使用领域知识，效率很低。启发式搜索使用关于领域的信息指导，使搜索向着有利于获得解的方向进展。如果应用得好，可以明显地缩小搜索空间，提高搜索效率 例如，在九宫游戏中使用启发式搜索

32、，就可以显著地减少搜索空间人工智能吉林大学珠海学院计算机科学与技术系MINMAX人工智能吉林大学珠海学院计算机科学与技术系在九宫游戏中使用启发式搜索：使用启发函数 h(s)=MAX 已投下的子可以占据的行，列和对角线数人工智能吉林大学珠海学院计算机科学与技术系MINMAX54432434445人工智能吉林大学珠海学院计算机科学与技术系 启发式搜索算法启发式搜索算法 最佳优先搜索。根据启发函数对尚为探索的节点进行排序，把最有希望的节点排再前面，在扩展节点时把最有希望的节点拿出来考虑。最佳优先搜索算法 function best-first-search 算法保存 2 个表，一个是open表，记录

33、已经产生但尚未探索的节点，另一个是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)的估计值.人工智能吉林大学

34、珠海学院计算机科学与技术系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);6EXPAND(n)mi,G=ADD(mi,G);7 建立和调整指针,计算各节点的f 值.并按各点的f值调整指针.7 把OPEN表中的节点按f值从小到大排序.8 GO LOOP人工智能吉林大学珠海学院计算机科学与技术系2 8 31 6 47 52 8 31 6 4

35、 7 52 8 31 47 6 52 8 31 6 47 541+5=61+3=41+5=61 2 38 47 6 5目标状态h 值是偏离目标位置的块数W(n)人工智能吉林大学珠海学院计算机科学与技术系2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 5 2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5 8 32 1 47 6 52 8 37 1 4 6 512345Goal

36、 node6s4A6B4C6D5E5F6G6H7I5J7K5L5M77人工智能吉林大学珠海学院计算机科学与技术系初始化.Open=s4;closed=1.测试s4,Open=B4,A6,C6;closed=s42.测试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,D5,E5 5.测试I5,Open=K5,A6,C6,F6,G6,H7,J7;closed=s4,B4,D5,E5,I5 6.

37、测试K5,Open=L5,A6,C6,F6,G6,H7,J7,M7;closed=s4,B4,D5,E5,I5,K5 7.L=goal,成功找到了解人工智能吉林大学珠海学院计算机科学与技术系2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 5 2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5 8 32 1 47 6 52 8 37 1 4 6 512345Goal node6

38、44646556675755772 8 31 6 47 52 8 31 6 47 5 Closed表中的节点open表中的节点选择节点 D 扩展时的Open表和closed 表人工智能吉林大学珠海学院计算机科学与技术系2.爬山法 f(n)=h(n)3.分支界限法4.f(n)=g(n)5.4.动态规划法6.对分支界限法的改进,如果有多条到达某一节点的路径,只保留费用最小的一条.人工智能吉林大学珠海学院计算机科学与技术系分支界限法sDAEFtBC32534544设有 7 城市,城市之间的距离如图,求从s到t的最短通路人工智能吉林大学珠海学院计算机科学与技术系分支界限法sDA1g=02g=33g=4

39、人工智能吉林大学珠海学院计算机科学与技术系分支界限法sDA1g=02g=33g=4DB5g=76g=8人工智能吉林大学珠海学院计算机科学与技术系分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6人工智能吉林大学珠海学院计算机科学与技术系分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6Bg=11g=13F109人工智能吉林大学珠海学院计算机科学与技术系分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECg=11g=121112109Bg=11g=13F人工智能吉林大学珠海学院计算机科学与技术系分支界限法

40、sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECg=11g=12BEg=10g=11Bg=13FDFBFACtg=14g=16g=15g=14g=15g=15g=1311128109人工智能吉林大学珠海学院计算机科学与技术系动态规划法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECBg=11Fg=10tg=14g=131112109人工智能吉林大学珠海学院计算机科学与技术系5.5.最佳图搜索算法最佳图搜索算法A*A*在启发式搜索中使用评估函数 f(n)=g(n)+h(n)其中，g(n)是从初始状态到 n 费用；h(n)是从 n 到目标的启发式

41、估计费用把使用这种估值函数的启发式程序叫做A算法。如果状态空间的图搜索问题存在解路径，搜索算法 f 一定能找到该问题的最优解路径，则称算法 f 是可采纳的。如果在A算法中使用的启发函数满足 h(n)h*(n)则称之为 A*算法。人工智能吉林大学珠海学院计算机科学与技术系 A*算法是可采纳的算法是可采纳的若存在从初始节点若存在从初始节点s s到目标节点到目标节点t t的路径，的路径，则则A*A*算法算法必能找到最佳解路径。必能找到最佳解路径。例如，在宽度优先搜索中，h(n)0，满足 h(n)h*(n)，是可采纳的。和前面举例的f(n)=g(n)+h(n)中，h(n)取为偏离目标位置的块数，满足h

42、(n)h*(n)，也是可采纳的。人工智能吉林大学珠海学院计算机科学与技术系单调性单调性 在算法 A 中，g(n)是 g*(n)的估计值，定义为在已经产生的节点中从初始节点到 n 的最短路径的费用，在算法进行的过程中，我们需要不断地计算，比较和调整这条最短路径，这要消耗大量的计算时间，因而也影响算法的效率，如果能对启发函数增加某些限制条件，使得在这种限制条件下，理论上就可以证明 g(n)就是 g*(n),则为获得 g(n)所需要的计算就可以省略了。这个条件就是单调性。定义：定义：单调性单调性 启发函数单调的条件是：1。对于所有的状态ni和nj，其中nj是ni的后继 h(ni)-h(nj)cost

43、(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,都有 h1(n)h2(n)则称h2(n)比 h1(n)有更高的信息度。如果h2(n)比 h1(n)有更高的信息度，则算法2所扩展的节点一定会被算法1所扩展，换句话说，算法2所扩展的节点比

44、算法1扩展的节点少。人工智能吉林大学珠海学院计算机科学与技术系8.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 31 6 47 52 8 31 6 4 7 52 8 31 47 6

45、 52 8 31 6 47 5 2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5 8 32 1 47 6 52 8 37 1 4 6 52345Goal node6G6H7I5P=5f=5P=2f=7P=6f=7P=4f=5P=6f=7P=5f=7P=3f=5P=5f=7P=2f=5P=4f=7P=1f=5P=0f=5人工智能吉林大学珠海学院计算机科学与技术系(5,5,1)(4,4,0)(5,2,0)(5,3,0)(5,4,0)

46、(5,3,1)(5,4,1)(5,0,0)(5,1,0)(3,3,0)(5,1,1)(5,2,1)(4,4,1)(0,3,0)(3,3,1)(2,2,0)h(n)=0图虽然简单,但包括许多经仔细考虑后的剪忮人工智能吉林大学珠海学院计算机科学与技术系迷宫问题求从入口到出口通过迷宫的最短路径入口出口人工智能吉林大学珠海学院计算机科学与技术系迷宫问题入口(1,1)出口(4,4)人工智能吉林大学珠海学院计算机科学与技术系问题描述 R1:if(x,y)then(x+1,y)R2:if(x,y)then(x,y-1)R1:if(x,y)then(x-1,y)R1:if(x,y)then(x,y+1)h(n

47、)=|Xg-xn|+|Yg-yn|其中(Xg,Yg)为目标点坐标,(xn,yn)为节点n的坐标,人工智能吉林大学珠海学院计算机科学与技术系(1,1)(1,2)(1,3)(2,3)(2,2)(2,4)(3,4)(1,4)(2,1)(3,2)(3,1)(3,3)(4,1)(4,2)(4,3)(4,4)人工智能吉林大学珠海学院计算机科学与技术系(1,1)(2,3)(2,2)(2,4)(1,4)(3,2)(3,4)(3,3)(4,2)(4,3)(4,4)h=3f=6h=6f=6721h=2f=63h=4f=83h=3f=8h=1f=6h=2f=8h=1f=8h=0f=8h=3f=10h=2f=1045

48、6人工智能吉林大学珠海学院计算机科学与技术系9.评价函数的启发能力 评价函数的启发能力由以下 3 因素决定 1.解路径的费用.2.求解过程中扩展节点的个数.3.计算h所需要的工作量.有时使用 f=g+wh 有时以牺牲可采纳性为代价,获得强的启发能力.显然解路径越长，找到解路径所需要的计算费用就越大。所以，在条件允许的情况下，我们希望找到费用最低的解路径，即最佳解路径。根据前面几节的介绍，我们知道如果启发函数满足h(n)h*(n),即使用A*算法，则只要被搜索的图有解，算法肯定能找到最佳解路径。人工智能吉林大学珠海学院计算机科学与技术系 解路径的费用（长度）并不是影响算法的唯一因素。算法在寻找解

49、路径的过程中所需要扩展的节点数也是影响效率的一个重要因素。所需要扩展的节点数少，说明算法引导搜索集中向目标节点的方向发展，当然有利于较快地找到解。因此，有时为了增加算法的启发能力，我们采用较大的启发函数值，甚至于不满足h(n)h*(n)，这样做牺牲了算法的可采纳性，但可以使算法扩展的节点个数大幅度下降，换来了算法的高效率。人工智能吉林大学珠海学院计算机科学与技术系在构造启发函数时，如果函数包含的启发信息越多，对算法在OPEN表中节点的排序越准确，总能把最有希望获得解的节点优先选出来扩展。但这时启发函数的计算量也就越大。最理想的启发函数h在搜索图中每一个节点上的取值都与该节点到目标节点的实际费用h*相同，但这样的启发函数需要大量的计算，使算法的效率反而下降。因此，在解决实际问题时，我们需要在启发函时的计算量和扩展节点的数量之间作认真的权衡。人工智能吉林大学珠海学院计算机科学与技术系 对于一个给定的启发函数，可以通过对该函数乘以一个大于1的正数w的方法增加它的启发能力。这时评价函数变成 f=g+w*h,如果w很大，相当于g(n)0.有些问题只要求我们找出解路径，不考虑解路径的费用，对于这类问题，我们可以完全不考虑g 对求解的影响，采用f=w*h式的评价函数。使w随搜索树的节点深度成反比变化,可提高搜索效率.人工智能吉林大学珠海学院计算机科学与技术系演讲完毕，谢谢观看！