人工智能chapter4search

DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring第四章状态空间搜索用搜索法对问题求解问题实例状态空间搜索的结构问题的状态空间表示法状态空间搜索策略与/或树的盲目搜索基于递归的搜索2DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring4.1用搜索法对问题求解一个问题可以形式化地定义为四个组成部分：初始状态可能行动的描述目标测试路径耗散问题的解就是从初始状态到目标状态的路径寻找解的过程就是搜索3DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring要成功地设计和实现搜索算法:问题求解器是否一定能找到一个解?问题求解器是否能终止运行,或是否会陷入一个死循环?当问题求解器找到解时,找到的是否是最好的解?搜索过程的时间与空间复杂性如何?怎样才能最有效地降低搜索的复杂性?怎样设计才能最有效地利用描述语言?4.1用搜索法对问题求解4DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring状态空间的理论是我们用来回答这些疑问最主要的工具。4.1用搜索法对问题求解图由结点集和连接结点对的弧或边的集合组成。结点：问题求解中的不同状态（棋局/推理结果）弧：状态之间的转换（一步走棋/一条规则运用）5DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring1.二阶梵塔问题设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。解：全部可能的问题状态共有以下9种：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)4.2问题实例6DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring问题的初始状态集合:目标状态集合:ABABAB123123123二阶梵塔问题的初始状态和目标状态初始状态S0和目标状态S4、S8如图所示S0=(1,1)S4=(2,2)S8=(3,3)S={S0}=(1,1)G={S4,S5}={(2,2),(3,3)}7DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring操作分别用A(i,j)和B(i,j)表示:A(i,j):把金片A从第i号钢针移到j号钢针上；B(i,j):把金片B从第i号钢针移到第j号钢针上。共有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)一个问题可以形式化地定义为四个组成部分：初始状态可能行动的描述目标测试路径耗散ABABAB123123123二阶梵塔问题的初始状态和目标状态S0=(1,1)S4=(2,2)S8=(3,3)8DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring(3,3)(1,3)(1,2)(2,2)从初始节点(1,1)到目标节点(2,2)及(3,3)的任何一条路径都是问题的一个解。最短的路径长度是?A(1,2)B(1,3)A(2,3)(1,1)(3,1)(3,2)(2,1)(2,3)A(1,3)B(1,2)A(3,2)ABABAB123123123S0=(1,1)S4=(2,2)S8=(3,3)9DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpringabc2猴子摘香蕉问题解：4元组（w,x,y,z）其中：w表示猴子的水平位置；x表示箱子的水平位置；y表示猴子是否在箱子上，当猴子在箱子上时，y取1，否则y取0；z表示猴子是否拿到香蕉，当拿到香蕉时z取1，否则z取0。10DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring初始状态:abcS0:(a,b,0,0)S1:(b,b,0,0)S2:(c,c,0,0)S3:(c,c,1,0)S4:(c,c,1,1)目标状态允许的操作为:Goto(u)：猴子走到位置u，即(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推着箱子到水平位置v，即(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即(x,x,0,0)→(x,x,1,0)Grasp；猴子拿到香蕉，即(c,c,1,0)→(c,c,1,1)11DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring猴子摘香蕉问题的解(a,b,0,0)(b,b,0,0)(c,c,0,0)(b,b,1,0)(c,c,1,0)(a,a,0,0)(c,c,1,1)初始状态Goto(b)Goto(b)Pushbox(c)Grasp目标状态猴子摘香蕉问题的状态空间图解序列为：{Goto(b),Pushbox(c),Climbbox,Grasp}Pushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)abc12DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring3.八数码问题724568318765432113DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring状态：状态描述了8个棋子中的每一个以及空位在棋盘的9个方格上的分布。初始状态：任何状态都可以被指定为初始状态。注意要到达任何一个给定的目标，可能的初始状态中恰好只有一半可以作为开始。后继函数：用来产生通过四个行动（把空位向Left，Right，Up或Down移动）能够达到的合法状态。目标测试：用来检测状态是否能匹配所要求的目标格局。路径耗散：每一步的耗散值为1，因此整个路径的耗散值为路径中的步数。八数码问题14DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring283147652831476523184765283147652831647583214765283714652318476523184765281437652831457628316475283164758321476528371465832147658132476528374615283714651238476512378465123847652341876528143765283145762836417528316754S0123456789101112131415161718192021222324252627Sg15DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring4.八皇后问题********16DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring4.八皇后问题状态：把8个皇后摆放在棋盘上的任何安排都是一个状态。初始状态：棋盘上没有皇后。后继状态：把一个皇后添加到棋盘上的任何空格。目标测试：8个皇后都在棋盘上，并且互相攻击不到。17DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring图是结点及连接它们的边的集合。如果图中每个结点都有一个或多个描述符(标记)使之与其他结点区别开来,这样的图称为标记图。有方向性的弧连接的图是有向图。图中的弧也可以做上标记，用来给关系取名或表示权值。当一对结点间有多条弧相连时，这种方法可以使之区别。4.3状态空间搜索的结构18DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring结点集={A,B,C,D,E}弧集={(A,B),(A,D),(B,C),(C,B),(C,D),(D,A),(D,E),(E,C),(E,D)}有向图EABDC19DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring有根树,一个家庭关系的例子ACFEGHIJDB4.3状态空间搜索的结构有根图具有唯一一个称为根的结点,从根结点出发到图中任何结点都存在相应路径。20DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring用来描述结点之间关系：祖先、后裔、父母、子女、兄弟4.3状态空间搜索的结构EABDC21DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring4.4问题的状态空间表示法图的结点和弧分别表示问题求解过程中解题状态和解题步骤。初始状态对应于实际问题的已知信息,是图中的根结点。目标就是实际问题的解。状态空间搜索将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。22DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSpring[定义]状态空间搜索状态空间是一个四元组[N,A,S,GD]:N是图中状态结点集,代表问题求解过程中的各种状态。A是结点间弧(或链)的集合,代表问题求解过程的各个步骤。S是N的非空子集,包含问题的初始状态。GD是N的非空子集,包含问题的目标状态。GD中的状态可用两种方式中的任一种来描述：搜索中遇到了目标状态的可检测的性质；欲搜索的路径的性质。图中从S中结点到GD中结点的路径称为求解路径。搜索算法的任务是在问题空间里找到一条求解路径。它包含了一系列使问题得到解决的操作(算子)。4.4问题的状态空间表示法23DepartmentofComputerScience&Technology,NanjingUniversityArtificialIntelligenceSprin