第2章基于状态空间图表示的搜索技术

第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.问题求解框架问题：是指事件或事物的已知或当前状态与目标状态之间有差异。问题求解：是指在一定的控制策略下，通过一系列的操作或运算来改变问题的状态，使之与目标状态接近或一致。例如，李明在北京，他要去西安（办事）。又如，博弈问题。2019/9/20人工智能6问题的求解框架（1）叙述性知识：描述问题的状态有关的各种知识。（2）过程性知识：描述状态之间的变换关系的各种知识。（3）控制性知识：描述如何在当前状态下选择合适操作的知识。2019/9/20人工智能82.1.2知识表示(1)知识表示：就是研究在计算机中如何用最合适的形式表示问题求解过程中所需要的各种知识，包括构成问题求解框架的全部知识。常用的知识表示形式状态空间图与或图谓词逻辑产生式框架语义网络……2.1.2知识表示(2)2019/9/20人工智能9例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人工智能102.1.3图搜索技术(1)1.搜索搜索，简单地说就是“寻找”，目的是找到问题的解。在问题求解过程中，待求解的问题被抽象成一定空间上的图，搜索过程就是从图中初始节点出发，沿着与之相连的边试探着前进，寻找目标节点或可解节点的过程。2.搜索树搜索过程中经过（考察过）的节点和边，按原图的连接关系，便会构成一个树型的有向图，称为搜索树。搜索树是一个搜索过程的搜索轨迹，或称之为搜索空间。2.1.3图搜索技术(2)2019/9/20人工智能11SgSo问题全状态空间搜索空间解路径图2-2搜索空间示意图问题的状态空间、搜索空间及解的示意图：2.1.3图搜索技术(3)3.搜索策略搜索策略将决定搜索过程按照什么样的顺序考察节点和经过状态空间图的哪些节点。盲目搜索：无向导的搜索，也称穷举搜索。启发式搜索：利用“启发性信息”作为导航的搜索过程。对于较大或无限状态空间问题，盲目搜索效率太低，所以在实际当中往往是不可行的。启发式搜索广泛地应用于实际问题求解中，如博弈、机器学习、数据挖掘、智能检索等。2019/9/20人工智能122019/9/20人工智能132.2状态空间图表示2.2.1状态空间图2.2.2隐式状态空间图2019/9/20人工智能142.2.1状态空间图（1）1.状态状态对应叙述性知识，描述一个问题在开始、结束或中间的某一时刻所处的状况或状态。通常引进一组变量，表示与问题状态相关的各种要素，并用这组变量所构成的多元组来表示状态。状态在状态图中表示为节点。12nqqq，，，12()nqqq，，，2019/9/20人工智能152.2.1状态空间图（2）2.操作操作对应过程性知识，即状态转换规则，描述状态之间的关系。描述一个操作要包含两个部分条件:指明被作用的状态要满足的约束条件动作:指明一个操作对状态的分量所做的改变。操作的表示形式可以是一个机械性的步骤、过程、规则或算子。操作在状态图中表示为边。在程序中，状态转换规则可用数据对、条件语句、规则、函数、过程等表示。如：如果室内温度低于26度，则关闭空调。2019/9/20人工智能162.2.1状态空间图（3）3.状态空间图问题的状态空间图是一个描述该问题全部可能的状态及相互关系的图，如考虑操作的代价，状态空间图就是一个赋值有向图。状态空间常记为三元组：S：初始状态的集合F：操作的集合G：目标状态的集合。由问题的状态空间表示就可以构造出状态空间图。SFG，，2.2.1状态空间图（4）4.求解在状态空间表示法中，问题求解过程转化为在图中寻找从初始状态Qs出发到达目标状态Qg的路径问题，也就是寻找操作序列的问题。状态空间的解为三元组Qs,a,QgQs：某个初始状态Qg：某个目标状态a：把Qs变换成Qg的有限的操作序列状态转换图Q1Q3Q2…f1f2f3f4QsQgfn2019/9/20人工智能172019/9/20人工智能18例2.2翻转钱币问题（1）三枚钱币处于反、正、反状态，每次只许翻动一枚钱币，问连续翻动三次后，能否出现全正或全反状态。初始状态目标状态集合例2.2翻转钱币问题（2）1.状态引入一个三元组(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)。2019/9/20人工智能192.操作翻动钱币的操作抽象为改变上述状态的算子，即F＝{a,b,c}a:把钱币q0翻转一次b:把钱币q1翻转一次c:把钱币q2翻转一次问题的状态空间为{Q5},{a,b,c}，{Q0,Q7}例2.2翻转钱币问题（3）例2.2翻转钱币问题（4）3.状态空间图问题的状态空间为：2019/9/20人工智能21构造状态空间图：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翻转钱币问题（5）2019/9/20人工智能22翻转钱币问题状态空间图的另一种表示：引入分量n表示已经翻过的次数即Q50表示经过0次翻转到达Q5；Q41表示经过1次翻转到达Q4；。。。。。。例2.2翻转钱币问题（6）2019/9/20人工智能23ccccbbbbaaaacccaaabbbabcQ50Q41Q11Q71Q02Q32Q52Q62Q03Q13Q23Q43Q73图2-5翻动三次后三枚钱币问题的状态变化aabababaabbbbcccbcccb2019/9/20人工智能24例2.3修道士和野人问题（1）在河的左岸有三个修道士、三个野人和一条船，修道士们想用这条船将所有的人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只能运两个人；（2）在任何岸边野人数目都不得超过修道士，否则修道士就会被野人吃掉。假定野人会服从任何一种过河安排，试规划出一种确保修道士安全过河方案。2019/9/20人工智能25例2.3修道士和野人问题（2）1、问题的状态可以用一个三元数组来描述：S＝(m,c,b)m：左岸的修道士人数m∈{0,1,2,3}c：左岸的野人数c∈{0,1,2,3}b：左岸的船数b∈{0,1}右岸的状态不必标出，因为：右岸的修道士人数m’＝3－m右岸的野人数c’＝3－c右岸的船数b’＝1－b2019/9/20人工智能26例2.3修道士和野人问题（3）状态m,c,b状态m,c,b状态m,c,b状态m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S31000不可能状态不合法状态合法状态16例2.3修道士和野人问题（4）2、操作pij操作：左岸到右岸qij操作：右岸到左岸船上修道士人数i，野人人数j满足：1≤i+j≤2可实施的操作集为：F＝{p01,p10,p11,p02,p20,q01,q10,q11,q02,q20}2019/9/20人工智能28例2.3修道士和野人问题（5）操作集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修道士和野人问题（6）3.状态空间给出状态和操作的描述之后，该问题的状态空间是：{{S0}，{P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}，{S31}}。以全部合法状态为节点，按照操作要求的条件，在节点之间构造有向边。2019/9/20人工智能30例2.3修道士和野人问题（7）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长度相等的最短路径，对应的操作序列就是该问题的四个最优解{P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}2019/9/20人工智能312.2.2隐式状态空间图显式状态空间图：表示了问题所有可能的状态及状态之间的关系，这种表示方式称为显式状态空间图，或称为状态空间图的显式表示。隐式状态空间图：利用有关状态描述和状态转换（操作）的知识定义的状态空间图。在计算机中仅存储描述问题状态及操作的有关知识，包括该问题的各状态分量的取值情况、分量之间的约束条件、开始状态、终止状态，以及全部操作的条件和动作等。