2.2.3 知识表示与问题求解(状态空间法).ppt

1,智能控制技术,上海大学机电工程与自动化学院杜鑫,2,2.2知识表示与问题求解,知识表示与问题求解,2.2.1一阶谓词知识表示法,2.2.2产生式知识表示法,2.2.3状态空间法,3,2.2知识表示与问题求解,知识表示与问题求解,2.2.1一阶谓词知识表示法,2.2.2产生式知识表示法,2.2.3状态空间法,-2.2.3.1基于状态空间法的问题描述,例:三数码难题（3puzzleproblem）,初始棋局,目标棋局,2.2.3状态空间法,5,状态空间表示法就是以“状态空间”的形式来表示问题及其搜索过程的一种方法。,状态空间表示法是人工智能中最基本的形式化方法，是讨论问题求解技术的基础。,2.2.3状态空间法,6,1.状态是描述问题求解过程中不同时刻状况的数据结构。一般用一组变量的有序集合表示：Q=(q0，q1，.，qn)其中每个元素qi(i=0，l，2，n)为状态变量。,2.2.3.1问题状态空间的构成,当给每一个变量以确定的值时，就得到了一个具体的状态。,2.2.3状态空间法,7,算符：引起状态中某些变量发生变化，从而使问题由一个状态变为另一个状态的操作。,2.算符,算符可分为走步、过程、规则、数学算子、运算符号、逻辑符号等。,例如：在产生式系统中，每一条产生式规则就是一个算符；而在下棋程序中，一个算符就是一个走步。,2.2.3.1问题状态空间的构成,2.2.3状态空间法,8,状态空间：一个问题的全部状态及一切可用算符构成的集合。,3.状态空间,状态空间由三部分构成：问题的所有可能初始状态构成的集合S；算符集合F；目标状态集合G。,用一个三元组表示为：(S，F，G),2.2.3.1问题状态空间的构成,2.2.3状态空间法,9,状态空间图：状态空间的图示形式。其中节点表示状态；有向边(弧)表示算符。,3.状态空间,2.2.3.1问题状态空间的构成,2.2.3状态空间法,10,状态空间的问题求解就是从问题的初始状态集S出发，经过一系列的算符运算，到达目标状态。,4.问题的解,由初始状态到目标状态所用算符的序列就构成了问题的一个解。,2.2.3.1问题状态空间的构成,2.2.3状态空间法,11,(1)定义状态的描述形式。,2.2.3.2用状态空间表示问题的步骤,(2)用所定义的状态描述形式把问题的所有可能的状态都表示出来，并确定出问题的初始状态集合描述和目标状态集合描述。,(3)定义一组算符，使得利用这组算符可把问题由一种状态转变为另一种状态。问题求解过程是一个不断把算符作用于状态的过程,2.2.3状态空间法,(4)首先将适用算符作用于初始状态，以产生新的状态；(5)然后再把一些适用的算符作用于新的状态；这样继续下去，直到产生的状态为目标状态为止。(6)这时，就得到了问题的一个解，这个解是从初始状态到目标状态所用算符构成的序列。,问题：最优解问题；搜索策略问题。,2.2.3.2用状态空间表示问题的步骤,2.2.3状态空间法,13,例如下棋、迷宫及各种游戏。,MiddleState,GoalState,2.2.3.2用状态空间表示问题的步骤,2.2.3状态空间法,14,Hanoi塔,2.2.3状态空间法,在梵城（Hana）地下有一个僧侣的秘密组织，他们有3个大型的塔柱，左边的塔柱上由方到小套着64个金盘。僧侣们的工作是要把这64个金盘从左边塔柱转移到右边塔柱上去。但转移过程有规定的：1、每次只能搬动一只盘子，盘十只能在3个塔柱上安放，不允许放在地上；2、在每个塔柱上，只允许把小盘十叠在大盘上，反之不允许。据传说，僧侣们完成这个任务时，世界的末日就来临了。,15,Hanoi塔,2.2.3状态空间法,19世纪，法国的一位数学家douardLucas(18421891)对该课题进行过研究，他指示，要完成这个任务，僧侣们搬动金盘的总次数：18446744073709551615（20位）假设僧侣们个个身强力壮，每天24小时不知头疲倦地工作，而且一秒钟移动一个金盘，那么，完成这个任务也得花5800亿年。,16,Hanoi塔,2.2.3状态空间法,观自在菩萨，行深般若波罗蜜多时，照见五蕴皆空，度一切苦厄。舍利子，色不异空，空不异色；色即是空，空即是色。受想行识，亦复如是。舍利子，是诸法空相，不生不灭，不垢不净，不增不减。,19世纪，法国的一位数学家douardLucas(18421891)对该课题进行过研究，他指示，要完成这个任务，僧侣们搬动金盘的总次数：18446744073709551615（20位）假设僧侣们个个身强力壮，每天24小时不知头疲倦地工作，而且一秒钟移动一个金盘，那么，完成这个任务也得花5800亿年。,17,已知3个柱子l、2、3和两个盘子A、B(A比B小)。初始状态下，A、B依次放在1柱上；目标状态是A、B依次放在柱子3上。条件是每次可移动一个盘子，盘子上方是空顶方可移动，而且任何时候都不允许大盘在小盘之上。,例2.2.3.1二阶Hanoi塔问题,2.2.3状态空间法,18,定义问题状态的描述形式设用Sk=(SkA，SkB)表示问题的状态，SkA表示盘子A所在的柱号，SkB表示盘子B所在的柱号。,第一步：用状态空间表示问题,用状态描述形式把问题的所有可能的状态都表示出来。本问题共有九种可能状态:S0=(1，1)，S1=(1，2)，S2=(1，3)S3=(2，1)，S4=(2，2)，S5=(2，3)S6=(3，1)，S7=(3，2)，S8=(3，3)问题的初始状态集合为S=S0，目标状态集合为G=S8。,2.2.3状态空间法,19,2.2.3状态空间法,算符A(i，j)表示把盘子A从第i号柱子移到第j号柱子上的操作；,算符B(i，j)表示把盘子B从第i号柱子移到第j号柱子上的操作。,算符组F中共有12个算符:A(1，2)，A(1，3)，A(2，1)，A(2，3)，A(3，1)，A(3，2)B(1，2)，B(1，3)，B(2，1)，B(2，3)，B(3，1)，B(3，2),问题的状态空间(S，F，G)构造完成。,定义一组算符F,2.2.3状态空间法,21,根据状态空间的9种可能状态和12种算符，构造它的状态空间图：,第二步：问题求解,2.2.3状态空间法,22,在状态空间图中，从初始节点(1，1)(状态S0)到目标节点(3，3)(状态S8)的任何一条通路都是问题的一个解。最短的路径长度是3，它由3个算符组成：A(1，2)、B(1，3)、A(2，3)。,2.2.3状态空间法,三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。,初始状态Qs,目标状态集合Q0,Q7,例1：翻转钱币问题,2.2.3状态空间法,引入一个三元组(q0,q1,q2)来描述总状态，钱币正面为0，反面为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)。,翻动钱币的操作抽象为改变上述状态的算子，即Fa,b,ca:把钱币q0翻转一次b:把钱币q1翻转一次c:把钱币q2翻转一次问题的状态空间为,例2.2.3.2：翻转钱币问题,2.2.3状态空间法,问题的状态空间为：,构造状态空间图：,aabababaabbbbcccbcccb,例2.2.3.2：翻转钱币问题,2.2.3状态空间法,图2-5翻动三次后三枚钱币问题的状态变化,翻转钱币问题状态空间图的另一种表示：,例2.2.3.2：翻转钱币问题,2.2.3状态空间法,例2.2.3.3：修道士和野人问题,在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：,1）修道士和野人都会划船，但船一次最多只能运两个人；,2）在任何岸边野人数目都不得超过修道士，否则修道士就会被野人吃掉。,2.2.3状态空间法,1、问题的状态可以用一个三元数组来描述：S(m,c,b)m：左岸的修道士数c：左岸的野人数b：左岸的船数右岸的状态不必标出，因为：右岸的修道士数m3m右岸的野人数c3c右岸的船数b1b,例2.2.3.3：修道士和野人问题,2.2.3状态空间法,2.2.3状态空间法,例2.2.3.3：修道士和野人问题,2.操作集Fp01,p10,p11,p02,p20,q01,q10,q11,q02,q20,2.2.3状态空间法,例2.2.3.3：修道士和野人问题,3.状态空间给出状态和操作的描述之后，该问题的状态空间是：S0，P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20，S31。,2.2.3状态空间法,例2.2.3.3：修道士和野人问题,4.状态空间图：,四条S0到S31长度相等的最短路径，对应的操作序列就是该问题的四个最优解,2.2.3状态空间法,例2.2.3.3：修道士和野人问题,思考题：(猴子摘香蕉),2.2.3状态空间法,2.2.3状态空间法,思考题：(猴子摘香蕉),隐式状态空间图：利用有关状态描述和状态转换（操作）的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识，包括该问题的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态，以及全部操作的条件和动作等。隐式状态空间图也称为是状态空间图的隐式表示或隐式图。,显式状态空间图vs隐式状态空间图,显式状态空间图：表示了问题所有可能的状态及状态之间的关系，这种表示方式称为显式状态空间图，或称为状态空间图的显示表示。,2.2.3状态空间法,重排九宫问题的状态表示,显式状态空间图vs隐式状态空间图,重排九宫问题的隐式图描述为：,2.2.3状态空间法,（1）有关状态的知识：,显式状态空间图vs隐式状态空间图,重排九宫问题的隐式图描述为：,初始状态：S0（0，1，2，3，5，6，4，7，8）目标状态：Sg（0，1，2，3，4，5，6，7，8）,状态S的定义：S(X0，X1，X2，X3，X4，X5，X6，X7，X8)其中，Xi0，1，2，3，4，5，6，7，8，,2.2.3状态空间法,0组规则R1(X0=0)(X2=n)X0=nX2=0；R2(X0=0)(X4=n)X0=nX4=0；R3(X0=0)(X6=n)X0=nX6=0；R4(X0=0)(X8=n)X0=nX8=0；1组规则R5(X1=0)(X2=n)X1=nX2=0；R6(X1=0)(X8=n)X1=nX8=0；,显式状态空间图vs隐式状态空间图,重排九宫问题的隐式图描述为：,（2）有关操作的知识（规则）：,2.2.3状态空间法,（S0,r1,r2,r24,Sg）,显式状态空间图vs隐式状态空间图,重排九宫问题的隐式图描述为：,这里仅给出了初始节点和目标节点，其余节点需用状态转换规则来产生。类似于这样表示的状态图称为隐式状态图，或者说状态图的隐式表示。,2.2.3状态空间法,40,2.2知识表示与问题求解,知识表示与问题求解,2.2.1一阶谓词知识表示法,2.2.2产生式知识表示法,2.2.3状态空间法,-2.2.3.2基于状态空间法的搜索策略,-2.2.3.1基于状态空间法的问题描述,状态空间图搜索中的通用数据结构,CLOSED表：用来记录考察过的节点以及节点之间的关系，如每个节点指向父节点的编号（返回指针）。CLOSED表中存放的就是一定搜索策略下的搜索树。,OPEN表,CLOSED表,OPEN表：专门登记已经生成但还没有考察的节点，即待考察节点。,2.2.3状态空间法,盲目搜索,盲目搜索:搜索时不参考与具体待求解问题相关的任何信息，只是按预先设定的顺序逐个考察节点。盲目搜索与问题无关，具有通用性。,状态空间图搜索,广度优先搜索,深度优先搜索,迭代加深搜索,2.2.3状态空间法,盲目搜索-广度优先搜索算法,广度优先搜索（Aed）基本思想,广度优先搜索是严格按节点在树中的出现位置一层一层向下的搜索过程。通过将OPEN表设计为一个队列来实现，将新生成的子节点放在OPEN表的后面，保证先生成的节点先考察。,2.2.3状态空间法,步1把初始结点S0放入OPEN表中；步2若OPEN表为空，则搜索失败，退出；步3否则，取OPEN表中第一个结点N放在CLOSED表中；并冠以顺序编号n；步4若结点N为目标结点，则搜索成功。利用CLOSED表中的返回指针找出S0到N的路径即为所求解，退出；步5若N不可扩展，转步2；步6否则，扩展N，将其所有子结点配上指向N的返回指针放入OPEN表的尾部，转步2。,广度优先搜索算法,盲目搜索-广度优先搜索算法,2.2.3状态空间法,2019/12/13,45,可编辑,广度优先搜索算法流程图,盲目搜索-广度优先搜索算法,2.2.3状态空间法,八数码广度优先搜索,使用广度优先搜索算法求解重排九宫问题,盲目搜索-广度优先搜索算法,2.2.3状态空间法,缺点搜索效率低。,广度优先搜索的特点：,广度优先中OPEN表是一个队列，CLOSED表是一个顺序表，表中各节点按顺序编号，正被考察的节点在表中编号最大。,广度优先搜索又称为宽度优先或横向搜索。,广度优先策略是完备的，即如果问题的解存在，则它一定可以找到解，并且找到的解还是最优解。,广度优先搜索策略与问题无关，具有通用性。,盲目搜索-广度优先搜索算法,2.2.3状态空间法,盲目搜索-深度优先搜索算法,深度优先搜索的基本思想,深度优先搜索是一种一直向下的搜索过程，它优先在自己的子结点集合中选择下一个被考察的结点，不断向纵深方向前进，直到到达叶子结点或受到深度限制时，才返回到上一级结点沿另一方向继续前进。,2.2.3状态空间法,与广度优先搜索策略的唯一不同点就是OPEN表被设计成后进先出的栈，新生成的子结点放在OPEN表的前面，后生成的结点优先被考察。深度优先搜索算法只需将宽度优先搜索算法步6修改为：步6否则，扩展N，将其所有子结点配上指向N的指针放入OPEN表的首部，转步2。,盲目搜索-深度优先搜索算法,深度优先搜索算法,2.2.3状态空间法,12384576,3,12384576,12384576,12843765,12385746,2,12384765,5,使用深度优先搜索算法求解重排九宫问题,盲目搜索-深度优先搜索算法,2.2.3状态空间法,深度优先搜索的特点：OPEN表为一个堆栈。深度优先又称纵向搜索。一般不能保证找到最优解。如下图所示：,图深度优先搜索不具有完备性示意图,深度优先搜索的特点：,盲目搜索-深度优先搜索算法,2.2.3状态空间法,为克服深度优先搜索的不足，可对其深度进行限制,盲目搜索-有界深度优先搜索算法,有界深度优先搜索的提出：,即使能求出解，它也不一定是最优解。,深度界限的选择很重要dm若太小，则达不到解的深度，得不到解；若太大，既浪费了计算机的存储空间与时间，又降低了搜索效率。由于解的路径长度事先难以预料，所以要恰当地给出dm的值是比较困难的。,2.2.3状态空间法,当在dm界限之内找不到解时，可以将深度界限dm不断扩大，每次增加一个深度增量d，直到找到解，或者搜索完整棵树。这样算法的完备性得到了保证，称为可变界深度优先搜索算法(或迭代加深搜索)。,盲目搜索-有界深度优先搜索算法,有界深度优先搜索的思路-迭代加深,当d=1时，算法开始蜕变为广度优先搜索算法。,2.2.3状态空间法,人工智能,盲目搜索-迭代加深优先搜索算法,2.2.3状态空间法,步1把初始结点S0放入OPEN表中，置d(S0)=0，dm=dm0，G=NULL。步2若OPEN表为空，则考察CLOSED表是否有待扩展结点：（1）若无待扩展结点，则判断G表是否为空：若为空，搜索失败，退出；否则，取出G表最后面的结点Sg，Sg即为所求最优解，搜索成功，退出；（2）若有待扩展结点，则取出CLOSED表中待扩展结点放入到OPEN表中，令dm=dm+d，转步2；,有界深度优先搜索的思路-迭代加深,盲目搜索-迭代加深优先搜索算法,2.2.3状态空间法,步3取OPEN表中首部的结点N放在CLOSED表中；并冠以顺序编号n；步4若d（N）dm，则标N为待扩展结点，转步2；步5若N是目标结点Sg，则令dmd（Sg）-1，把Sg放到G表的尾部，转步2。步6若N不可扩展，则转步2；步7否则，扩展N，将其所有子结点Ni配上指向N的返回指针放入OPEN表首部，置d（Ni）d（N）1，转步2。,有界深度优先搜索的思路-迭代加深,盲目搜索-迭代加深优先搜索算法,2.2.3状态空间法,八数码难题的深度优先搜索树(深度约束=4),对n应用一个算符以产生该节点的一个后继节点放入OPEN表的前端,59,Combinesdepth-andbreadthfirstOptimalandcomplete,memoryefficient,迭代加深(深度约束=1),迭代加深算法Demo,60,迭代加深(深度约束=2),61,迭代加深(深度约束=3),1,2,3,8,4,5,6,7,62,迭代加深(深度约束=4),问题：当d1时，是否能保证找到最优解？,有界深度优先搜索的思路-迭代加深,盲目搜索-迭代加深优先搜索算法,2.2.3状态空间法,盲目搜索&启发式搜索,状态空间图搜索,广度优先搜索,深度优先搜索,迭代加深搜索,A搜索,A*搜索,状态组合爆炸,2.2.3状态空间法,65,隐式部分(362866states),显式部分(14states),5,7,1,4,5,6,3,2,5,InitialState,Goal,8数码问题9!=362,880states15数码问题1.3x1012states24数码问题1025states,100millionsstates/sec,0.036sec,盲目搜索的困境-状态组合爆炸！,2.2.3状态空间法,启发性知识就是与被求解问题自身特性相关的知识，包括被求解问题的解的特性、解的分布规律和在实际当中求解此类问题的经验、技巧等，对应于问题求解框架中的控制性知识。,启发式搜索的基本思想,启发函数要实现启发式搜索，需要把启发性知识形式化，即用一定的函数表示出来，通过函数计算来评价每种选择的价值大小，用以指导搜索过程，这样的函数称为启发函数。,启发式搜索,2.2.3状态空间法,启发式搜索的基本思想,用启发函数来导航，其搜索算法就要在状态图一般搜索算法基础上再增加启发函数值的计算与传播过程，并且由启发函数值来确定节点的扩展顺序。,启发式搜索,2.2.3状态空间法,在很多实际问题中，已经付出的实际代价是必须考虑的，如TSP问题等。将两者同时考虑，用于指导搜索的算法称为A算法和A*算法。,启发函数是对当前结点到达目标结点未来可能要付出的代价的估计。,在全局择优和局部择优搜索算法中，都没有考虑从初始结点到当前结点已经付出的实际代价。,启发函数/代价函数/估价函数,启发式搜索,2.2.3状态空间法,为了防止在单独利用启发函数的时候误入歧途，将启发函数h（x）与代价函数g（x）相结合，即初始节点S0到达节点x处已付出的代价与节点x到达目标节点Sg的接近程度估计值总和。,估价函数,初始节点,节点n,目标节点,g(n),h(n),f（x）g（x）h（x）,启发式搜索,2.2.3状态空间法,AlgorithmA(A算法),Uniform-Costsearch（等代价搜索）分支界限/瞎子爬山,GreedySearch（贪婪搜索）,AlgorithmA*(A星算法),f(n)=g(n),f(n)=h(n),f(n)=g(n)+h(n),f(n)=g(n)+h(n),h(n)=h*(n),估价函数及其相应算法,启发式搜索,2.2.3状态空间法,开始,把S放入OPEN表,OPEN表为空表？,把第一个节点(n)从OPEN表移至CLOSED表,n为目标节点吗？,把n的后继节点放入OPEN表的末端，提供返回节点n的指针,修改指针方向,根据最佳优先重排OPEN表,失败,成功,是,是,否,否,(1),(3),(4),(5),(6),(7),(7),(8),(9),OPEN,CLOSED,(1),(2),启发式搜索,2.2.3状态空间法,1.全局择优搜索基本思想：在OPEN表中保留所有已生成而未考察的节点，并用启发函数h(x)对它们全部进行估价，从中选出最优节点进行扩展，而不管这个节点出现在搜索树的什么地方。,2.局部择优搜索基本思想：局部择优搜索是在启发性知识导航下的深度优先搜索，在OPEN表中保留所有已生成而未考察的结点，对其中新生成的每个子结点x计算启发函数，从全部子结点中选出最优结点进行扩展，其选择下一个要考察结点的范围是刚刚生成的全部子结点，,启发式搜索的两类基本策略,启发式搜索,2.2.3状态空间法,f（x）g（x）h（x）,g（x）：对某一确定的节点，是确定的值。,h（x）：不同的问题启发函数的定义不同，相同的问题也可以定义出不同的启发函数。,估价函数定义探讨,启发式搜索,如何设计合理的启发函数？,衡量启发式函数h（x）优劣的标准是看其是否能够准确反映出节点x到达目标的难易程度（距离）。,2.2.3状态空间法,（3）根据主观经验的主观打分等。,在实际设计过程中，启发函数是用来估计搜索树节点x与目标节点接近程度的一种函数，通常根据下列思路来选择启发函数：,（1）一个结点到目标结点的某种距离或差异的量度；,（2）一个结点处在最佳路径上的概率；,启发式搜索,如何设计合理的启发函数？,2.2.3状态空间法,启发式搜索,如何设计合理的启发函数？,带有比原问题在操作上更少约束条件的问题称问原问题的一个松弛问题,松弛问题,原问题的解,松弛问题的解,2.2.3状态空间法,启发式搜索,如何设计合理的启发函数？,带有比原问题在操作上更少约束条件的问题称问原问题的一个松弛问题,松弛问题,松弛问题中最优解的代价函数是一个admissible的启发函数！（代价函数的获取可通过移除原问题操作中的约束条件来得到）,2.2.3状态空间法,启发式搜索,如何设计合理的启发函数？,如果一个启发函数h(x)满足h(x)=h*(x),则该函数为一个admissible的启发函数，其中h*(x)为原问题的最优解代价函数,Admissibility,原问题的解,松弛问题的解,2.2.3状态空间法,估价函数f（x）g（x）h（x）,g(x)用节点深度d（x）来衡量,如何定义？,例重排九宫问题中的启发式函数的设计,启发式搜索,如何设计合理的启发函数？,2.2.3状态空间法,将某个数字从位置A移动到位置B的操作所需满足的条件为：,启发式搜索,例重排九宫问题中的启发式函数的设计,如何设计合理的启