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

1智能控制技术上海大学机电工程与自动化学院杜鑫自动化系仪自教研室22.2知识表示与问题求解知识表示与问题求解2.2.1一阶谓词知识表示法2.2.2产生式知识表示法2.2.3状态空间法自动化系仪自教研室32.2知识表示与问题求解知识表示与问题求解2.2.1一阶谓词知识表示法2.2.2产生式知识表示法2.2.3状态空间法-2.2.3.1基于状态空间法的问题描述自动化系仪自教研室例:三数码难题（3puzzleproblem）123123123312312312初始棋局目标棋局2.2.3状态空间法自动化系仪自教研室5状态空间表示法就是以“状态空间”的形式来表示问题及其搜索过程的一种方法。状态空间表示法是人工智能中最基本的形式化方法，是讨论问题求解技术的基础。2.2.3状态空间法自动化系仪自教研室61.状态是描述问题求解过程中不同时刻状况的数据结构。一般用一组变量的有序集合表示：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例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState2.2.3.2用状态空间表示问题的步骤2.2.3状态空间法自动化系仪自教研室14Hanoi塔2.2.3状态空间法在梵城（Hana）地下有一个僧侣的秘密组织，他们有3个大型的塔柱，左边的塔柱上由方到小套着64个金盘。僧侣们的工作是要把这64个金盘从左边塔柱转移到右边塔柱上去。但转移过程有规定的：1、每次只能搬动一只盘子，盘十只能在3个塔柱上安放，不允许放在地上；2、在每个塔柱上，只允许把小盘十叠在大盘上，反之不允许。据传说，僧侣们完成这个任务时，世界的末日就来临了。自动化系仪自教研室15Hanoi塔2.2.3状态空间法19世纪，法国的一位数学家ÉdouardLucas(1842−1891)对该课题进行过研究，他指示，要完成这个任务，僧侣们搬动金盘的总次数：18446744073709551615（20位）假设僧侣们个个身强力壮，每天24小时不知头疲倦地工作，而且一秒钟移动一个金盘，那么，完成这个任务也得花5800亿年。自动化系仪自教研室16Hanoi塔2.2.3状态空间法观自在菩萨，行深般若波罗蜜多时，照见五蕴皆空，度一切苦厄。舍利子，色不异空，空不异色；色即是空，空即是色。受想行识，亦复如是。舍利子，是诸法空相，不生不灭，不垢不净，不增不减。19世纪，法国的一位数学家ÉdouardLucas(1842−1891)对该课题进行过研究，他指示，要完成这个任务，僧侣们搬动金盘的总次数：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状态空间法自动化系仪自教研室192.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)构造完成。③定义一组算符F2.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)。翻动钱币的操作抽象为改变上述状态的算子，即F＝{a,b,c}a:把钱币q0翻转一次b:把钱币q1翻转一次c:把钱币q2翻转一次问题的状态空间为{Q5},{a,b,c}，{Q0Q7}例2.2.3.2：翻转钱币问题2.2.3状态空间法自动化系仪自教研室问题的状态空间为：构造状态空间图：507{}{}{}QabcQQ，，，，，cbbcQ1aQs=Q5bQ7=Qg2aQ3cQ2aQ6baQ4Q0=Qg1c(0,0,0)(1,0,0)(0,0,1)(1,0,1)(1,1,1)(0,1,1)(1,1,0)(0,1,0)aabababaabbbbcccbcccb例2.2.3.2：翻转钱币问题2.2.3状态空间法自动化系仪自教研室ccccbbbbaaaacccaaabbbabcQ50Q41Q11Q71Q02Q32Q52Q62Q03Q13Q23Q43Q73图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：左岸的船数右岸的状态不必标出，因为：右岸的修道士数m’＝3－m右岸的野人数c’＝3－c右岸的船数b’＝1－b例2.2.3.3：修道士和野人问题2.2.3状态空间法自动化系仪自教研室状态m,c,b状态m,c,b状态m,c,b状态m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S31000状态不合法由合理的状态转换规则无法退出2.2.3状态空间法例2.2.3.3：修道士和野人问题自动化系仪自教研室2.操作集F＝{p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}q20b=0,(m=0,c=2)或(m=1,c=1)b=1,m=m+2q02b=0,m=0或3,c≤2b=1,c=c+2q11b=0,m=c,c≤2b=1,m=m+1,c=c+1q10b=0,(m=0,c=1)或(m=2,c=2)b=1,m=m+1q01b=0,m=0或3,c≤2b=1,c=c+1p20b=1,(m=3,c=1)或(m=2,c=2)b=0,m=m-2p02b=1,m=0或3,c≥2b=0,c=c-2p11b=1,m=c,c≥1b=0,m=m-1,c=c-1p10b=1,(m=3,c=2)或(m=1,c=1)b=0,m=m-1p01b=1,m=0或3,c≥1b=0,c=c-1操作符条件动作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：修道士和野人问题自动化系仪自教研室S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S0(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S30(0,1,0)p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.状态空间图：四条S0到S31长度相等的最短路径，对应的操作序列就是该问题的四个最优解2.2.3状态空间法例2.2.3.3：修道士和野人问题自动化系仪自教研室思考题：(猴子摘香蕉)2.2.3状态空间法自动化系仪自教研室•猴子香蕉箱子•猴子香蕉箱子••••••••••Ha!Ha!2.2.3状态空间法