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

《3-知识的状态空间表示法及搜索问题讨论概要》由会员分享，可在线阅读，更多相关《3-知识的状态空间表示法及搜索问题讨论概要（117页珍藏版）》请在金锄头文库上搜索。

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

2、章所要的讨论的问题如下：,有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。,3.1 状态空间表示知识,一、状态空间表示知识要点 1状态 状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成： Q=q1，q2，qn 当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。,2操作（规则或算符） 操作（Operator）是把问题从一种状态变成为另一种状态的手段。当对

3、一个问题状态使用某个可用操作时，它将引起该状态中某一些分量发生变化，从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。通常可表示为： F= f1 , f2, fm,3.1 状态空间表示知识（续）,3状态空间 状态空间（State Space）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间。用三元组表示为： （Qs，F，Qg） Qs：初始状态，Qg：目标状态，F：操作（或规则）。 4状态空间（转换）图 状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态

4、空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作。,3.1 状态空间表示知识（续）,二、状态图搜索 1.搜索方式 用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。 2.搜索策略 大体可分为盲目搜索和启发式（heuristic）搜索两大类。,3.1 状态空间表示知识（续）,搜索空间示意图,例3.1 钱币翻转问题 设有三枚硬币，其初始状态为（反，正，反），允许每次翻转一个硬币（只翻一个硬币，必须翻一个硬币）。必须连翻三次。问是否可以达到目标状态（正，正，正）或（反，反，反）。 问题求解过程如下： 用数组表示的话，显然每一硬币需占一维空间，则用三维数组状

5、态变量表示这个知识： 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

6、分油问题。 有两只空油瓶，容量分别为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

7、 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） 深度优先法（

8、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 图搜索,用计算机进行状态空间问题求解的基本思路： 首先把问题的初始状态（即初结点）作为当前状态，选择合适的

9、算符对其进行操作，生成一组子状态，然后检查目标状态是否在其中出现。若出现，则搜索成功，若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现，或者不在有可供操作的状态为止。,一、显示图与隐式图 1显式图（显式存储） 把与问题有关的全部状态空间以及相应的有关知识（叙述性知识、过程性知识、控制性知识)都直接存入知识库，称为显式图，或“显式存贮”。 2隐式图（隐式存贮） 只存贮与问题有关的部分知识，存贮的状态由初始状态开始运用相应的知识，逐步生成所需的部分状态空间，通过搜索推理，逐渐转移到要求的目标状态，只需在知识库中存贮局部的状态空间，称为“隐式图”或“

10、隐式存贮”。通常采用隐式图进行解题（搜索推理）。,3.3 图搜索（续）,二、 “隐式图”求解问题的一般过程 open表：用于存放刚生成的结点 closed表：用于存放将要扩展或者已扩展的结点,3.3 图搜索（续）,open表,closed 表,搜索过程如下： 1：把初始结点s0放入open表中。 2：检查open表是否为空，若空，问题无解，退出。 3：把open表中的第一个结点取出放入closed表中，并证实该结点为n结点。 4：考察结点n为是否为目标结点，若是，退出。 5：扩展结点n,生成一组子结点，把其中不是先辈的那些结点加入open表的尾部，并配以指向父结点的指针。 6：按某种搜索策略对

11、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:=ADDmi,G;,一般的图搜索算法(续),7、标记和修改指针: ADD (mi,OPEN),并标记mi到n的指针; 计算是否要修改mk、ml到n的指针； 计算是否修

12、改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层结点没有搜索考察完之前，不

13、对第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，CLO

14、SED）；,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表的首部

15、，而后再检查下一个同级结点，如不是目标结点，则按规则生成下级子结点，并放在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:=ADDmi,G; 8、IF 目标在mi中

16、 THEN EXIT(SUCCESS); 9、ADD(mi,OPEN),并标记mj到n指针; 10、将mi重排序到open表头部。 11、GO LOOP;,目标,深度优先搜索性质,一般不能保证找到最优解 当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制 最坏情况时, 搜索空间等于穷举 与回溯法的差别:图搜索 是一个通用的与问题无关的方法,3.4 回溯策略,所谓回溯策略，简单地说是这样一种策略：首先将规则给出一个固定的排序，在搜索时，对当前状态（搜索开始时，当前状态是初始状态）依次检测每一条规则，在当前状态未使用过的规则中找到第一条可触发规则，被应用于当前状态，得到的新状态重新设置为当前状态，并重复以上搜索。如果当前状态无规则可用，或者所有规则已经被试探用过