第4章 图搜索技术*1推理与搜索n各种典型的逻辑推理过程都是一个状态空间图的搜索 过程n任一搜索过程也都是一个推理过程n隐式图的搜索过程是一种利用局部性知识构造全局性 答案的过程n在各种搜索过程中，人工智能最感兴趣的是那些具有 很强选择性的启发式方法，即那些利用很局部的状态空 间可以有效地找到问题的解的方法n机器学习等很多过程都是在假设空间中搜索目标的过 程Date2第4章 图搜索技术n4.1 状态图知识表示n4.2 状态图搜索n4.3 状态图问题求解n4.4 与或图知识表示n4.5 与或图搜索n4.6 与或图问题求解 n4.7 博弈树搜索Date34.1 状态图知识表示n4.1.1 状态、操作和状态空间n4.1.2 修道士和野人的状态空间n4.1.3 梵塔问题的状态空间n4.1.4 问题求解的基本框架n4.1.5 重排九宫问题和隐式图Date44.1.1 状态、操作和状态空间（1）n状态 （State）n为了描述某一类事物中各个不同事物之间的差异 而引入的最少的一组变量q的有序组合n表示成矢量形式：Date54.1.1 状态、操作和状态空间（2）n操作 （Operator）n引起状态中某些分量发生改变，从而使一个具 体状态变化到另一个具体状态的作用。
n它可以是一个机械性的步骤、过程、规则或算 子n操作描述了状态之间的关系Date64.1.1 状态、操作和状态空间（3）n状态空间（State Space）n问题的状态空间是一个表示该问题全部的可能 状态及相互关系的图n一般用赋值有向图，包含nS：问题的可能有的初始状态的集合；nF：操作的集合；nG：目标状态的集合n状态空间常记为三元序列Date74.1.1 状态、操作和状态空间（4）n状态空间中问题求解n在状态空间表示法中，问题求解过程转化为在 图中寻找从初始状态Qs出发到达目标状态Qg的路 径问题，也就是寻找操作序列的问题n状态空间的解为三元组nQs ：某个初始状态nQg ：某个目标状态na：把变换成的有限的操作序列Date84.1.1 状态、操作和状态空间（5 ）例2.1 三枚钱币，能否从下面状态翻动三 次后出现全正或全反状态反正反正正正初始状态θs目标状态集合{θ0, θ7}反反反Date94.1.1 状态、操作和状态空间（6 ）引入一个三元组(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翻转一次问题的状态空间为Date104.1.1 状态、操作和状态空间（7 ）状态空间图（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，0）（1，1，1）acabacabcbbcDate114.1.2 修道士和野人问题的状态空间（1）例2.2修道士和野人问题在河的左岸有三个修道士 、三个野人河一条船，修道士们想用这条船将所有的 人都运过河去，但受到以下条件的限制：（1）修道士和野人都会划船，但船一次最多只 能运两个人；（2）在任何岸边野人数目都不得超过修道士， 否则修道士就会被野人吃掉假定野人会服从任何一种过河安排，试规划出一 种确保修道士安全过河方案Date124.1.2 修道士和野人问题的状态空间（2）解：先建立问题的状态空间问题的状态可以用一 个三元数组来描述：S＝(m, c, b)m：左岸的修道士数c：左岸的野人数b：左岸的船数右岸的状态不必标出，因为：右岸的修道士数m’＝3－m右岸的野人数c’＝3－c右岸的船数b’=1-bDate134.1.2 修道士和野人问题的状态空间（3）状态m, c, b状态m, c, b状态m, c, b状态m, c, b S03 3 1S81 3 1S163 3 0S241 3 0 S13 2 1S91 2 1S173 2 0S251 2 0 S23 1 1S101 1 1S183 1 0S261 1 0 S33 0 1S111 0 1S193 0 0S271 0 0 S42 3 1S120 3 1S202 3 0S28 0 3 0S52 2 1S130 2 1S212 2 0S290 2 0 S62 1 1S140 1 1S222 1 0S300 1 0 S72 0 1S150 0 1S232 0 0S310 0 0Date144.1.2 修道士和野人问题的状态空间（4）操作集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操作符条 件动 作Date154.1.2 修道士和野人问题的状态空间（5）S0 (3,3,1)S18 (3,1,0)p02 q02S17 (3,2,0)p01q01S21 (2,2,0)p11q11S1 (3,2,1)q01p01p10 q10S19 (3,0,0)q02p02S2 (3,1,1)p01q01S26 (1,1,0)q20p20S0 (0,0,0)q11 p11S14 (0,1,1)p01q01 p02q02S10 (1,1,1)p10q10S13 (0,2,1)q01 p01S30 (0,1,0) q02p02S12 (0,3,1)p01q01S29 (0,2,0)q20p20S5 (2,2,1)p11q11Date164.1.3 梵塔问题的状态空间（1）例2.3 一号杆有A、B两个金盘，A小于B。
要求将 AB移至三号杆，每次只可移动一个盘子，任何时 刻B不能在A上用二元组（SA，SB）表示状态，SA表示A所在 杆号，SB表示B所在杆号，全部状态如下：（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）Date174.1.3 梵塔问题的状态空间（2）AB123 S0：（1，1）123 S1：（1，2）123 S2：（1，3）AA123 S5：（2，3）123 S4：（2，2）123 S3：（2，1）123 S8：（3，3）123 S7：（3，2）123 S6：（3，1）AAAAABA BBBBBDate184.1.3 梵塔问题的状态空间（3）转换规则：A（I，j）表示金盘A从第I号杆移到j号杆B（I，j）表示金盘B从第I号杆移到j号杆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） 初始状态（1，1），目标状态（3，3） 梵塔问题用状态图表示为：Date194.1.3 梵塔问题的状态空间（4）1,12,13,12,33,31,33,21,22,2A(1,3)A(2,1)B(3,1)A(3,2)A(1,3)B(1,3)A(2,1)B(1,2)A(3,2)Date204.1.4 问题求解的基本框架（1）n问题求解所需要的知识n与描述问题的状态有关的各种叙述性知识。
n描述状态之间的变换关系的各种过程性知识n描述如何根据当前状态和目标状态选择合适的操作的控制 性知识n一般以一组操作的形式出现的任何一个操作都含有条件 和动作两部分，条件给定了操作的适用范围，动作描述了由 于操作而引起的状态中某些分量的变化情形n根据叙述性和过程性知识可以构造问题的状态空间一般 讲状态空间是一个赋值有向图，节点对应着问题的状态，边 对应操作Date214.1.4 问题求解的基本框架（2）n问题求解就是再图中寻找一条从初始节点到 达目标节点的通路或操作序列n首先从操作集中选择可作用在当 前状态上的操作；n如果符合条件的操作有许多个， 则要从挑选出最有希望导致目标状态的 操作施加到当前状态上，以便克服组合 爆炸；n如果解的长度很大，还需要更为 复杂的克服组合爆炸的技术Date224.1.5 重排九宫问题和隐式图（1）n显式图 全部结构都可以在一张纸上或贮存在 一台计算机上n隐式图 利用有关状态描述和状态转换的知识 定义的状态空间图n如何隐式的描述一个状态空间n有描述问题状态的有关知识，包括该问题的各 状态分量的取值情况，开始条件、结束条件、 各种约束条件等等n需要由任何一个状态生成其所有直接后继节点 的的有关知识。
Date23283 1476581324765例2.4重排九宫问题4.1.5 重排九宫问题和隐式图（1）初始棋局目标棋局分析：状态数：9！X1X2X3X8X0X4X7X6X5Date244.1.5 重排九宫问题和隐式图（2）重排九宫问题的隐式表示 ：将棋局用如下向量表示：A＝(X0，X1 ，X2 ，X3 ，X4 ，X5 ， X6 ， X7 ，X8)状态：约束条件： Xi{0，1 ，2，3，4，5，6，7,8}XiXj，当ij时初始状态： S0 ＝（0，2，8，3，4，5，6，7，1）目标状态： Sg ＝（0，1，2，3，4，5，6，7，8）Date254.1.5 重排九宫问题和隐式图（3）操作：数码的移动规则就是该问题的状态操作经分析，该问题共有24 条规则，分为9组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 X1 =0；r23(X8=0 ) (X0=n ) X8 = n X0=0；r24(X8=0 ) (X7=n ) X8 = n X7 =0；Date264.1.5 重排九宫问题和隐式图（3）八数码的状态图可表示为（{S0}, {r1 , r2 ,… , r24 }, {Sg}）八数码问题状态图仅给出了初始节点和 目标节点，其余节点需用状态转换规则来产生 。
这样表示的状态图称为隐式状态图，或者说 状态图的隐式表示Date274.2 状态图搜索n4.2.1 状态图搜索n4.2.2穷举式搜索n4.2.3启发式搜索n4.2.4加权状态图搜索n4.2.5启发式图搜索的A算法和A*算法n4.2.6状态图搜索策略小结Date284.2.1 状态图搜索（1）n搜索方式n树式搜索在搜索过程中记录所经过的所有节点和边树 式搜索所记录的轨迹始终是一棵树，这棵树也就是搜索 过程中所产生得搜索树n线式搜索在搜索过程中只记录那些当前认为在所找路径 上的。