3-知识的状态空间表示法及搜索问题讨论概要.ppt

知识的状态空间表示法,计算机科学技术学院 陈峰,1 课前思考： 人类的思维过程，可以看作是一个搜索的过程 某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题 2 学习目标： 掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和A搜索算法，对典型问题，掌握启发式函数的定义方法3 学习指南： 了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下，程序实现每一个算法，求解一些典型的问题 4 难重点： 回溯搜索算法、 算法及其性质、改进的Ａ＊算法5 知识点：,本章所要的讨论的问题如下：,有哪些常用的搜索算法 问题有解时能否找到解 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何3.1 状态空间表示知识,一、状态空间表示知识要点 1．状态 状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构通常表示成： Q={q1，q2，……，qn} 当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。

实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用2．操作（规则或算符） 操作（Operator）是把问题从一种状态变成为另一种状态的手段当对一个问题状态使用某个可用操作时，它将引起该状态中某一些分量发生变化，从而使问题由一个具体状态变成另一个具体状态操作可以是一个机械步骤、一个运算、一条规则或一个过程操作可理解为状态集合上的一个函数，它描述了状态之间的关系通常可表示为： F={ f1 , f2,……… fm},3.1 状态空间表示知识（续）,3．状态空间 状态空间（State Space）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间用三元组表示为： （{Qs}，{F}，{Qg}） Qs：初始状态，Qg：目标状态，F：操作（或规则） 4．状态空间（转换）图 状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作3.1 状态空间表示知识（续）,二、状态图搜索 1.搜索方式 用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索 2.搜索策略 大体可分为盲目搜索和启发式（heuristic）搜索两大类。

3.1 状态空间表示知识（续）,,搜索空间示意图,,例3.1 钱币翻转问题 设有三枚硬币，其初始状态为（反，正，反），允许每次翻转一个硬币（只翻一个硬币，必须翻一个硬币）必须连翻三次问是否可以达到目标状态（正，正，正）或（反，反，反） 问题求解过程如下： 用数组表示的话，显然每一硬币需占一维空间，则用三维数组状态变量表示这个知识： Q=（q1 , q2 , q3） 取q=0 表示钱币的正面 q=1 表示钱币的反面,3.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）,3.1 状态空间表示知识（续）,3.1 状态空间表示知识（续）,例3.2 分油问题 有两只空油瓶，容量分别为8斤和6斤，另有一个大油桶，里面有足够的油我们可以任意从油桶中取出油灌满某一油瓶，也可以把某瓶中的油全部倒回油桶，两个油瓶之间可以互相灌。

问如何在8斤油瓶中精确的得到4斤油3.1 状态空间表示知识（续）,问题的求解显然用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斤油瓶中含有的油量 总结出如下分油操作规则：,3.1 状态空间表示知识（续）,f1：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，S）且 E 8 且E+S ≥ 8—→（8，E+S-8） f8：用8斤油瓶内油去灌满6斤油瓶 （E，S）且 S 6 且E+S ≥ 6—→（E+S-6，6）,3.2 搜索问题讨论,（1）求任一解路的搜索策略 回溯法（Backtracking） 爬山法（Hill Climbing） 宽度优先法（Breadth-first） 深度优先法（Depth-first） 限定范围搜索法（Beam Search） 好的优先法（Best-first）,（2）求最佳解路的搜索策略 大英博物馆法（British Museum） 分枝界限法（Branch and Bound） 动态规划法（Dynamic Programming） 最佳图搜索法（A﹡）,（3）求与或关系解图的搜索法 一般与或图搜索法（AO﹡） 极小极大法（Minimax） α－β剪枝法（Alpha-beta Pruning） 启发式剪枝法（Heuristic Pruning）,3.3 图搜索,用计算机进行状态空间问题求解的基本思路： 首先把问题的初始状态（即初结点）作为当前状态，选择合适的算符对其进行操作，生成一组子状态，然后检查目标状态是否在其中出现。

若出现，则搜索成功，若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现，或者不在有可供操作的状态为止一、显示图与隐式图 1．显式图（显式存储） 把与问题有关的全部状态空间以及相应的有关知识（叙述性知识、过程性知识、控制性知识)都直接存入知识库，称为显式图，或“显式存贮” 2．隐式图（隐式存贮） 只存贮与问题有关的部分知识，存贮的状态由初始状态开始运用相应的知识，逐步生成所需的部分状态空间，通过搜索推理，逐渐转移到要求的目标状态，只需在知识库中存贮局部的状态空间，称为“隐式图”或“隐式存贮”通常采用隐式图进行解题（搜索推理）3.3 图搜索（续）,二、 “隐式图”求解问题的一般过程 open表：用于存放刚生成的结点 closed表：用于存放将要扩展或者已扩展的结点,3.3 图搜索（续）,open表,closed 表,搜索过程如下： 1：把初始结点s0放入open表中 2：检查open表是否为空，若空，问题无解，退出 3：把open表中的第一个结点取出放入closed表中，并证实该结点为n结点 4：考察结点n为是否为目标结点，若是，退出 5：扩展结点n,生成一组子结点，把其中不是先辈的那些结点加入open表的尾部，并配以指向父结点的指针。

6：按某种搜索策略对open表中的结点进行排序 7：转入第2步3.3 图搜索（续）,一般的图搜索算法,1、G=G0(G0=s)，OPEN:= (s); 2、CLOSED:=( ); 3、LOOP:IF OPEN=( ) THEN EXIT(FAIL); 4、n:=FIRST(OPEN),REMOVE(n,OPEN), ADD (n,CLOSED), 5、IF GOAL(n) THEN EXIT(SUCCESS); 6、EXPAND(n)→{mi},G:=ADD{mi,G};,→,一般的图搜索算法(续),7、标记和修改指针: ADD (mi,OPEN),并标记mi到n的指针; 计算是否要修改mk、ml到n的指针； 计算是否修改ml到其后续节点的指针； 8、对OPEN中的节点按某种原则重新排序； 9、GO LOOP；,一些基本概念,节点深度 根节点深度=0 其它节点深度=父节点深度+1 路径 设一节点序列为（n0，n1 ，… ，nk）,对于i=1,…,k，若节点ni-1具有一个后续节点ni，则该序列称为从n0到nk的路径 路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。

用C(ni, nj)表示从ni到nj的路径的耗散值 扩展一个节点 生成该节点的所有后续节点,并给出它们之间的耗散值.这一过程称为“扩展一个节点”.,三、广度优先搜索流程图 广度优先搜索的含义：在对第n层结点没有搜索考察完之前，不对第n+1层结点进行搜索，但在隐式图优先搜索中是讲：从初始结点s0开始，按生成规则逐步生成下一级各子结点，在检查同级子结点同时，生成下级子结点并放在open表的末尾，而后再检查下一个同级结点，如不是目标结点，则按规则生成下级子结点，并放在open表末尾，如此下去，直到找到目标为止3.3 图搜索（续）,广度优先搜索算法流程,①G:=G0（G0=s）,OPEN:=(s), CLOSED:=（）； ②LOOP：IF OPEN＝（ ）THEN EXIT（FAIL）； ③n:＝FIRST（OPEN）； ④IF GOAL（n）THEN EXIT（SUCCESS）； ⑤REMOVE（n，OPEN），ADD（n，CLOSED）；,3.3 图搜索（续）,⑥EXPAND（n）→{mi}，G:＝ADD（ mi ，G）； ⑦ IF 目标在 {mi} 中，THEN EXIT（SUCCESS）； ⑧ ADD（OPEN， mj ），并标记 到n的指针； ⑨GO LOOP,3.3 图搜索（续）,宽度优先搜索示例,8数码问题的宽度优先搜索树,广度优先搜索的性质,当问题有解时,一定能找到解 当问题为单位耗散值时,且问题有解时,一定能找到最优解 方法与问题无关,具有通用性 效率较低 属于图搜索方法,3.3 图搜索（续）,四、深度优先搜索流程 从初始结点s0开始，按生成规则逐步生成下一级各子结点，在检查同级子结点同时，生成下级子结点并放在open表的首部，而后再检查下一个同级结点，如不是目标结点，则按规则生成下级子结点，并放在open表首部，如此下去，直到找到目标为止。

3.3 图搜索（续）,深度优先搜索,1、G=G0(G0=s)，OPEN:= (s);，CLOSED:=( ); 2、LOOP:IF OPEN=( ) THEN EXIT(FAIL); 3、n:=FIRST(OPEN), 4、IF GOAL(n) THEN EXIT(SUCCESS); 5、REMOVE(n,OPEN), ADD (n,CLOSED), 6、IF DEPTH(n)Dm GO LOOP; 7、EXPAND(n) → {mi},G:=ADD{mi,G}; 8、IF 目标在{mi}中 THEN EXIT(SUCCESS); 9、ADD(mi,OPEN),并标记mj到n指针; 10、将mi重排序到open表头部 11、GO LOOP;,,,,,,,,,,,,,,,,,,,,,,目标,①,③,④,⑤,⑥,⑦,⑧,⑨,⑩,⑾,⑿,⒀,⒁,②,深度优先搜索性质,一般不能保证找到最优解 当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制 最坏情况时, 搜索空间等于穷举 与回溯法的差别:图搜索 是一个通用的与问题无关的方法,3.4 回溯策略,所谓回溯策略，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。

如果当前状态无规则可用，或者所有规则已经被试探用过。