资源描述：
《人工智能 搜索问题培训资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、人工智能搜索问题例智力游戏问题：传教士与野人渡河问题传教士与野人渡河问题：有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例设有
2、8数码难题如下:在3×3的框架中有8个标有数字的硬纸片，这些硬纸片上标的数字分别是1，2，…,8，每个纸片都可以移进相邻的空格，8数码难题的初始状态和目标状态分别列出如下，问如何把这个问题由初始状态移向目标状态？2831647512386475InitialGoal8数码难题（8-puzzle）的矩阵描述对于8数码难题，我们选用直接的矩阵描述，解题过程中的任何一个中间情况都对应一个3*3的矩阵，用0,1，2，…,8这9个数的一个排列依次去充填这个矩阵的各个单元,就是求解问题的一个可能的情况,共有9!种。1
3、437658213746582143765821237865212376582137465821374658214317658214357682143786521437865214376358214376258例旅行推销员问题ABDCE75100125125501005075125100125问题表示,形式为(A****)的字符串和(A****A)的字符串。其中****为B,C,D,E的排列.问题的节，形式为(A****A)的字符串,其中****为B,C,D,E的排列.旅行推销员问题的搜索空间EADCBC
4、DEAEDADCEAE100125100751501754252253252753753002501.1回溯策略回溯策略的主要思想:只保留从初始状态到当前状态的一条解路径,给变换状态的规则给出一个排序方法,对当前状态使用规则产生新的状态,不断地向前延伸解路径.当没有规则可用,或向前延伸的状态都是无解状态(称为死点,deadend)时,沿解路径后退到前一个状态(回溯),重新开始搜索,直至找到解或宣布失败.回溯策略是一种穷尽的搜索方法.2.1回溯算法BacktrackingStrategies 递归过程Asi
5、mplerecursiveprocedure 输入:问题的初始状态.. Theinput:theinitialstate. 输出:一个规则表.应用这个规则表可以把初始状态变为目标状态.否则回答FAIL. Theoutputoftheprocedure,alistofrules,usingitwecangetthegoalfromtheinitialstate.Iftheprocedurecannotfindthesolution,itreturnFAIL.RecursiveprocedureBACKTRC
6、K(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,aftergetthelisto
7、frulesusingthefunctionAPPRULES,weneedtoordertherulesinthelists.Theorderingisveryimportant.Ifthe“better” ruleisputinthefrontofthelist,itcanbeusedfirstly,theefficiencyofthesystemishigh.Ifthe“worse”ruleisputinthefront,thesystemneedstotry morerules,theefficie
8、ncyofthesystemispoor. TheExampleofBacktrackingprocedure. The4queenproblem***在利用APPRUKES得到规则表之后,需要对表中的规则排序,把好的规则放在表的前面优先使用,这个排序对算法的效率有很大影响.Theproblemrepresentation theglobaldatabase:4*4array therule:Rij Ifi=1:therea
