搜索
人工智能吉林大学珠海学院计算机科学与技术系第1章搜索问题1.什么是状态空间？2.回溯策略。3.图搜索策略4.无信息的图搜索策略5.启发式图搜索策略6.A*算法。7.A*算法的性质。8.搜索算法的讨论。人工智能吉林大学珠海学院计算机科学与技术系状态空间1.计算机对传统的问题求解方法带来了根本性的改变。传统方法，由专家给出公式，使用者的任务是理解公式，应用公式。有些问题用传统方法描述很困难,例如本节的几个例子公式的推导需要很高的水平，与实际问题相差较远，对应用者要求很高。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）2831647512386475初始状态Initial目标状态Goal例设有8数码难题如下:在3×3的框架中有8个标有数字的硬纸片，这些硬纸片上标的数字分别是1，2，…,8，每个纸片都可以移进相邻的空格，8数码难题的初始状态和目标状态分别列出如下，问如何把这个问题由初始状态移向目标状态？人工智能吉林大学珠海学院计算机科学与技术系2831647512386475InitialGoal8数码难题（8-puzzle）的矩阵描述对于8数码难题，我们选用直接的矩阵描述，解题过程中的任何一个中间情况都对应一个3*3的矩阵，用0,1，2，…,8这9个数的一个排列依次去充填这个矩阵的各个单元,就是求解问题的一个可能的情况,共有9!种。人工智能吉林大学珠海学院计算机科学与技术系1437658213746582143765821237865212376582137465821374658214317658214357682143786521437865214376358214376258人工智能吉林大学珠海学院计算机科学与技术系例旅行推销员问题ABDCE75100125125501005075125100125问题表示,形式为(A****)的字符串和(A****A)的字符串。其中****为B,C,D,E的排列.问题的节，形式为(A****A)的字符串,其中****为B,C,D,E的排列.人工智能吉林大学珠海学院计算机科学与技术系旅行推销员问题的搜索空间EADCBCDEAEDADCEAE10012510075150175425225325275375300250人工智能吉林大学珠海学院计算机科学与技术系1.1回溯策略回溯策略的主要思想:只保留从初始状态到当前状态的一条解路径,给变换状态的规则给出一个排序方法,对当前状态使用规则产生新的状态,不断地向前延伸解路径.当没有规则可用,或向前延伸的状态都是无解状态(称为死点,deadend)时,沿解路径后退到前一个状态(回溯),重新开始搜索,直至找到解或宣布失败.回溯策略是一种穷尽的搜索方法.人工智能吉林大学珠海学院计算机科学与技术系2.1回溯算法BacktrackingStrategies递归过程Asimplerecursiveprocedure输入:问题的初始状态..Theinput:theinitialstate.输出:一个规则表.应用这个规则表可以把初始状态变为目标状态.否则回答FAIL.Theoutputoftheprocedure,alistofrules,usingitwecangetthegoalfromtheinitialstate.Iftheprocedurecannotfindthesolution,itreturnFAIL.RecursiveprocedureBACKTRCK(DATA)1ifTERM(DATA),returnNIL;2ifDEADEND(DATA),returnFAIL;3RULES←APPRULES(DATA);人工智能吉林大学珠海学院计算机科学与技术系4LOOP:ifNULL(RULES),returnFAIL;5R←FIRST(RULES);6RULES←TAIL(RULES);7RDATA←R(DATA);8PATH←BACKTRACK(RDATA);9ifPATH=FAIL,goLOOP;10returnCONS(R,PATH)人工智能吉林大学珠海学院计算机科学与技术系Instep3,aftergetthelistofrulesusingthefunctionAPPRULES,weneedtoordertherulesinthelists.Theorderingisveryimportant.Ifthe“better”ruleisputinthefrontofthelist,itcanbeusedfirstly,theefficiencyofthesystemishigh.Ifthe“worse”ruleisputinthefront,thesystemneedstotrymorerules,theefficiencyofthesystemispoor.TheExampleofBacktrackingprocedure.The4queenproblem***在利用APPRUKES得到规则表之后,需要对表中的规则排序,把好的规则放在表的前面优先使用,这个排序对算法的效率有很大影响.人工智能吉林大学珠海学院计算机科学与技术系Theproblemrepresentationtheglobaldatabase:4*4arraytherule:RijIfi=1:therearenoqueeninthearray1i=4:Thereisaqueenintherowi-1thenputaqueenintherowi,columnjWeordertherulesaccordingtothecolumn.我们用Rij表示在棋盘的第i行第j列放一个王后.按行的增加顺序依次放皇后,在规则的排序上依列的上升次序排序.Terminationcondition:thereare4queensinthechessboard,theycannotkilleachother.终止条件:4皇后都放到棋盘上,且不能互相杀死.人工智能吉林大学珠海学院计算机科学与技术系Orderofrules:R11,R12,R13,R14R21,R22,R23,R24deadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadenddeadendTheremanybacktrackNIL()(R43)(R31,R43)(R24,R31,R43)(R12,R24,R31,R43)人工智能吉林大学珠海学院计算机科学与技术系Wecanusemoreinformedruleorderingusingfunctiondiag(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)andnjHomework:Solvethe4queensproblembyusingbacktrackingprocedureandfunctiondiagBACKTRACK1:toavoidcycle1.Theargumentoftheprocedureischanged,fromasinglestatetoalistofstate.2.UseMEMBERfunctiontocheckcycle.3.Adddepthbound人工智能吉林大学珠海学院计算机科学与技术系2.1BacktrackingStrategiesAsimplerecursiveprocedureTheinputoftheprocedure,DATA:theinitialstate.Theoutputoftheprocedure,alistofrules,usingitwecangetthegoalfromtheinitialstate.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);人工智能吉林大学珠海学院计算机科学与技术系7LOOP: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)人工智能吉林大学珠海学院计算机科学与技术系1.2图搜索策略graph-searchstrategies回溯算法只包含一条探索路径,如果发现deadend节点或无规则可用时要退回来,因此可能产生把探索过的节点擦掉后又重新产生的现象.在图搜索算法中.将所有搜索过的状态用一个图(搜索图)记录下来,图的弧反映状态之间的关系.在图中选择节点加以扩展,直至把搜索图扩展到充分大,包含解路径在内.人工智能吉林大学珠海学院计算机科学与技术系ThemainideaofgraphsearchInthebacktrackingprocedure,wepreserveonlyapathfromtheinitialstatetothecurrentstate,sosometimesweneedtoproductsomestatesagainafterthestateswereremoved.However,ingraphsearchmethod,Wepreserveagraphinthememory,thegraphincludeallthestateswepassedthroughandtherelationoftheirsequences.Whenwefindsomenode(state)inthegraphissuitedtoexpandforsearch,weexpandit,continueoursearching,untilasolutionisfinded.人工智能吉林大学珠海学院计算机科学与技术系图论与状态空间表示有向图G是一个偶对(N,E),其中N是节点集合，E是有向弧的集合。DECBA有向图中的有关概念，父亲节点，儿子节点，叶节点，路径，回路，有向树。人工智能吉林大学珠海学院计算机科学与技术系用有向图表示问题的状态空间是一种很自然的方式，节点代表状态描述，弧代表状态之间的转移。但是，问题的状态描述与有向图又有许多本质上的不同，需要引起我们注意：1。图论中研究的有向图是有限的，我们可以把有向图全部画出来。而人工智能中描述问题的有向图一般说来