人工智能 搜索问题课件

第1章搜索问题什么是状态空间？回溯策略。图搜索策略无信息的图搜索策略启发式图搜索策略A*算法。A*算法的性质。搜索算法的讨论。第1章搜索问题什么是状态空间？1状态空间计算机对传统的问题求解方法带来了根本性的改变。传统方法，由专家给出公式，使用者的任务是理解公式，应用公式。有些问题用传统方法描述很困难,例如本节的几个例子公式的推导需要很高的水平，与实际问题相差较远，对应用者要求很高。2.计算机利用自己强大的计算能力和存储能力,采用”猜”的方式,试探法.能解决问题的领域更广,更结合实际.状态空间计算机对传统的问题求解方法带来了根本性的改变。2例智力游戏问题：传教士与野人渡河问题传教士与野人渡河问题：有3个传教士带3个野人渡河，河的岸边有一条船，每次最多可载2人，要求无论在河的哪一边，野人的数目不能超过传教士的数目，问为安全起见，应如何安排传教士与野人渡河？一种较为简单的表示方式3元向量（x,y,z）x:河此岸的传教士数，y:河此岸的野人数。x,y取值范围{0，1，2，3}z:船在此岸，z取值范围{0，1}例智力游戏问题：传教士与野人渡河问题传教士与野人渡河问3初始状态：（3，3，1）目标状态：（0，0，0）2831647512386475初始状态Initial目标状态Goal例设有8数码难题如下:在3×3的框架中有8个标有数字的硬纸片，这些硬纸片上标的数字分别是1，2，…,8，每个纸片都可以移进相邻的空格，8数码难题的初始状态和目标状态分别列出如下，问如何把这个问题由初始状态移向目标状态？初始状态：（3，3，1）2831647512386475初42831647512386475InitialGoal8数码难题（8-puzzle）的矩阵描述对于8数码难题，我们选用直接的矩阵描述，解题过程中的任何一个中间情况都对应一个3*3的矩阵，用0,1，2，…,8这9个数的一个排列依次去充填这个矩阵的各个单元,就是求解问题的一个可能的情况,共有9!种。2831647512386475Initial5143765821374658214376582123786521237658213746582137465821431765821435768214378652143786521437635821437625814313143126例旅行推销员问题ABDCE75100125125501005075125100125问题表示,形式为(A****)的字符串和(A****A)的字符串。其中****为B,C,D,E的排列.问题的节，形式为(A****A)的字符串,其中****为B,C,D,E的排列.例旅行推销员问题ABDCE75100125125501007旅行推销员问题的搜索空间EADCBCDEAEDADCEAE10012510075150175425225325275375300250旅行推销员问题的搜索空间EADCBCDEAEDADCEAE181.1回溯策略回溯策略的主要思想:只保留从初始状态到当前状态的一条解路径,给变换状态的规则给出一个排序方法,对当前状态使用规则产生新的状态,不断地向前延伸解路径.当没有规则可用,或向前延伸的状态都是无解状态(称为死点,deadend)时,沿解路径后退到前一个状态(回溯),重新开始搜索,直至找到解或宣布失败.回溯策略是一种穷尽的搜索方法.1.1回溯策略9

2.1回溯算法BacktrackingStrategies

递归过程Asimplerecursiveprocedure

输入:问题的初始状态..

Theinput:theinitialstate.

输出:一个规则表.应用这个规则表可以把初始状态变为目标状态.否则回答FAIL.

Theoutputoftheprocedure,alistofrules,usingitwecangetthegoalfromtheinitialstate.Iftheprocedurecannotfindthesolution,itreturnFAIL.

RecursiveprocedureBACKTRCK(DATA)1ifTERM(DATA),returnNIL;2ifDEADEND(DATA),returnFAIL;3RULES←APPRULES(DATA);2.1回溯算法BacktrackingStrate104LOOP:ifNULL(RULES),returnFAIL;

5R←FIRST(RULES);

6RULES←TAIL(RULES);

7RDATA←R(DATA);

8PATH←BACKTRACK(RDATA);

9ifPATH=FAIL,goLOOP;

10returnCONS(R,PATH)4LOOP:ifNULL(RULES),retu11Instep3,aftergetthelistofrulesusingthefunctionAPPRULES,weneedtoordertherulesinthelists.Theorderingisveryimportant.Ifthe“better”

ruleisputinthefrontofthelist,itcanbeusedfirstly,theefficiencyofthesystemishigh.Ifthe“worse”ruleisputinthefront,thesystemneedstotry

morerules,theefficiencyofthesystemispoor.

TheExampleofBacktrackingprocedure.

The4queenproblem

*

*

*在利用APPRUKES得到规则表之后,需要对表中的规则排序,把好的规则放在表的前面优先使用,这个排序对算法的效率有很大影响.Instep3,aftergetthelist12Theproblemrepresentation

theglobaldatabase:4*4array

therule:Rij

Ifi=1:therearenoqueeninthearray

1<i<=4:Thereisaqueenintherowi-1

thenputaqueenintherowi,columnj

Weordertherulesaccordingtothecolumn.

我们用Rij表示在棋盘的第i行第j列放一个王后.按行的增加顺序依次放皇后,在规则的排序上依列的上升次序排序.

Terminationcondition:thereare4queensinthechessboard,theycannotkilleachother.

终止条件:4皇后都放到棋盘上,且不能互相杀死.

Theproblemrepresentation

13Orderofrules:R11,R12,R13,R14R21,R22,R23,R24deadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadendTheremanybacktrackNIL()(R43)(R31,R43)(R24,R31,R43)(R12,R24,R31,R43)Orderofrules:R11,R12,R13,14Wecanusemoreinformedruleorderingusingfunctiondiag(i,j)

我们可以采用含有较多信息的函数diag(i,j).

Diag(i,j)=thelengthofthelongestdiagonalpassingthroughcell(i,j)

diag(i,j)是通过单元(i,j)的最长对角线的长度,我们按diag(i,j)排序,weorderRmnbeforeRij,ifdiag(m,n)<diag(i,j)

RinbeforeRij,Ifdiag(i,n)=diag(i,j)andn<j

Homework:Solvethe4queensproblembyusingbacktrackingprocedureandfunctiondiag

BACKTRACK1:toavoidcycle

1.Theargumentoftheprocedureischanged,fromasinglestate

toalistofstate.

2.UseMEMBERfunctiontocheckcycle.

3.AdddepthboundWecanusemoreinformedrule15

2.1BacktrackingStrategies

Asimplerecursiveprocedure

Theinputoftheprocedure,DATA:theinitialstate.

Theoutputoftheprocedure,alistofrules,usingitwecanget

thegoalfromtheinitialstate.Iftheprocedurecannotfindthesolution,itreturnFAIL.

RecursiveprocedureBACKTRCK(DATALIST)1DATA←FIRST(DATALIST);2ifMEMBER(DATA,TAIL(DATALIST)),returnFAIL;3ifTERM(DATA),returnNIL;4ifDEADEND(DATA),returnFAIL;5ifLENGTH(DATALIST)>BOUND,returnFAIL;6RULES←APPRULES(DATA);2.1BacktrackingStrategies167LOOP:ifNULL(RULES),returnFAIL;

8R←FIRST(RULES);

9RULES←TAIL(RULES);

10RDATA←R(DATA);

11RDATALIST←CONS(RDATA,DATALIST);

12PATH←BACKTRACK(RDATALIST);

13ifPATH=FAIL,goLOOP;

14returnCONS(R,PATH)7LOOP:ifNULL(RULES),retu171.2图搜索策略graph-searchstrategies回溯算法只包含一条探索路径,如果发现deadend节点或无规则可用时要退回来,因此可能产生把探索过的节点擦掉后又重新产生的现象.在图搜索算法中.将所有搜索过的状态用一个图(搜索图)记录下来,图的弧反映状态之间的关系.在图中选择节点加以扩展,直至把搜索图扩展到充分大,包含解路径在内.1.2图搜索策略graph-searchstra18Themainideaofgraphsearch

Inthebacktrackingprocedure,wepreserveonlyapathfromtheinitialstatetothecurrentstate,sosometimesweneedtoproductsomestatesagainafterthestateswereremoved.However,ingraphsearchmethod,Wepreserveagraphinthememory,thegraphincludeallthestateswepassedthroughandtherelationoftheirsequences.Whenwefindsomenode(state)inthegraphissuitedtoexpandforsearch,weexpandit,continueoursearching,untilasolutionisfinded.Themainideaofgraphsearch

19图论与状态空间表示

有向图G是一个偶对(N,E),其中N是节点集合，E是有向弧的集合。

DECBA有向图中的有关概念，父亲节点，儿子节点，叶节点，路径，回路，有向树。图论与状态空间表示

有向图G是一个偶对(N,E),20用有向图表示问题的状态空间是一种很自然的方式，节点代表状态描述，弧代表状态之间的转移。

但是，问题的状态描述与有向图又有许多本质上的不同，需要引起我们注意：

1。图论中研究的有向图是有限的，我们可以把有向图全部画出来。而人工智能中描述问题的有向图一般说来是无限的，或者说虽然有限，但是非常大，我们不可能将其画出来。

2。图论中的问题求解是在对图完全了解的情况下进行。而我们对状态空间搜索解的过程是边产生图边求解，这里所产生的图是表示状态空间的无限图的显式部分，从求解的效率考虑，就有把这个无限图的显式部分向哪个方向以何种方式扩展的问题。用有向图表示问题的状态空间是一种很自然的方式，节点代表状态21Motivation:thelimitationofbacktrackingprocedureSometimes,afteranalyzingweneedtoreproducesomestatesagain.DB1DB2DB3DB4R1R2R3DB1DB2DB3DB4R1R2R3222.2graph-searchstrategiesMotivation:thelimitationofbacktrackingprocedureSometimes,afteranalyzingweneedtoreproducesomestatesagain.DB1DB4R22.2graph-searchstrategiesMo23DB1DB2DB4R1R2DB1DB2DB3DB4R1R2R3DB1DB2DB4R1R2DB1DB224问题的状态和它们之间的关系可以用一个图隐含地加以描述.

状态用图的节点表示,状态之间的关系用图中的弧表示.

thestatesandtheirrelationsaredefinedbyagraphimplicitly:

states————————>nodes

ruleapplications——————>arcs

但是,我们也应该注意到它们之间的区别:

However,generallythegraphisendless,Wecannotdrawthegraphsinordinaryway.

问题的状态和它们之间的关系可以用一个图隐含地加以描述.

状25Startingfromtheinitialstate,wegenerateansub-graph(anexplicitpartofthegraphimplicitlydefinedbyproductionsystem),thenweselectthenodeinthesub-graphtoexpandit,ifthesub-graphdoesnotcontainthegoalnode,wecontinuetoexpandit,untilthesub-graphislargeenoughtoincludethegoalnode,andwefindthesolutionpathfromtheinitialnode

tothegoalnode.

TheprocedureGRAPHSEARCH

input:theproductionsystem(theinitialnose,productionrule,goalnode)

output:thesolutionpathfromtheinitialnodetoagoalnodeStartingfromtheinitialstat26

ProcedureGRAPHSEARCHG=s,OPEN=(s);G为搜索图,初始化为问题的初始状态s,建立OPEN表,初始化为只含初始状态s.CLOSED=(),建立CLOSED表,初始化为空表.LOOP:IFOPEN=(),THENEXIT(FAIL)n=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);称n为当前节点.IFGOAL(n)THENEXIT(SUCCESS);由n循指针返回s,可以获得解路径.EXPAND(n)→mi,G=ADD(mi,G),子节点集{mi}中不包含n的父辈节点.

277标记和修改指针ADD(mj,OPEN),并标记mj连接到n的指针,mj是未在OPEN和CLOSED中出现过的子节点.计算是否需要修改mk,ml到n的指针;mk是出现在OPEN表中的子节点,ml是出现在CLOSED表中的子节点,{Mi}={Mj}∪{Mk}∪{Ml}计算是否需要修改mi到其后记节点的指针.8.对OPEN表中的节点按某种原则重新排序.9.GOLOOP.

7标记和修改指针28对GRAPHSEARCH算法的几点说明:两个图,G:搜索图,它是记录算法访问过的所有节点的图,初始化为问题的初始状态s,在搜索过程中不断地扩展.T:G的有向支撑树,与G有同样的节点,由指针定义.记录由该节点到s的最短路径,在搜索过程中需要不断调整.2.两个表:OPEN和CLOSED,OPEN表记录搜索图的前沿,CLOSED表记录已经扩展过的节点.3.树T的指针的建立和调整.树T中节点的指针记录从该节点到初始节点s的最短路径,随着算法的进行,图的扩展,这些指针需要不断地调整.对新产生的节点,为其建立指针.对OPEN和CLOSED表中的节点,需要考虑调整其指针,对于CLOSED表中节点,还需要考虑调整其后继节点的指针.对GRAPHSEARCH算法的几点说明:29NotesabouttheprocedureGRAPHSEARCH1.Twographs:G:Theexplicitpartofthegraphgeneratedbytheproductionsystem,itsinitialnodeistheinitialstate,itisexpandedconstantly.T:thedirectedsupporttreeofG,ithassamenodesasthegraphG,hisarc(onlyoneoutgoingarcfromanode)directtheshortestpathfromonenodetoanothernode.Thearcsaremarkedbypointers.Inordertopreservethecharacter,theprocedureneedtoreadjustthearcsofthetreeconstantly.NotesabouttheprocedureGRAP302.Twolist:OPENthefrontiernodesofgraphG,fromwhich,we

selectanodetoexpand.

CLOSEDtheinteriornodesofgraphG,thenodehave

beenexpanded.

3.TheestablishmentandreadjustmentofthepointersoftreeT.

Forthenewlygeneratednodes,weneedtoestablishthepointer

forthem.

ForthenodesinthelistsonOPENandCLOSED,weneedto

considertoreadjusttheirpointers.

ForthenodesofCLOSED,weneedtoconsiderthereadjustmentof

theirdescendants,fortheadjustmentofthenodesofCLOSED

mayinfluencetheirdescendant’spointers

2.Twolist:OPENthef31s12s12321212331.3无信息的图搜索过程

深度优先和宽度优先

深度优先和宽度优先的思想在数据结构中已经讲过,在数据结构中是作为树的遍历的方法讲的,人工智能中在状态空间中搜索解的过程也类似于遍历.所不同的是这里搜索的是图而不是树.所以这里我们只讨论与解有关的问题

宽度优先在搜索解的过程中总是在探索了层数小于或等于n的节点之后才进入到n+1层节点的探索,所以这中方法获得的解具有最短的解路径.但如果图的分枝系数很高,或者解路径很长,效率会很低.

深度优先可以很快地使实验解路径延伸到很长,如果刚好在延伸的过程中遇到解,这种方法的效率会很高,但不能保证找到有最短的解路径.甚至即使在原问题有解的时候,也会发生会在错误的方向上无限延伸下去而找不到解的情况,1.3无信息的图搜索过程

深度优先和宽度优先

34深度优先算法ProcedureDEPTH-FIRTSTSEARCH1G=s,OPEN=(s),CLOSED=().2LOOP:IFOPEN=(),THENEXIT(FAIL)n=FIRST(OPEN);4IFGOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN),ADD(n,CLOSED);

6EXPAND(n)→{mi},G=ADD(mi,G);ADD(mi,OPEN),并标记mi到n的指针,把不在OPEN和CLOSED中的节点放在最前面,使深度大的节点可以优先扩展.8GOLOOP深度优先算法35使用DEPTH-FIRST-SEARCH搜索的例

D6C4B4A5H3G4F5E5O2JIKP3TSKKLMNgoal使用DEPTH-FIRST-SEARCH搜索的例

D6C436为保证深度优先算法在问题有解的情况下总能找到解,需要增加深度限制,而且深度限制必须超过解的长度.为保证深度优先算法在问题有解的情况下总能找到解,需要增加深371.4启发式搜索

4。0简介heuristic

Oforrelatingtoausuallyspeculativeformulationservingasaguideintheinvestigationorsolutionofaproblem:

探索的,做为调查或解决问题的向导的一种通常为推测性系统阐述

回溯式搜索，深度优先和宽度优先都不使用领域知识，效率很低。

启发式搜索使用关于领域的信息指导，使搜索向着有利于获得解的方向进展。如果应用得好，可以明显地缩小搜索空间，提高搜索效率

例如，在九宫游戏中使用启发式搜索，就可以显著地减少搜索空间1.4启发式搜索

4。0简介heuristic38MINMAXMINMAX39在九宫游戏中使用启发式搜索：

使用启发函数

h(s)=MAX已投下的子可以占据的行，列和对角线数

在九宫游戏中使用启发式搜索：

使用启发函数

40MINMAX54432434445MINMAX5443243444541启发式搜索算法

最佳优先搜索。根据启发函数对尚为探索的节点进行排序，把最有希望的节点排再前面，在扩展节点时把最有希望的节点拿出来考虑。

最佳优先搜索算法functionbest-first-search

算法保存2个表，一个是open表，记录已经产生但尚未探索的节点，另一个是closed表，记录已经探索过的节点，算法把新产生的节点加入到open表中，然后按启发函数值将它们排序，把最有希望的节点排在前面，选出来加以测试和扩展启发式搜索算法

最佳优先搜索。根据启发函数对42启发式搜索算法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

评价函数

依据领域知识，对43A算法ProcedureA1G=s,OPEN=(s),CLOSED=().2LOOP:IFOPEN=(),THENEXIT(FAIL)3n=FIRST(OPEN);4IF4IFGOAL(n)THENEXIT(SUCCESS);5REMOVE(n,OPEN),ADD(n,CLOSED);EXPAND(n)→{mi},G=ADD(mi,G);建立和调整指针,计算各节点的f值.并按各点的f值调整指针.7把OPEN表中的节点按f值从小到大排序.8GOLOOPA算法442831647528316475283147652831647541+5=61+3=41+5=612384765目标状态h值是偏离目标位置的块数W(n)2832832832834145283164752831647528314765283164752831476523184765283147652318476523184765123847651238476512378465832147652837146512345Goalnode6s4A6B4C6D5E5F6G6H7I5J7K5L5M77283283283283246初始化.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,D5,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,成功找到了解

初始化.Open=[s4];closed=[]

47283164752831647528314765283164752831476523184765283147652318476523184765123847651238476512378465832147652837146512345Goalnode644646556675755772831647528316475Closed表中的节点open表中的节点选择节点D扩展时的Open表和closed表2832832832832482.爬山法

f(n)=h(n)分支界限法f(n)=g(n)4.动态规划法对分支界限法的改进,如果有多条到达某一节点的路径,只保留费用最小的一条.2.爬山法

f(n)=h(n)分支界限法49分支界限法

sDAEFtBC32534544设有7城市,城市之间的距离如图,求从s到t的最短通路分支界限法

sDAEFtBC32534544设有7城市,50分支界限法sDA1g=02g=33g=4分支界限法sDA1g=02g=33g=451分支界限法sDA1g=02g=33g=4DB5g=76g=8分支界限法sDA1g=02g=33g=4DB5g=76g=852分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6分支界限法sDA1g=02g=33g=4DB5g=76g=853分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6Bg=11g=13F109分支界限法sDA1g=02g=33g=4DB5g=76g=854分支界限法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECg=11g=121112109Bg=11g=13F分支界限法sDA1g=02g=33g=4DB5g=76g=855分支界限法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=856动态规划法sDA1g=02g=33g=4DB5g=76g=8EA7g=94g=6ECBg=11Fg=10tg=14g=131112109╳╳╳╳动态规划法sDA1g=02g=33g=4DB5g=76g=8575.最佳图搜索算法A*

在启发式搜索中使用评估函数

f(n)=g(n)+h(n)

其中，g(n)是从初始状态到n费用；

h(n)是从n到目标的启发式估计费用

把使用这种估值函数的启发式程序叫做A算法。

如果状态空间的图搜索问题存在解路径，搜索算法f一定能找到该问题的最优解路径，则称算法f是可采纳的。

如果在A算法中使用的启发函数满足

h(n)≦h*(n)

则称之为A*算法。

5.最佳图搜索算法A*

在启发式搜索中使用评估函数

58

A*算法是可采纳的

若存在从初始节点s到目标节点t的路径，则A*算法必能找到最佳解路径。

例如，在宽度优先搜索中，h(n)≦0，满足h(n)≦h*(n)，是可采纳的。

和前面举例的f(n)=g(n)+h(n)中，

h(n)取为偏离目标位置的块数，满足h(n)≦h*(n)，也是可采纳的。

A*算法是可采纳的

若存在从初始节点s到目标节点t的路径59单调性

在算法A中，g(n)是g*(n)的估计值，定义为在已经产生的节点中从初始节点到n的最短路径的费用，在算法进行的过程中，我们需要不断地计算，比较和调整这条最短路径，这要消耗大量的计算时间，因而也影响算法的效率，如果能对启发函数增加某些限制条件，使得在这种限制条件下，理论上就可以证明g(n)就是g*(n),则为获得g(n)所需要的计算就可以省略了。这个条件就是单调性。

定义：单调性

启发函数单调的条件是：

1。对于所有的状态ni和nj，其中nj是ni的后继

h(ni)-h(nj)≦cost(ni,nj)

cost(ni,nj)是节点ni和nj之间的实际最小费用

2。h(goal)=0

单调性

在算法A中，g(n)是g*(n)60启发函数的比较

设有两个算法，分别使用两个启发函数

算法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所扩展的节点比算法1扩展的节点少。

启发函数的比较

设有两个算法，分别使用两个启发函数

61A*算法的应用举例.

(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。A*算法的应用举例.

(1)8数码问题

6228316475283164752831476528316475283147652318476528314765231847652318476512384765123847651237846583214765283714652345Goalnode6G6H7I5P=5f=5P=2f=7P=6f=7P=4f=5P=6f=7P=5f=7P=3f=5P=5f=7P=2f=5P=4f=7P=1f=5P=0f=5283283283283263(5,5,1)(4,4,0)(5,2,0)(5,3,0)(5,4,0)(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图虽然简单,但包括许多经仔细考虑后的剪忮(5,5,1)(4,4,0)(5,2,0)(5,3,0)(564迷宫问题求从入口到出口通过迷宫的最短路径入口出口迷宫问题求从入口到出口通过迷宫的最短路径入口出口65迷宫问题入口(1,1)出口(4,4)迷宫问题入口(1,1)出口(4,4)66问题描述

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)=|Xg-xn|+|Yg-yn|

其中(Xg,Yg)为目标点坐标,(xn,yn)为节点n的坐标,问题描述

R1:if(x,y)then(x+1,67(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)(1,2)(1,3)(2,3)(2,2)(2,4)68(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=10456(1,1)(2,3)(2,2)(2,4)(1,4)(3,2)699.评价函数的启发能力

评价函数的启发能力由以下3因素决定

1.解路径的费用.

2.求解过程中扩展节点的个数.

3.计算h所需要的工作量.

有时使用f=g+wh

有时以牺牲可采纳性为代价,获得强的启发能力.

显然解路径越长，找到解路径所需要的计算费用就越大。所以，在条件允许的情况下，我们希望找到费用最低的解路径，即最佳解路径。根据前面几节的介绍，我们知道如果启发函数满足h(n)≦h*(n),即使用A*算法，则只要被搜索的图有解，算法肯定能找到最佳解路径。

9.评价函数的启发能力

评价函数的启发能力由以下70解路径的费用（长度）并不是影响算法的唯一因素。算法在寻找解路径的过程中所需要扩展的节点数也是影响效率的一个重要因素。所需要扩展的节点数少，说明算法引导搜索集中向目标节点的方向发展，当然有利于较快地找到解。因此，有时为了增加算法的启发能力，我们采用较大的启发函数值，甚至于不满足h(n)≦h*(n)，这样做牺牲了算法的可采纳性，但可以使算法扩展的节点个数大幅度下降，换来了算法的高效率。解路径的费用（长度）并不是影响算法的唯一因素。算法在寻71在构造启发函数时，如果函数包含的启发信息越多，对算法在OPEN表中节点的排序越准确，总能把最有希望获得解的节点优先选出来扩展。但这时启发函数的计算量也就越大。最理想的启发函数h在搜索图中每一个节点上的取值都与该节点到目标节点的实际费用h*相同，但这样的启发函数需要大量的计算，使算法的效率反而下降。因此，在解决实际问题时，我们需要在启发函时的计算量和扩展节点的数量之间作认真的权衡。在构造启发函数时，如果函数包含的启发信息越多，对算法在O72

对于一个给定的启发函数，可以通过对该函数乘以一个大于1的正数w的方法增加它的启发能力。这时评价函数变成f=g+w*h,如果w很大，相当于g(n)≡0.有些问题只要求我们找出解路径，不考虑解路径的费用，对于这类问题，我们可以完全不考虑g对求解的影响，采用f=w*h式的评价函数。使w随搜索树的节点深度成反比变化,可提高搜索效率.对于一个给定的启发函数，可以通过对该函数乘以一个大于1的73第1章搜索问题什么是状态空间？回溯策略。图搜索策略无信息的图搜索策略启发式图搜索策略A*算法。A*算法的性质。搜索算法的讨论。第1章搜索问题什么是状态空间？74状态空间计算机对传统的问题求解方法带来了根本性的改变。传统方法，由专家给出公式，使用者的任务是理解公式，应用公式。有些问题用传统方法描述很困难,例如本节的几个例子公式的推导需要很高的水平，与实际问题相差较远，对应用者要求很高。2.计算机利用自己强大的计算能力和存储能力,采用”猜”的方式,试探法.能解决问题的领域更广,更结合实际.状态空间计算机对传统的问题求解方法带来了根本性的改变。75例智力游戏问题：传教士与野人渡河问题传教士与野人渡河问题：有3个传教士带3个野人渡河，河的岸边有一条船，每次最多可载2人，要求无论在河的哪一边，野人的数目不能超过传教士的数目，问为安全起见，应如何安排传教士与野人渡河？一种较为简单的表示方式3元向量（x,y,z）x:河此岸的传教士数，y:河此岸的野人数。x,y取值范围{0，1，2，3}z:船在此岸，z取值范围{0，1}例智力游戏问题：传教士与野人渡河问题传教士与野人渡河问76初始状态：（3，3，1）目标状态：（0，0，0）2831647512386475初始状态Initial目标状态Goal例设有8数码难题如下:在3×3的框架中有8个标有数字的硬纸片，这些硬纸片上标的数字分别是1，2，…,8，每个纸片都可以移进相邻的空格，8数码难题的初始状态和目标状态分别列出如下，问如何把这个问题由初始状态移向目标状态？初始状态：（3，3，1）2831647512386475初772831647512386475InitialGoal8数码难题（8-puzzle）的矩阵描述对于8数码难题，我们选用直接的矩阵描述，解题过程中的任何一个中间情况都对应一个3*3的矩阵，用0,1，2，…,8这9个数的一个排列依次去充填这个矩阵的各个单元,就是求解问题的一个可能的情况,共有9!种。2831647512386475Initial781437658213746582143765821237865212376582137465821374658214317658214357682143786521437865214376358214376258143131431279例旅行推销员问题ABDCE75100125125501005075125100125问题表示,形式为(A****)的字符串和(A****A)的字符串。其中****为B,C,D,E的排列.问题的节，形式为(A****A)的字符串,其中****为B,C,D,E的排列.例旅行推销员问题ABDCE751001251255010080旅行推销员问题的搜索空间EADCBCDEAEDADCEAE10012510075150175425225325275375300250旅行推销员问题的搜索空间EADCBCDEAEDADCEAE1811.1回溯策略回溯策略的主要思想:只保留从初始状态到当前状态的一条解路径,给变换状态的规则给出一个排序方法,对当前状态使用规则产生新的状态,不断地向前延伸解路径.当没有规则可用,或向前延伸的状态都是无解状态(称为死点,deadend)时,沿解路径后退到前一个状态(回溯),重新开始搜索,直至找到解或宣布失败.回溯策略是一种穷尽的搜索方法.1.1回溯策略82

2.1回溯算法BacktrackingStrategies

递归过程Asimplerecursiveprocedure

输入:问题的初始状态..

Theinput:theinitialstate.

输出:一个规则表.应用这个规则表可以把初始状态变为目标状态.否则回答FAIL.

Theoutputoftheprocedure,alistofrules,usingitwecangetthegoalfromtheinitialstate.Iftheprocedurecannotfindthesolution,itreturnFAIL.

RecursiveprocedureBACKTRCK(DATA)1ifTERM(DATA),returnNIL;2ifDEADEND(DATA),returnFAIL;3RULES←APPRULES(DATA);2.1回溯算法BacktrackingStrate834LOOP:ifNULL(RULES),returnFAIL;

5R←FIRST(RULES);

6RULES←TAIL(RULES);

7RDATA←R(DATA);

8PATH←BACKTRACK(RDATA);

9ifPATH=FAIL,goLOOP;

10returnCONS(R,PATH)4LOOP:ifNULL(RULES),retu84Instep3,aftergetthelistofrulesusingthefunctionAPPRULES,weneedtoordertherulesinthelists.Theorderingisveryimportant.Ifthe“better”

ruleisputinthefrontofthelist,itcanbeusedfirstly,theefficiencyofthesystemishigh.Ifthe“worse”ruleisputinthefront,thesystemneedstotry

morerules,theefficiencyofthesystemispoor.

TheExampleofBacktrackingprocedure.

The4queenproblem

*

*

*在利用APPRUKES得到规则表之后,需要对表中的规则排序,把好的规则放在表的前面优先使用,这个排序对算法的效率有很大影响.Instep3,aftergetthelist85Theproblemrepresentation

theglobaldatabase:4*4array

therule:Rij

Ifi=1:therearenoqueeninthearray

1<i<=4:Thereisaqueenintherowi-1

thenputaqueenintherowi,columnj

Weordertherulesaccordingtothecolumn.

我们用Rij表示在棋盘的第i行第j列放一个王后.按行的增加顺序依次放皇后,在规则的排序上依列的上升次序排序.

Terminationcondition:thereare4queensinthechessboard,theycannotkilleachother.

终止条件:4皇后都放到棋盘上,且不能互相杀死.

Theproblemrepresentation

86Orderofrules:R11,R12,R13,R14R21,R22,R23,R24deadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadendTheremanybacktrackNIL()(R43)(R31,R43)(R24,R31,R43)(R12,R24,R31,R43)Orderofrules:R11,R12,R13,87Wecanusemoreinformedruleorderingusingfunctiondiag(i,j)

我们可以采用含有较多信息的函数diag(i,j).

Diag(i,j)=thelengthofthelongestdiagonalpassingthroughcell(i,j)

diag(i,j)是通过单元(i,j)的最长对角线的长度,我们按diag(i,j)排序,weorderRmnbeforeRij,ifdiag(m,n)<diag(i,j)

RinbeforeRij,Ifdiag(i,n)=diag(i,j)andn<j

Homework:Solvethe4queensproblembyusingbacktrackingprocedureandfunctiondiag

BACKTRACK1:toavoidcycle

1.Theargumentoftheprocedureischanged,fromasinglestate

toalistofstate.

2.UseMEMBERfunctiontocheckcycle.

3.AdddepthboundWecanusemoreinformedrule88

2.1BacktrackingStrategies

Asimplerecursiveprocedure

Theinputoftheprocedure,DATA:theinitialstate.

Theoutputoftheprocedure,alistofrules,usingitwecanget

thegoalfromtheinitialstate.Iftheprocedurecannotfindthesolution,itreturnFAIL.

RecursiveprocedureBACKTRCK(DATALIST)1DATA←FIRST(DATALIST);2ifMEMBER(DATA,TAIL(DATALIST)),returnFAIL;3ifTERM(DATA),returnNIL;4ifDEADEND(DATA),returnFAIL;5ifLENGTH(DATALIST)>BOUND,returnFAIL;6RULES←APPRULES(DATA);2.1BacktrackingStrategies897LOOP:ifNULL(RULES),returnFAIL;

8R←FIRST(RULES);

9RULES←TAIL(RULES);

10RDATA←R(DATA);

11RDATALIST←CONS(RDATA,DATALIST);

12PATH←BACKTRACK(RDATALIST);

13ifPATH=FAIL,goLOOP;

14returnCONS(R,PATH)7LOOP:ifNULL(RULES),retu901.2图搜索策略graph-searchstrategies回溯算法只包含一条探索路径,如果发现deadend节点或无规则可用时要退回来,因此可能产生把探索过的节点擦掉后又重新产生的现象.在图搜索算法中.将所有搜索过的状态用一个图(搜索图)记录下来,图的弧反映状态之间的关系.在图中选择节点加以扩展,直至把搜索图扩展到充分大,包含解路径在内.1.2图搜索策略graph-searchstra91Themainideaofgraphsearch

Inthebacktrackingprocedure,wepreserveonlyapathfromtheinitialstatetothecurrentstate,sosometimesweneedtoproductsomestatesagainafterthestateswereremoved.However,ingraphsearchmethod,Wepreserveagraphinthememory,thegraphincludeallthestateswepassedthroughandtherelationoftheirsequences.Whenwefindsomenode(state)inthegraphissuitedtoexpandforsearch,weexpandit,continueoursearching,untilasolutionisfinded.Themainideaofgraphsearch

92图论与状态空间表示

有向图G是一个偶对(N,E),其中N是节点集合，E是有向弧的集合。

DECBA有向图中的有关概念，父亲节点，儿子节点，叶节点，路径，回路，有向树。图论与状态空间表示

有向图G是一个偶对(N,E),93用有向图表示问题的状态空间是一种很自然的方式，节点代表状态描述，弧代表状态之间的转移。

但是，问题的状态描述与有向图又有许多本质上的不同，需要引起我们注意：

1。图论中研究的有向图是有限的，我们可以把有向图全部画出来。而人工智能中描述问题的有向图一般说来是无限的，或者说虽然有限，但是非常大，我们不可能将其画出来。

2。图论中的问题求解是在对图完全了解的情况下进行。而我们对状态空间搜索解的过程是边产生图边求解，这里所产生的图是表示状态空间的无限图的显式部分，从求解的效率考虑，就有把这个无限图的显式部分向哪个方向以何种方式扩展的问题。用有向图表示问题的状态空间是一种很自然的方式，节点代表状态94Motivation:thelimitationofbacktrackingprocedureSometimes,afteranalyzingweneedtoreproducesomestatesagain.DB1DB2DB3DB4R1R2R3DB1DB2DB3DB4R1R2R3952.2graph-searchstrategiesMotivation:thelimitationofbacktrackingprocedureSometimes,afteranalyzingweneedtoreproduces