翻动钱币的操作抽象为改变上述状态的算子，
即F＝{a, b, c}
a:把钱币q0翻转一次 b:把钱币q1翻转一次 c:把钱币q2翻转一次 问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}>
04.12.2020
ppt课件
13
3.1.1 状态、操作和状态空间（10）
状态空间图 a
c （0，0，0） （1，0，0） b
迷宫问题规则集描述了图中所有节点和边。类似于 这样罗列出全部节点和边的状态图称为显式状态图， 或者说状态图的显式表示。
04.12.2020
ppt课件
11
3.1.1 状态、操作和状态空间（8）
补充例1 三枚钱币，能否从下面状态翻动三次后 出现全正或全反状态。
正
正
正
反
正
反
反
反
反
初始状态θs
04.12.2020
3.1.1 状态、操作和状态空间 3.1.2 修道士和野人的状态空间 3.1.3 梵塔问题的状态空间 3.1.4 重排九宫问题和隐式图 3.1.5 问题求解的基本框架
04.12.2020
ppt课件
4
3.1.1状态、操作和状态空间（1）
例3.1走迷宫
走迷宫问题就是从该有向图的初始节点出发，寻找目 标节点的问题，或者是寻找通向目标节点的路径问题。
状态转换图
O1
O2
O3
O4
On
Qs
S1
S2
S3
…
Qg
04.12.2020
ppt课件
10
3.1.1 状态、操作和状态空间（7）
例 3.7 迷宫问题的状态图表示。
S：So
F：｛(So, S4), (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
中状态转换规则可用数据对、条件语句、规 则、函数、过程等表示。
04.12.2020
ppt课件
8
3.1.1 状态、操作和状态空间（5）
状态空间（State Space）
问题的状态空间是一个表示该问题全部的可 能状态及相互关系的图。
状态空间一般用赋值有向图表示，记为： （S，F，G）
S：问题的可能有的初始状态的集合； F：操作的集合； G：目标状态的集合。
（0，0，1）
c
a
（1，0，1）
b
b
（1，1，0）
a
c
（0，1，0）
b
c
（1，1，1） a （0，1，0）
04.12.2020
ppt课件
14
3.1.2 修道士和野人问题的状态空间（1）
补充例2 修道士和野人问题。在河的左岸有三个 修道士、三个野人和一条船，修道士们想用这 条船将所有的人都运过河去，但受到以下条件 的限制：
机器学习等很多过程都是在假设空间中搜索 目标的过程。
04.12.2020
ppt课件
2
第3章 图搜索与问题求解
3.1 状态图知识表示（状态图搜索问题求解） 3.2 状态图搜索 3.3 与或图知识表示（与或图搜索问题求解 ） 3.4 与或图搜索 3.5 博弈树搜索
04.12.2020
ppt课件
3
3.1 状态图知识表示
04.12.2020
ppt课件
5
3.1.1 状态、操作和状态空间（2）
例3.2八数码难题(重排九宫问题)
28 3
1
4
76 5
12 3
8
4
76 5
初始棋局
目标棋局
棋局作为节点，相邻节点通过移动数码一个一个产生
出来，所有节点由它们的相邻关系连成一个有向图。
以上两个问题抽象来看，都是某个有向图中寻找目标 或路径的问题，在人工智能技术中，把这种描述问题 的有向图称为状态空间图，简称状态图。
04.12.2020
ppt课件
6
3.1.1 状态、操作和状态空间（3）
状态（State）p62
为了描述某一类事物中各个不同事物之间 的差异而引入的最少的一组变量q的有序 组合，表征了问题的特征和结构。
表示成矢量形式：
q0
Q
q1
＝
q 0，q1，q 2，
T
q2
状态在状态图中表示为节点。
目标状态集合{θ0, θ7}
ppt课件
12
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)。
第3章 图搜索与问题求解
推理与搜索
图搜索技术是人工智能的核心技术之一。
任一搜索过程也都是一个推理过程。
隐式图的搜索过程是一种利用局部性知识构 造全局性答案的过程。
在各种搜索过程中，人工智能最感兴趣的是 那些具有很强选择性的启发式方法，即那些 利用很局部的状态空间可以有效地找到问题 的解的方法。
04.12.2020
ppt课件
9
3.1.1 状题求解
在状态空间表示法中，问题求解过程转化为在图中 寻找从初始状态Qs出发到达目标状态Qg的路径问题， 也就是寻找操作序列的问题。
状态空间的解为三元组< Qs, a, Qg > Qs ：某个初始状态 Qg ：某个目标状态 a：把Qs变换成Qg的有限的操作序列
04.12.2020
ppt课件
7
3.1.1 状态、操作和状态空间（4）
状态转换规则（操作 operator）
引起状态中某些分量发生改变，从而使一个 具体状态变化到另一个具体状态的作用。
它可以是一个机械性的步骤、过程、规则或 算子。
操作描述了状态之间的关系。 状态转换规则在状态图中表示为边。在程序
（1）修道士和野人都会划船，但船一次最 多只能运两个人；
（2）在任何岸边野人数目都不得超过修道 士，否则修道士就会被野人吃掉。
假定野人会服从任何一种过河安排，试规划 出一种确保修道士安全过河方案。
04.12.2020
ppt课件
15
3.1.2 修道士和野人问题的状态空间（2）
解：先建立问题的状态空间。问题的状态可以用 一个三元数组来描述： S＝(m, c, b) m：左岸的修道士数 c：左岸的野人数 b：左岸的船数 右岸的状态不必标出，因为： 右岸的修道士数m’＝3－m 右岸的野人数c’＝3－c 右岸的船数b’=1-b