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