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

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

本章所要的讨论的问题如下：
有哪些常用的搜索算法。
问题有解时能否找到解。
找到的解是最佳的吗？
什么情况下可以找到最佳解？
求解的效率如何。
状态空间体现知识
一、状态空间体现知识要点
1．状态
状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解历程中任意时刻的数据结构。通常体现成：
Q={q1，q2，……，qn}
当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。
2．操纵（规矩或算符）
操纵（Operator）是把问题从一种状态酿成为另一种状态的手段。当对一个问题状态使用某个可用操纵时，它将引起该状态中某一些分量产生变革，从而使问题由一个具体状态酿成另一个具体状态。操纵可以是一个机器步调、一个运算、一条规矩或一个历程。操纵可理解为状态聚集上的一个函数，它描述了状态之间的干系。通常可体现为：
F={ f1 , f2,……… fm}
3．状态空间
状态空间（State Space）是由问题的全部及一切可用算符（操纵）所组成的聚集称为问题的状态空间。用三元组体现为：
（{Qs}，{F}，{Qg}）
Qs：初始状态，Qg：目标状态，F：操纵（或规矩）。
4．状态空间（转换）图
状态空间也可以用一个赋值的有向图来体现，该有向图称为状态空间图，在状态空间图中包罗了操纵和状态之间的转换干系，节点体现问题的状态，有向边体现操纵。
二、状态图搜索

用盘算机来实现状态图的搜索，有两种最根本的方法：树式搜索和线式搜索。

大要可分为盲目搜索和启发式（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