第3章图搜索与问题求解ppt课件.ppt

《第3章图搜索与问题求解ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、1状态、操作和状态空间3.1.2修道士和野人的状态空间3.1.3梵塔问题的状态空间3.1.4问题求解的基本框架3.1.5重排九宫问题和隐式图9/4/20214人工智能3.1.1状态、操作和状态空间（1）例3.1走迷宫9/4/20215人工智能3.1.1状态、操作和状态空间（2）例3.2八数码问题2831476512384765初始棋局目标棋局以上两个问题抽象来看，都是某个有向图中寻找目标或路径的问题，在人工智能技术中，把这种描述问题的有向图称为状态空间图，简称状态图。9/4/20216人工智能3.1.1状态、操作和状态空间（3）状态（State）为了描述某一类事物中各个不同事物之间的差异

3、而引入的最少的一组变量q的有序组合。表示成矢量形式：状态在状态图中表示为节点。9/4/20217人工智能3.1.1状态、操作和状态空间（4）状态转换规则（操作operator）引起状态中某些分量发生改变，从而使一个具体状态变化到另一个具体状态的作用。它可以是一个机械性的步骤、过程、规则或算子。操作描述了状态之间的关系。状态转换规则在状态图中表示为边。在程序中状态转换规则可用数据对、条件语句、规则、函数、过程等表示。9/4/20218人工智能3.1.1状态、操作和状态空间（5）状态空间（StateSpace）问题的状态空间是一个表示该问题全部的可能状态及相互关系的图。一般用赋值有向图表示，

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

5、S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,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/4/202111人工智能3.1.1状态、操作和状态空间（8）补充例1三枚钱币，能否从下面状态翻动三次后出现全正或全反状态。反正反正正正反反反初始状态θs目标状态集合{θ0,θ7}9/

6、4/202112人工智能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/4/202113人工智能3.1.1状态、操作和状态空间（10）状态空间图（0，0，0

7、）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，0）（1，1，1）acabacabcbbc9/4/202114人工智能3.1.2修道士和野人问题的状态空间（1）补充例2修道士和野人问题。在河的左岸有三个修道士、三个野人河一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运两个人；（2）在任何岸边野人数目都不得超过修道士，否则修道士就会被