文档介绍：第三章知识的状态空间表示法 1 课前思考: 人类的思维过程,可以看作是一个搜索的过程。某个方案所用的步骤是否最少?也就是说它是最优的吗?如果不是, 如何才能找到最优的方案?在计算机上又如何实现这样的搜索?这些问题实际上就是本章我们要介绍的搜索问题。 2 学****目标: 掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和 A 搜索算法,对典型问题, 掌握启发式函数的定义方法。 3 学****指南: 了解算法的每一个过程和细节问题, 掌握一些重要的定理和结论, 在有条件的情况下, 程序实现每一个算法,求解一些典型的问题。 4 难重点: 回溯搜索算法、算法及其性质、改进的A*算法。 5 知识点: 本章所要的讨论的问题如下: 有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗? 什么情况下可以找到最佳解? 求解的效率如何。 状态空间表示知识一、状态空间表示知识要点 1 .状态状态( State )用于描述叙述性知识的一组变量或数组,也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成: Q={q1 , q2, ……, qn} 当给每一个分量以确定的值时, 就得到一个具体的状态, 每一个状态都是一个结点( 节点)。实际上任何一种类型的数据结构都可以用来描述状态, 只要它有利于问题求解, 就可以选用。 2 .操作(规则或算符) 操作( Operator ) 是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某个可用操作时, 它将引起该状态中某一些分量发生变化, 从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数,它描述了状态之间的关系。通常可表示为: F={ f1, f2, ……… fm} 3 .状态空间状态空间( State Space ) 是由问题的全部及一切可用算符( 操作) 所构成的集合称为问题的状态空间。用三元组表示为: ( {Qs} , {F} , {Qg} ) Qs :初始状态, Qg :目标状态, F :操作(或规则)。 4 .状态空间(转换)图状态空间也可以用一个赋值的有向图来表示, 该有向图称为状态空间图, 在状态空间图中包含了操作和状态之间的转换关系,节点表示问题的状态,有向边表示操作。二、状态图搜索 1. 搜索方式用计算机来实现状态图的搜索,有两种最基本的方式:树式搜索和线式搜索。 2. 搜索策略大体可分为盲目搜索和启发式( 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 斤油瓶内油去