《知识的状态空间表示法》由会员分享，可在线阅读，更多相关《知识的状态空间表示法（29页珍藏版）》请在金锄头文库上搜索。
1、第三章知识的状态空间表示法1课前思考：人类的思维过程，可以看作是一个搜索的过程。某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。2学习目标：掌握回溯搜索算法、 深度优先搜索算法、 宽度优先搜索算法和 A搜索算法，对典型问题，掌 握启发式函数的定义方法。3学习指南：了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下， 程序实现每一个算法，求解一些典型的问题。4难重点：回溯搜索算法、算法及其性质、改进的A *算法。5知识点：本章所要的讨论的问题如下：有哪些常用的搜
2、索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。状态空间表示知识一、状态空间表示知识要点1 .状态状态（State ）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成：Q=q1, q2,qn)当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点(节点)。实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。2 .操作(规则或算符)操作(Operator )是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某个可用操作时，它将引起该状态中某一些分
3、量发生变化，从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为 状态集合上的一个函数，它描述了状态之间的关系。通常可表示为：F= fl , f2, fm)3 .状态空间状态空间(State Space )是由问题的全部及一切可用算符(操作)所构成的集合称为问题 的状态空间。用三元组表示为：(Qs) , F , Qg)Qs：初始斗犬态,Qg：目标犬态,F：操作(或规则)。4 .状态空间(转换)图状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作
4、。二、状态图搜索1 .搜索方式用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。2 .搜索策略大体可分为盲目搜索和启发式(heuristic )搜索两大类。搜索空间示意图例钱币翻转问题 设有三枚硬币，其初始状态为(反，正，反) ，允许每次翻转一个硬币(只翻一个硬币，必 须翻一个硬币)。必须连翻三次。问是否可以达到目标状态(正，正，正)或(反，反，反)问题求解过程如下：用数组表示的话，显然每一硬币需占一维空间，则用三维数组状态变量表示这个知识：Q= (q1 , q2 , q3 )取q=0表示钱币的正面 q=1 表示钱币的反面构成的问题状态空间显然为：Q0=(0,0,0),Q1=
5、 (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斤油。问题的求解显
6、然用 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, S)f2 :6斤油瓶不满时装满(E,S)且S (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 ( 0, E+S
7、)f6:6斤油瓶内油全部装入8斤油瓶内(E,S)S 0且E+S ( E+S0)f7 :用6斤油瓶内油去灌满8斤油瓶(E,S)且E 8 -( 8, E+S-8)f8 :用8斤油瓶内油去灌满6斤油瓶(E,S)且S 6 -( E+S-6, 6)搜索问题讨论(1)求任一解路的搜索策略回溯法(Backtracking )爬山法(Hill Climbing )宽度优先法(Breadth-first )深度优先法(Depth-first )限定范围搜索法(Beam Search)好的优先法(Best-first )(2)求最佳解路的搜索策略大英博物馆法(British Museum )分枝界限法(Branc
8、h and Bound )动态规划法( Dynamic Programming )最佳图搜索法(A* )(3)求与或关系解图的搜索法一般与或图搜索法(AO* )极小极大法(Minimax)a - 3 剪枝法(Alpha-beta Pruning )启发式剪枝法(Heuristic Pruning )图搜索用计算机进行状态空间问题求解的基本思路：首先把问题的初始状态（即初结点）作为当前状态，选择合适的算符对其进行操作，生成一组子状态，然后检查目标状态是否在其中出现。若出现，则搜索成功，若不出现，则按 某种搜索策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现，或者不在有
9、可供操作的状态为止。一、显示图与隐式图1 .显式图（显式存储）把与问题有关的全部状态空间以及相应的有关知识（叙述性知识、过程性知识、控制性知识）都直接存入知识库，称为显式图，或“显式存贮”。2 .隐式图（隐式存贮）只存贮与问题有关的部分知识，存贮的状态由初始状态开始运用相应的知识，逐步生成所需的部分状态空间，通过搜索推理，逐渐转移到要求的目标状态，只需在知识库中存贮局部的状态空间，称为“隐式图”或“隐式存贮” 。通常采用隐式图进行解题（搜索推理）。二、“隐式图”求解问题的一般过程open表：用于存放刚生成的结点closed表：用于存放将要扩展或者已扩展的结点图搜索（续）状态节点父节点编P状态节
10、点父节点open 表closed 表搜索过程如下：1:把初始结点 s0放入open表中。2：检查open表是否为空，若空，问题无解，退出。3:把open表中的第一个结点取出放入closed表中，并证实该结点为 n结点。4：考察结点n为是否为目标结点，若是，退出。5:扩展结点n,生成一组子结点，把其中不是先辈的那些结点加入open表的尾部，并配以指向父结点的指针。6:按某种搜索策略对 open表中的结点进行排序7：转入第2步。一般的图搜索算法1、G=G0(G0=s), OPEN:= (s);2、CLOSED:=();3、LOOP:IF OPEN=( ) THEN EXIT(FAIL);4、n:=
11、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的指针；计算是否修改 ml到其后续节点的指针；8、对OPEN的节点按某种原则重新排序；9、GO LOOP一些基本概念 节点深度根节点深度=0其它节点深度=父节点深度+1路径设一节点序列为(n0, n1 ,，nk),对于i=1,k ,若节点ni-1具有一个后续节点 ni , 则该序列称为从 n0到nk
12、的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj) 表示从ni到nj的路径的耗散值。扩展一个节点生成该节点的所有后续节点，并给出它们之间的耗散值.这一过程称为“扩展一个节点”.三、广度优先搜索流程图广度优先搜索的含义：在对第n层结点没有搜索考察完之前，不对第n+1层结点进行搜索，但在隐式图优先搜索中是讲：从初始结点s0开始，按生成规则逐步生成下一级各子结点，在检查同级子结点同时，生成下级子结点并放在open表的末尾，而后再检查下一个同级结点，如不是目标结点，则按规则生成下级子结点，并放在open表末尾，如此下去，直到找到目标为止。广度优先搜索算法
13、流程G:=G0 (G0=s) ,OPEN:=(s), CLOSED:=();LOOP IF OPEN= ( ) THEN EXIT (FAIL);n: = FIRST (OPEN；IF GOAL (n) THEN EXIT (SUCCESSREMOVEn, OPEN, ADD(n, CLOSED；EXPAND(n) - mi , G:=ADD( mi , G); IF 目标在mi 中，THEN EXIT (SUCCESSADD (OPEN mj ),并标记 到n的指针；GO LOOP宽度优先搜索示例8数码问题的宽度优先搜索树广度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值时，且问
14、题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法四、深度优先搜索流程从初始结点S0开始，按生成规则逐步生成下一级各子结点，在检查同级子结 点同时，生成下级子结点并放在 open表的首部，而后再检查下一个同级结点，如不是目标 结点，则按规则生成下级子结点，并放在 open表首部，如此下去，直到找到目标为止。深度优先搜索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中 THEN EXIT(SUCCESS);9、ADD(mi,OPEN),并标记 mj 到 n 指针；10、将mi重排序到open表头部。11、GO LOOP;深度优先搜索性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改
