B-搜索问题-人工智能(AI).ppt

《B-搜索问题-人工智能(AI).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、搜索问题(对可能的选择进行探索，也是一种推理的过程)R&N:Chap.3,Sect.3.1–2+3.61描述性的知识创造了多种可能的选择：●那么应该使用哪条的知识呢？●如何使用呢？搜索就是对可能的选择的探索.是探索知识的一种主要方法Search搜索Knowledgerep.知识表示Planning规划Reasoning推理Learning学习Agent智能体Robotics机器人Perception感知Naturallanguage自然语言...ExpertSystems专家系统Constraintsatisfaction约束满足2Exam

2、ple:8-Puzzle1234567812345678InitialstateGoalstate状态：3×3棋盘上8个数码牌和空位的任意一种布局38-Puzzle:后继函数12345678123456781234567812345678搜索是对可能的选择的探索后继函数是有关8数码问题的知识，但它不是告诉我们应该选择哪一个结果，也不是告诉我们应该应用棋局的哪一种状态的知识。4纵观历史，数码问题和博弈（如棋类）需要在众多的可能选项中进行选择，被认为是对人类智能的巨大挑战：象棋大约4000年前起源于波斯和印度跳棋大约于3600年出现在埃及围棋源于300

3、0多年前的中国因此，AI针对博弈游戏来设计及测试算法并不让人觉得意外5615-Puzzle据说在1878年，自称为“美立坚最伟大数码问题专家”的SamLoyd，发出悬赏15数码问题715-PuzzleSamLoyd自掏腰包悬赏，第一个解决下面15数码问题的人将得到$1,000的赏金:121411151013956784321121511141013956784321?8Butnooneeverwontheprize!!9把问题描述为搜索问题StatespaceS（状态空间）Successorfunction（后继函数）:xSSUCCESSOR

4、S(x)2SInitialstates0（初始状态）Goaltest（目标测试）:xSGOAL?(x)=TorFArccost（弧的耗散）S13210StateGraph状态图每一个状态被描述为一个不同的节点每一段弧（或边）连接节点s和节点s’，若s’SUCCESSORS(s)状态图可以包含多个连通图11搜索问题的解SolutiontotheSearchProblem问题的一个解即为连接初始节点与（任一）目标节点的路径IG12SolutiontotheSearchProblem问题的一个解即为连接初始节点与（任一）目标节点的路径一条路径的耗

5、散即为该路径上所有弧的耗散的和最优解即为有着最小耗散的解路径可能无解！IG13(n2-1)数码问题的状态空间到底有多大？8-puzzle??states14(n2-1)数码问题的状态空间到底有多大？8-puzzle9!=362,880states15-puzzle16!~2.09x1013states24-puzzle25!~1025states但其中只有一半的状态才是可以到达的（但事先无法知道具体是哪一些状态）15Wlg,letthegoalbe:Atilejappearsafteratileiif,ifeitherjappearso

6、nthesamerowasitotherightofi,oronanotherrowbelowtherowofi.Foralli=1,2,...,15,letnibethenumberoftilesj

7、=4n11=0n12=0n13=0n14=0n15=0N=7+416Proposition:(Nmod2)isinvariantunderanylegalmoveoftheemptytileProof:AnyhorizontalmoveoftheemptytileleavesNunchangedAverticalmoveoftheemptytilechangesNbyanevenincrement(1111)121511141013956784321s=121511141013956784321s’=N(s’)=N(s)+3+117Pro

8、position:(Nmod2)isinvariantunderanylegalmoveoftheemptytileFo