图搜索与问题求解.ppt

《图搜索与问题求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章图搜索与问题求解推理与搜索图搜索技术是人工智能的核心技术之一。任一搜索过程也都是一个推理过程。隐式图的搜索过程是一种利用局部性知识构造全局性答案的过程。在各种搜索过程中，人工智能最感兴趣的是那些具有很强选择性的启发式方法，即那些利用很局部的状态空间可以有效地找到问题的解的方法。机器学习等很多过程都是在假设空间中搜索目标的过程。9/6/20212人工智能第3章图搜索与问题求解3.1状态图知识表示（状态图搜索问题求解）3.2状态图搜索3.3与或图知识表示（与或图搜索问题求解）3.4与或图搜索3.5博弈树搜索9/6/20213

2、人工智能3.1状态图知识表示3.1.1状态、操作和状态空间3.1.2修道士和野人的状态空间3.1.3梵塔问题的状态空间3.1.4重排九宫问题和隐式图3.1.5问题求解的基本框架9/6/20214人工智能3.1.1状态、操作和状态空间（1）例3.1走迷宫走迷宫问题就是从该有向图的初始节点出发，寻找目标节点的问题，或者是寻找通向目标节点的路径问题。9/6/20215人工智能3.1.1状态、操作和状态空间（2）例3.2八数码难题(重排九宫问题)2831476512384765初始棋局目标棋局以上两个问题抽象来看，都是某个有向图中寻找

3、目标或路径的问题，在人工智能技术中，把这种描述问题的有向图称为状态空间图，简称状态图。棋局作为节点，相邻节点通过移动数码一个一个产生出来，所有节点由它们的相邻关系连成一个有向图。9/6/20216人工智能3.1.1状态、操作和状态空间（3）状态（State）p62为了描述某一类事物中各个不同事物之间的差异而引入的最少的一组变量q的有序组合，表征了问题的特征和结构。表示成矢量形式：状态在状态图中表示为节点。9/6/20217人工智能3.1.1状态、操作和状态空间（4）状态转换规则（操作operator）引起状态中某些分量发生改变

4、，从而使一个具体状态变化到另一个具体状态的作用。它可以是一个机械性的步骤、过程、规则或算子。操作描述了状态之间的关系。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。9/6/20218人工智能3.1.1状态、操作和状态空间（5）状态空间（StateSpace）问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。状态空间一般用赋值有向图表示，记为：（S，F，G）S：问题的可能有的初始状态的集合；F：操作的集合；G：目标状态的集合。9/6/20219人工智能3.1.1状态、

5、操作和状态空间（6）状态空间中问题求解在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题，也就是寻找操作序列的问题。状态空间的解为三元组Qs：某个初始状态Qg：某个目标状态a：把Qs变换成Qg的有限的操作序列状态转换图S1S3S2…O1O2O3O4QsQgOn9/6/202110人工智能3.1.1状态、操作和状态空间（7）例3.7迷宫问题的状态图表示。S：SoF：｛(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S

6、2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)｝G：Sg迷宫问题规则集描述了图中所有节点和边。类似于这样罗列出全部节点和边的状态图称为显式状态图，或者说状态图的显式表示。9/6/202111人工智能3.1.1状态、操作和状态空间（8）补充例1三枚钱币，能否从下面状态翻动三次后出现全正或全反状态。反正反正正正反反反初始状态θs目标状态集合{θ0,θ7}9/6/202112人工

7、智能3.1.1状态、操作和状态空间（9）引入一个三元组(q0,q1,q2)来描述总状态，钱币正面为0，反面为1，全部可能的状态为：Q0=(0,0,0);Q1=(0,0,1);Q2=(0,1,0)Q3=(0,1,1);Q4=(1,0,0);Q5=(1,0,1)Q6=(1,1,0);Q7=(1,1,1)。翻动钱币的操作抽象为改变上述状态的算子，即F＝{a,b,c}a:把钱币q0翻转一次b:把钱币q1翻转一次c:把钱币q2翻转一次问题的状态空间为<{Q5},{Q0Q7},{a,b,c}>9/6/202113人工智能3.1.1状态、操

8、作和状态空间（10）状态空间图（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，0）（1，1，1）acabacabcbbc9/6/202114人工智能3.1.2修道士和野人问题的状态空间（1）补充例2修道士和野人问题。在河的左岸有三