第三章 知识的状态空间表示法.docx

第三章知识的状态空间表示法
1 课前思考:
人类的思维过程,可以看作是一个搜索的过程。
某个方案所用的步骤是否最少?也就是说它是最优的吗?如果不是,如何才能找到最优的方案?在计算机上又如何实现这样的搜索?这些问题实际上就是本章我们要介绍的搜索问题。
2 学****目标:
掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法,对典型问题,掌握启发式函数的定义方法。
3 学****指南:
了解算法的每一个过程和细节问题,掌握一些重要的定理和结论,在有条件的情况下,程序实现每一个算法,求解一些典型的问题。
4 难重点:
回溯搜索算法、算法及其性质、改进的A*算法。
5 知识点:

本章所要的讨论的问题如下:
有哪些常用的搜索算法。
问题有解时能否找到解。
找到的解是最佳的吗?
什么情况下可以找到最佳解?
求解的效率如何。
状态空间表示知识
一、状态空间表示知识要点

状态(State)用于描述叙述性知识的一组变量或数组,也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成:
Q={q1,q2,……,qn}
当给每一个分量以确定的值时,就得到一个具体的状态,每一个状态都是一个结点(节点)。实际上任何一种类型的数据结构都可以用来描述状态,只要它有利于问题求解,就可以选用。
(规则或算符)
操作(Operator)是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某个可用操作时,它将引起该状态中某一些分量发生变化,从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数,它描述了状态之间的关系。通常可表示为:
F={ f1 , f2,……… fm}

状态空间(State Space)是由问题的全部及一切可用算符(操作)所构成的集合称为问题的状态空间。用三元组表示为:
({Qs},{F},{Qg})
Qs:初始状态,Qg:目标状态,F:操作(或规则)。
(转换)图
状态空间也可以用一个赋值的有向图来表示,该有向图称为状态空间图,在状态空间图中包含了操作和状态之间的转换关系,节点表示问题的状态,有向边表示操作。
二、状态图搜索

用计算机来实现状态图的搜索,有两种最基本的方式:树式搜索和线式搜索。

大体可分为盲目搜索和启发式(heuristic)搜索两大类。
搜索空间示意图

钱币翻转问题
设有三枚硬币,其初始状态为(反,正,反),允许每次翻转一个硬币(只翻一个硬币,必须翻一个硬币)。必须连翻三次。问是否可以达到目标状态(正,正,正)或(反,反,反)。
问题求解过程如下:
用数组表示的话,显然每一硬币需占一维空间,则用三维数组状态变量表示这个知识:
Q=(q1 , q2 , q3)
取q=0 表示钱币的正面 q=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)
引入操作:
f1:把q1翻一面。
f2:把q2翻一面。
f3:把q3翻一面。
显然:F={f1,f2,f3}
目标状态:(找到的答案) Qg=(0,0,0)或(1,1,1)

分油问题。
有两只空油瓶,容量分别为8斤和6斤,另有一个大油桶,里面有足够的油。我们可以任意从油桶中取出油灌满某一油瓶,也可以把某瓶中的油全部倒回油桶,两个油瓶之间可以互相灌。问如何在8斤油瓶中精确的得到4斤油。
问题的求解显然用2维数组或状态空间描述比较合适,第一位表示8斤油瓶油量,第二位表示6斤油瓶油量,构成整数序列偶(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斤油瓶内油全部装入6斤油瓶内(E,S)E > 0 且E+S ≤ 6—→(0,E+S)
f6:6斤油瓶内油全部装入8斤油瓶内(E,S)S > 0 且 E+S ≤ 8—→(E+S,0)
f7:用6斤油瓶内油去灌满8斤油瓶(E,