第2章_基于状态空间图表示的搜索搜索技术(新)XXXX1013

第2章基于图的知识表示与图搜索技术2019/9/20人工智能2第2章基于图的知识表示与图搜索技术2.1概述2.2状态空间图表示2.3状态空间图的盲目搜索2.4状态空间图的启发式搜索2.5与或图表示及搜索技术2.6博弈树及搜索技术2019/9/20人工智能32.1概述2.1.1知识与问题求解框架2.1.2知识表示2.1.3图搜索技术2019/9/20人工智能42.1.1知识与问题求解框架(1)1.知识的定义心理学：个体通过与环境相互作用后获得的信息及其组织。费根鲍姆：知识是经过消减、塑造、解释和转换的信息。博恩斯坦（Bernstein）：知识是由特定领域的描述、关系和过程组成的。概括地说，知识是高度组织起来的信息集团，是人们在长期的生活和社会实践中、科学研究和科学实验中积累起来的经验或对客观世界规律的认识等。2.1.1知识与问题求解框架(2)2.知识的分类（1）从应用领域来划分常识性知识领域（专业）性知识（2）从在问题求解中的作用来划分叙述性知识过程性知识控制性知识（3）从确定性来划分确定性知识非确定性知识（4）从知识的表现形式来划分，可分为文字、符号、声音、图形、图像等。2019/9/20人工智能52.1.1知识与问题求解框架(3)3.问题求解框架问题：是指事件或事物的已知或当前状态与目标状态之间有差异。问题求解：是指在一定的控制策略下，通过一系列的操作或运算来改变问题的状态，使之与目标状态接近或一致。例如，李明在北京，他要去西安（办事）。又如，博弈问题。问题的求解框架（1）叙述性知识：描述问题的状态有关的各种知识。（2）过程性知识：描述状态之间的变换关系的各种知识。（3）控制性知识：描述如何在当前状态下选择合适操作的知识。2019/9/20人工智能62019/9/20人工智能72.1.2知识表示(1)知识表示：就是研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。常用的知识表示形式状态空间图与或图谓词逻辑产生式框架语义网络……2.1.2知识表示(2)2019/9/20人工智能8例2.1麦卡赛问题。在一个2n2n的方格棋盘中，去掉对角的两个方格，如图（a），问能否将它全部划成若干12的小长方块？2n2n(b)同构问题2n2n(a)原始问题QSQ1Qg(c)同态问题(2n2,2n2–2)(2n2–1,2n2–3)(2,0)(0,0)Q2n2-22n2n(b)同构问题2n2n(a)原始问题QSQ1Qg(c)同态问题(2n2,2n2–2)(2n2–1,2n2–3)(2,0)(0,0)Q2n2-22n2n(b)同构问题2n2n(a)原始问题QSQ1Qg(c)同态问题(2n2,2n2–2)(2n2–1,2n2–3)(2,0)(0,0)Q2n2-2目标状态初始状态可达状态同构问题同态问题2019/9/20人工智能92.1.3图搜索技术(1)1.搜索搜索，简单地说就是“寻找”，目的是找到问题的解。在问题求解过程中，待求解的问题被抽象成一定空间上的图，搜索过程就是从图中初始节点出发，沿着与之相连的边试探着前进，寻找目标节点或可解节点的过程。2.搜索树搜索过程中经过（考察过）的节点和边，按原图的连接关系，便会构成一个树型的有向图，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。2.1.3图搜索技术(2)2019/9/20人工智能10SgSo问题全状态空间搜索空间解路径图2-2搜索空间示意图问题的状态空间、搜索空间及解的示意图：2.1.3图搜索技术(3)3.搜索策略搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点。盲目搜索：无向导的搜索，也称穷举搜索。启发式搜索：利用“启发性信息”作为导航的搜索过程。对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。2019/9/20人工智能112019/9/20人工智能122.2状态空间图表示2.2.1状态空间图2.2.2隐式状态空间图2019/9/20人工智能132.2.1状态空间图（1）1.状态状态对应叙述性知识，描述一个问题在开始、结束或中间的某一时刻所处的状况或状态。通常引进一组变量，表示与问题状态相关的各种要素，并用这组变量所构成的多元组来表示状态。状态在状态图中表示为节点。12nqqq，，，12()nqqq，，，2019/9/20人工智能142.2.1状态空间图（2）2.操作操作对应过程性知识，即状态转换规则，描述状态之间的关系。描述一个操作要包含两个部分条件:指明被作用的状态要满足的约束条件动作:指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤、过程、规则或算子。操作在状态图中表示为边。在程序中，状态转换规则可用数据对、条件语句、规则、函数、过程等表示。如：如果室内温度低于26度，则关闭空调。2019/9/20人工智能152.2.1状态空间图（3）3.状态空间图问题的状态空间图是一个描述该问题全部可能的状态及相互关系的图，如考虑操作的代价，状态空间图就是一个赋值有向图。状态空间常记为三元组：S：初始状态的集合F：操作的集合G：目标状态的集合。由问题的状态空间表示就可以构造出状态空间图。SFG，，2.2.1状态空间图（4）4.求解在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题，也就是寻找操作序列的问题。状态空间的解为三元组Qs,a,QgQs：某个初始状态Qg：某个目标状态a：把Qs变换成Qg的有限的操作序列状态转换图S1S3S2…f1f2f3f4QsQgfn2019/9/20人工智能162019/9/20人工智能17例2.2翻转钱币问题（1）三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。初始状态Qs目标状态集合{Q0,Q7}例2.2翻转钱币问题（2）引入一个三元组(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}2019/9/20人工智能18例2.2翻转钱币问题（4）3.状态空间图问题的状态空间为：2019/9/20人工智能19构造状态空间图：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)aabababaabbbbcccbcccb2019/9/20人工智能20例2.3修道士和野人问题（1）在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运两个人；（2）在任何岸边野人数目都不得超过修道士，否则修道士就会被野人吃掉。假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。2019/9/20人工智能21例2.3修道士和野人问题（2）1、问题的状态可以用一个三元数组来描述：S＝(m,c,b)m：左岸的修道士数c：左岸的野人数b：左岸的船数右岸的状态不必标出，因为：右岸的修道士数m’＝3－m右岸的野人数c’＝3－c右岸的船数b’＝1－b2019/9/20人工智能22例2.3修道士和野人问题（3）状态m,c,b状态m,c,b状态m,c,b状态m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S310002019/9/20人工智能23例2.3修道士和野人问题（4）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.3修道士和野人问题（5）3.状态空间给出状态和操作的描述之后，该问题的状态空间是：{{S0}，{P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}，{S31}}。2019/9/20人工智能25例2.3修道士和野人问题（6）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)q20p20S31(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长度相等的最短路径，对应的操作序列就是该问题的四个最优解2019/9/20人工智能262.2.2隐式状态空间图显式状态空间图：表示了问题所有可能的状态及状态之间的关系，这种表示方式称为显式状态空间图，或称为状态空间图的显示表示。隐式状态空间图：利用有关状态描述和状态转换（操作）的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识，包括该问题的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态，以及全部操作的条件和动作等。隐式状态空间图也称为是状态空间图的隐式表示或隐式图。重排九宫问题的隐式图描述为：（1）有关状态的知识：状态S的定义：S＝(X0，X1，X2，X3，X4，X5，X6，X7，X8)其中，Xi｛0，1，2，3，4，5，6，7，8｝，，且。初始状态：S0＝（0，1，2，3，5，6，4，7，8）目标状态：Sg＝（0，1，2，3，4，5，6，7，8）(a)初始状态(b)终止状态1238574612384765X1X2X3X8X0X4X7X6X5重排九宫问题的状态表示80iijijXX时，例2.4重排九宫问题（八数码问题）例2.4重排九宫问题（2）（2）有关操作的知识（规则）：0组规则R1(X0=0)(X2=n)X0=nX2=0；R2(X0=0)(X4=n)X0=nX4=0；R3(X0=0)(X6=n)X0=nX6=0；R4(X0=0)(X8=n)X0=nX8=0；1组规则R5(X1=0)(X2=n)X1=nX2=0；R6(X1=0)(X8=n)X1=nX8=0；8组规则:R22(X8=0)(X1=n)X8=n