第二章知识的状态空间表示法
1课前思考： 人类的思维过程，可以看作是一个搜索的过程。 某个方案所用的步骤是否最少？也就是说它
是最优的吗？如果不是，
如何才能找到最优的方
案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。
2学习目标：
掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和 掌握启发式函数的定义方法。
A搜索算法，对典型问题,
3学习指南:
了解算法的每一个过程和细节问题, 掌握一些重要的定理和结论, 实现每一个算法，求解一些典型的问题。
在有条件的情况下，程序
4难重点：
回溯搜索算法、
算法及其性质、改进的A*算法。
5知识点:
r-Ψ,≡i7t?
盲目搜索
本章所要的讨论的问题如下： 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。
3.1 状态空间表示知识
一、状态空间表示知识要点
1. 状态
状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中 任意时刻的数据结构。通常表示成：
Q={q1, q2,……,qn}
当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。
实际上任何一种类型的数据结构都可以用来描述状态,
只要它有利于问题求解，就可以选用。
2 ?操作（规则或算符）
操作（OPerator）是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某 个可用操作时，它将引起该状态中某一些分量发生变化，
从而使问题由一个具体状态变成另
一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为 状态集合上的一个函数，它描述了状态之间的关系。通常可表示为：
F={ fl , f2, .... fm} 3 .状态空间
状态空间（State SPaCe）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的 状态空间。用三元组表示为： （{Qs}, {F}, {Qg}）
Qs:初始状态，Qg:目标状态，F：操作（或规则）。 4 .状态空间（转换）图
状态空间也可以用一个赋值的有向图来表示，
该有向图称为状态空间图，
在状态空间图中包
含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作。 二、状态图搜索
1?搜索方式
用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。
2?搜索策略
大体可分为盲目搜索和启发式（heuristic）搜索两大类。 搜索空间示意图
例3.1钱币翻转问题
设有三枚硬币，其初始状态为（反，正，反）
，允许每次翻转一个硬币（只翻一个硬币，必
须翻一个硬币）。必须连翻三次。问是否可以达到目标状态 （正，正，正）或（反，反，反）。 问题求解过程如下：
用数组表示的话，显然每一硬币需占一维空间，则用三维数组状态变量表示这
个知识：
Q= （q1 ,q2,q3）
取q=0表示钱币的正面 构成的问题状q=1表示钱币的反面 态空间显然为：
Qo= ( 0, 0, 0), Q仁(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)
f1: 把 q1 翻一面。 f2:把q2翻一面。 f3:把q3翻一面。
显然：F={f1, f2, f3} 目标状态：(找到的答案)
Qg= (0, 0, 0)或(1, 1, 1)
例 3.2分油问题。
有两只空油瓶，容量分别为8斤和6斤，另有一个大油桶，里面有足够的油。 我们可 以任意从油桶
中取出油灌满某一油瓶， 也可以把某瓶中的油全部倒回油桶， 两个油瓶之间可 以互相灌。问如何在 8斤油瓶中精确的得到 4斤油。
问题的求解显然用 2维数组或状态空间描述比较合适， 示6斤油瓶油量，构成整数序列偶(
第一位表示8斤油瓶油量，第二位表
E, S)
E： =0, 1, 2, 3, 4, 5, 6, 7, 8。表示8斤油瓶中含有的油量。 S: =0, 1 , 2, 3, 4, 5, 6。表示6斤油瓶中含有的油量。
总结出如下分油操作规则：
f1： 8斤油瓶不满时装满(E, S)且E < 8-- ( 8 , S) f2： 6斤油瓶不满时装满(E, S)且S < 6-- ( E , 6) f3： 8斤油瓶不空时倒空(E, S)且E > 0-- ( 0 , S) f4： 6斤油瓶不空时倒空(E, S)且S > 0-- ( E , 0)
f5 : 8斤油瓶内油全部装入 f66斤油瓶内油全部装入 ： 用6斤油瓶内油去灌满 f7
： f8用8斤油瓶内油去灌满
6斤油瓶内 (E, S) E > 0且E+S ≤ 6( 0 , E+S) 8斤油瓶内 8斤油瓶 6斤油瓶
(E , S) S > 0 且 E+S ≤ 8— →( E+S, 0) (E , S) 且 E < 8 且 E+S ≥ 8( 8 , E+S-8) (E , S) 且 S < 6 且 E+S ≥ 6( E+S-6 6)
3.2 搜索问题讨论 first)
深度优先法(DePth-first)
：
(1) 求任一解路的搜索策略 回溯法(BaCktraCking) 爬山法(HillClimbing ) 宽度优先法(Breadth-
限定范围搜索法(Beam SearCh)
第三章知识的状态空间表示法
