搜索策略课件dtfo.pptx
2023/3/251第第3 3章章 搜索策略搜索策略o问题求解系统划分为两大类问题求解系统划分为两大类n知识贫乏系统知识贫乏系统 o依靠依靠搜索技术搜索技术解决问题解决问题 o知识贫乏、缺乏针对性知识贫乏、缺乏针对性o效率低效率低 n知识丰富系统知识丰富系统 o依靠依靠推理技术推理技术解决问题解决问题o基于丰富知识的推理技术，直截了当基于丰富知识的推理技术，直截了当 o效率高效率高 2023/3/252第第3 3章章 搜索策略搜索策略o两大类两大类搜索技术搜索技术:n1、一般图搜索、启发式搜索、一般图搜索、启发式搜索n2、基于问题归约的与或图搜索、基于问题归约的与或图搜索 o两种典型的两种典型的推理技术推理技术:n1、基于归结的演绎推理、基于归结的演绎推理o归结反演归结反演n2、基于规则的演绎推理、基于规则的演绎推理o正向演绎推理正向演绎推理o逆向演绎推理逆向演绎推理 2023/3/2533.1 引言引言 o对于给定的问题，智能系统的行为一般是找到能够达到所希望目标的动作序列，并使其所付出的代价最小、性能最好。o基于给定的问题，问题求解的第一步是目标的表示。o搜索就是找到智能系统的动作序列的过程。2023/3/254o搜索算法的输入是给定的问题，输出是表示为动作序列的方案。o一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）o因此，求解问题包括：n目标表示目标表示n搜索搜索n执行执行2023/3/255（1）初始状态集合：定义了初始的环境。（2）操作符集合：把一个问题从一个状态变换为另一个状态的动作集合。（3）目标检测函数：用来确定一个状态是不是目标。（4）路径费用函数：对每条路径赋予一定费用的函数。其中，初其中，初始状态集始状态集合和操作合和操作符集合定符集合定义了问题义了问题的搜索空的搜索空间。间。一般给定问题就是确定该问题的一一般给定问题就是确定该问题的一些基本信息，一个问题由些基本信息，一个问题由4 4部分组成部分组成:2023/3/256o和通常的搜索空间不同，人工智能中大多数问题的状态空间在问题求解之前不是全部知道的。在人工智能中，搜索问题一般包括两个重要在人工智能中，搜索问题一般包括两个重要的问题：的问题：v搜索什么搜索什么搜索什么通常指的就是目标。搜索什么通常指的就是目标。v在哪里搜索在哪里搜索在哪里搜索就是在哪里搜索就是“搜索空间搜索空间”。搜索空间通常。搜索空间通常是指一系列状态的汇集，因此称为是指一系列状态的汇集，因此称为状态空间状态空间。2023/3/257o所以，人工智能中的搜索可以分成两个阶段：n状态空间的生成阶段n在该状态空间中对所求问题状态的搜索搜索可以根据是否使用启发式信息分搜索可以根据是否使用启发式信息分为为v盲目搜索盲目搜索v启发式搜索启发式搜索 2023/3/258o盲目搜索盲目搜索 只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。o启发式搜索启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。2023/3/259o根据问题的表示方式分为n状态空间搜索n与或图搜索状态空间状态空间搜索是用搜索是用状态空间状态空间法来求解法来求解问题所进问题所进行的搜索行的搜索与与/或图搜或图搜索是指用问索是指用问题规约方法题规约方法来求解问题来求解问题时所进行的时所进行的搜索。搜索。2023/3/2510o考虑一个问题的状态空间为一棵树的形式。o宽度优先搜索o深度优先搜索如果根节点首先如果根节点首先扩展，然后是扩扩展，然后是扩展根节点生成的展根节点生成的所有节点，然后所有节点，然后是这些节点的后是这些节点的后继，如此反复下继，如此反复下去。去。在树的最深一层的节点在树的最深一层的节点中扩展一个节点。只有中扩展一个节点。只有当搜索遇到一个死亡节当搜索遇到一个死亡节点（非目标节点并且是点（非目标节点并且是无法扩展的节点）的时无法扩展的节点）的时候，才返回上一层选择候，才返回上一层选择其他的节点搜索。其他的节点搜索。2023/3/2511o无论是宽度优先搜索还是深度优先搜索，遍历节点的顺序一般都是固定的，即一旦搜索空间给定，节点遍历的顺序就固定了。这种类型的遍历称为“确定性”的，也就是盲目搜索。o对于启发式搜索，在计算每个节点的参数之前无法确定先选择哪个节点扩展，这种搜索一般也称为非确定的。2023/3/2512o完备性：n如果存在一个解答，该策略是否保证能够找到？o时间复杂性：n需要多长时间可以找到解答？o空间复杂性：n执行搜索需要多少存储空间？o最优性：n如果存在不同的几个解答，该策略是否可以发现最高质量的解答？搜索策略评价标准搜索策略评价标准:2023/3/2513有许多智力问题有许多智力问题(如梵塔问题、旅行商问题、八皇如梵塔问题、旅行商问题、八皇后问题、农夫过河问题等后问题、农夫过河问题等)和实际问题（如路径规和实际问题（如路径规划、机器人行动规划等）都可以归结为划、机器人行动规划等）都可以归结为状态空间搜状态空间搜索索。用用状态空间搜索状态空间搜索来求解问题的系统均定义一个来求解问题的系统均定义一个状态状态空间空间，并通过适当的，并通过适当的搜索算法搜索算法在在状态空间状态空间中搜索中搜索解解答路径答路径。3.2 基于状态空间图的搜索技术基于状态空间图的搜索技术2023/3/2514状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(1)(1)状态空间的表示状态空间的表示状态空间的表示状态空间的表示oo状态空间记为状态空间记为状态空间记为状态空间记为SPSP，可表示为二元组：，可表示为二元组：，可表示为二元组：，可表示为二元组：n nSP=(S,O)SP=(S,O)nS问题求解（即搜索）过程中所有问题求解（即搜索）过程中所有可能到达可能到达的的合法状态合法状态构成的集合；构成的集合；nO操作算子操作算子的集合，的集合，操作算子的执行会导致问题状态的操作算子的执行会导致问题状态的变迁变迁；n状态状态用于记载问题求解（即搜索）过程中用于记载问题求解（即搜索）过程中某一时刻问某一时刻问题现状的快照题现状的快照；o抽象为矢量形式抽象为矢量形式 Q=q0,q1,qnTo每个元素每个元素qi称为称为状态分量状态分量 o给定每个给定每个状态分量状态分量qi的值就得到一个具体的状态的值就得到一个具体的状态 Qk=q0k,q1k,qnkT2023/3/2515状态状态表示状态的变迁表示状态的变迁操作算子操作算子问题的状态空间问题的状态空间是一个表示该问题的全部可能状态是一个表示该问题的全部可能状态及其变迁的及其变迁的有向图有向图。o节点节点n状态状态o有向弧有向弧n状态的变迁状态的变迁 o弧上的标签弧上的标签n导致状态变迁的导致状态变迁的操作算子操作算子 用用状态空间搜索状态空间搜索来求解问题的系统均定义一个来求解问题的系统均定义一个状态状态空间空间，并通过适当的，并通过适当的搜索算法搜索算法在在状态空间状态空间中搜索中搜索解解答路径答路径。2023/3/2516例例例例1 1：走迷宫走迷宫走迷宫走迷宫是人们熟悉的一种游戏。是人们熟悉的一种游戏。是人们熟悉的一种游戏。是人们熟悉的一种游戏。状态空间搜索状态空间搜索2023/3/2517oo格子、入口和出口格子、入口和出口格子、入口和出口格子、入口和出口节点节点节点节点状态状态状态状态oo通道通道通道通道有向弧有向弧有向弧有向弧操作算子操作算子操作算子操作算子oo迷宫可以由一个迷宫可以由一个迷宫可以由一个迷宫可以由一个有向图有向图有向图有向图表示表示表示表示2023/3/2518 例例2:在在一一个个33的的方方格格棋棋盘盘上上放放置置着着1,2,3,4,5,6,7,8八八个个数数码码，每每个个数数码码占占一一格格，且且有有一一个个空空格格。这这些些数数码码可可在在棋棋盘盘上上移移动动，其其移移动动规规则则是是：与与空空格格相相邻邻的数码方可移入空格。的数码方可移入空格。现现在在的的问问题题是是：对对于于指指定定的的初初始始棋棋局局和和目目标标棋棋局局，给出给出数码的移动序列数码的移动序列。该问题称为。该问题称为八数码问题八数码问题。56741382初始棋局初始棋局56748321目标棋局目标棋局移动数码移动数码2023/3/25192 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 3 8 47 6 52023/3/25202023/3/2521状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(2)(2)状态空间表示的经典例子状态空间表示的经典例子状态空间表示的经典例子状态空间表示的经典例子“传教士和野人问题传教士和野人问题传教士和野人问题传教士和野人问题”o问题的描述问题的描述问题的描述问题的描述：n nN N个传教士带领个传教士带领个传教士带领个传教士带领N N个野人划船过河；个野人划船过河；个野人划船过河；个野人划船过河；n n3 3个安全约束条件：个安全约束条件：个安全约束条件：个安全约束条件：o1)船上人数不得超过载重限量，设为船上人数不得超过载重限量，设为K个人；个人；o2)任何时刻（包括两岸、船上）野人数目不得任何时刻（包括两岸、船上）野人数目不得超过传教士；超过传教士；o3)允许在河的某一岸或者在船上只有野人而没允许在河的某一岸或者在船上只有野人而没有传教士；有传教士；2023/3/2522状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(2)(2)状态空间表示的经典例子状态空间表示的经典例子状态空间表示的经典例子状态空间表示的经典例子“传教士和野人问题传教士和野人问题传教士和野人问题传教士和野人问题”o 特例：特例：特例：特例：N=3N=3，K=2 K=2 n n状态分量状态分量状态分量状态分量mm传教士在左岸的实际人数传教士在左岸的实际人数传教士在左岸的实际人数传教士在左岸的实际人数n n状态分量状态分量状态分量状态分量c c野人在左岸的实际人数野人在左岸的实际人数野人在左岸的实际人数野人在左岸的实际人数n n状态分量状态分量状态分量状态分量b b指示船是否在左岸指示船是否在左岸指示船是否在左岸指示船是否在左岸(1(1、0)0)n n3 3个安全约束条件个安全约束条件个安全约束条件个安全约束条件oom m c(c(左岸安全左岸安全左岸安全左岸安全)且且且且 N-m N-m N-c(N-c(右岸安全右岸安全右岸安全右岸安全););oom=0m=0且且且且0c N(0c N(左岸没有传道士，右岸一定安全左岸没有传道士，右岸一定安全左岸没有传道士，右岸一定安全左岸没有传道士，右岸一定安全););ooN-m=0N-m=0且且且且0N-cN(0N-cN(右岸没有传道士，左岸一定安全右岸没有传道士，左岸一定安全右岸没有传道士，左岸一定安全右岸没有传道士，左岸一定安全););2023/3/2523设设设设初始状态初始状态初始状态初始状态下传教士、野人和船都在左岸，下传教士、野人和船都在左岸，下传教士、野人和船都在左岸，下传教士、野人和船都在左岸，目标状态目标状态目标状态目标状态下下下下这三者均在右岸，这三者均在右岸，这三者均在右岸，这三者均在右岸，问题状态问题状态问题状态问题状态以以以以（m,c,bm,c,b）表示表示表示表示。oo问题的求解任务可描述为：问题的求解任务可描述为：问题的求解任务可描述为：问题的求解任务可描述为：(3,3,1)(3,3,1)(0,0,0)(0,0,0)oo该简单问题该简单问题该简单问题该简单问题可能到达可能到达的的合法状态合法状态：n n可能状态可能状态可能状态可能状态总数总数总数总数：4 4 2=32n n根据条件得出根据条件得出根据条件得出根据条件得出合法状态合法状态合法状态合法状态：2020oom m c c 且且且且 N-m N-m N-c N-c(左岸安全且右岸安全左岸安全且右岸安全左岸安全且右岸安全左岸安全且右岸安全)n nm=1,c=1m=1,c=1；m=2,c=2m=2,c=2 oom=0m=0且且且且0c N(0c N(左岸没有传道士左岸没有传道士左岸没有传道士左岸没有传道士)n nm=0,c=0,1,2,3m=0,c=0,1,2,3 ooN-m=0N-m=0且且且且0N-cN(0N-cN(右岸没有传道士右岸没有传道士右岸没有传道士右岸没有传道士)n nm=3,c=0,1,2,3m=3,c=0,1,2,3n n不可能到达的合法状态不可能到达的合法状态不可能到达的合法状态不可能到达的合法状态：o(0,0,1),(0,3,0),(3,0,1),(3,3,0)n n可能到达可能到达可能到达可能到达的的的的合法状态合法状态合法状态合法状态共共共共1616个个个个2023/3/2524状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(2)状态空间表示的经典例子状态空间表示的经典例子“传教士和野人问题传教士和野人问题”o定义定义2类类操作算子操作算子：nL(x,y)指示从指示从左岸左岸到到右岸右岸的划船操作的划船操作 nR(x,y)指示从指示从右岸右岸到到左岸左岸的划船操作的划船操作ox+y K=2(船的载重限制船的载重限制)；ox和和y取值的可能组合只有取值的可能组合只有5个个o10，20，11，01，02 o(允许在船上只有野人而没有传教士允许在船上只有野人而没有传教士)n共有共有10个操作算子个操作算子2023/3/2525渡河问题的状态空间有向图渡河问题的状态空间有向图2023/3/2526状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示o由此例可以看出由此例可以看出n n用状态空间方法表示问题时，首先必须用状态空间方法表示问题时，首先必须用状态空间方法表示问题时，首先必须用状态空间方法表示问题时，首先必须定义状定义状定义状定义状态的描述形式态的描述形式态的描述形式态的描述形式，通过使用这种描述形式可把问，通过使用这种描述形式可把问，通过使用这种描述形式可把问，通过使用这种描述形式可把问题的题的题的题的一切状态都表示出来一切状态都表示出来一切状态都表示出来一切状态都表示出来。另外，还要。另外，还要。另外，还要。另外，还要定义一定义一定义一定义一组操作组操作组操作组操作，通过使用这些操作可把问题，通过使用这些操作可把问题，通过使用这些操作可把问题，通过使用这些操作可把问题由一种状由一种状由一种状由一种状态转变为另一种状态态转变为另一种状态态转变为另一种状态态转变为另一种状态。n n问题的求解过程是一个问题的求解过程是一个问题的求解过程是一个问题的求解过程是一个不断把操作作用于状态不断把操作作用于状态不断把操作作用于状态不断把操作作用于状态的过程的过程的过程的过程。如果在使用某个操作后得到的新状态。如果在使用某个操作后得到的新状态。如果在使用某个操作后得到的新状态。如果在使用某个操作后得到的新状态是目标状态，就得到了问题的一个解。这个解是目标状态，就得到了问题的一个解。这个解是目标状态，就得到了问题的一个解。这个解是目标状态，就得到了问题的一个解。这个解是从是从是从是从初始状态到目标状态所用操作构成的序列初始状态到目标状态所用操作构成的序列初始状态到目标状态所用操作构成的序列初始状态到目标状态所用操作构成的序列。2023/3/2527状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示o由此例可以看出由此例可以看出n n要使问题由一种状态转变到另一种状态时，就要使问题由一种状态转变到另一种状态时，就要使问题由一种状态转变到另一种状态时，就要使问题由一种状态转变到另一种状态时，就必须使用一次操作。这样，在从初始状态转变必须使用一次操作。这样，在从初始状态转变必须使用一次操作。这样，在从初始状态转变必须使用一次操作。这样，在从初始状态转变到目标状态时，就可能存在多个操作序列到目标状态时，就可能存在多个操作序列到目标状态时，就可能存在多个操作序列到目标状态时，就可能存在多个操作序列(即得即得即得即得到多个解到多个解到多个解到多个解)。那么，其中。那么，其中。那么，其中。那么，其中使用操作最少或较少的使用操作最少或较少的使用操作最少或较少的使用操作最少或较少的解才为最优解解才为最优解解才为最优解解才为最优解(因为只有在使用操作时所付出的因为只有在使用操作时所付出的因为只有在使用操作时所付出的因为只有在使用操作时所付出的代价为最小的解才是最优解代价为最小的解才是最优解代价为最小的解才是最优解代价为最小的解才是最优解)。n n对其中的某一个状态，可能存在多个操作使对其中的某一个状态，可能存在多个操作使对其中的某一个状态，可能存在多个操作使对其中的某一个状态，可能存在多个操作使该状态变到几个不同的后继状态那么到底用该状态变到几个不同的后继状态那么到底用该状态变到几个不同的后继状态那么到底用该状态变到几个不同的后继状态那么到底用哪个操作进行搜索呢哪个操作进行搜索呢哪个操作进行搜索呢哪个操作进行搜索呢?这就有赖于这就有赖于这就有赖于这就有赖于搜索策略了搜索策略了搜索策略了搜索策略了不同的搜索策略有不同的顺序不同的搜索策略有不同的顺序不同的搜索策略有不同的顺序不同的搜索策略有不同的顺序，这就是本章后，这就是本章后，这就是本章后，这就是本章后面要讨论的问题。面要讨论的问题。面要讨论的问题。面要讨论的问题。2023/3/2528课堂练习课堂练习o有一农夫带一只狐狸、一只小羊和一篮菜过河（从有一农夫带一只狐狸、一只小羊和一篮菜过河（从左岸到右岸）。假设船太小，农夫每次只能带一样左岸到右岸）。假设船太小，农夫每次只能带一样东西过河；考虑到安全，无农夫看管时，狐狸和小东西过河；考虑到安全，无农夫看管时，狐狸和小羊不能在一起，小羊和那篮菜也不能在一起。请为羊不能在一起，小羊和那篮菜也不能在一起。请为该问题的解决设计状态空间，并画出状态空间图。该问题的解决设计状态空间，并画出状态空间图。2023/3/2529解析解析o以变量以变量m m、f f、s s、v v分别指示农夫、狐狸、小羊、菜分别指示农夫、狐狸、小羊、菜,且每个且每个变量只可取值变量只可取值1(1(表示在左岸表示在左岸)或或0(0(表示在右岸表示在右岸)。问题状态可。问题状态可以四元组以四元组(m(m、f f、s s、v)v)描述描述,设初始状态下均在左岸设初始状态下均在左岸,目标状目标状态下都到达右岸。从而态下都到达右岸。从而,问题求解任务可描述为问题求解任务可描述为 (1,1,1,1)-(0,0,0,0)(1,1,1,1)-(0,0,0,0)o由于问题简单由于问题简单,状态空间中可能的状态总数为状态空间中可能的状态总数为2222=2222=16,16,由于要遵从安全限制由于要遵从安全限制,合法的状态只有合法的状态只有(除初、目状态外除初、目状态外):):1110 1110，11011101，10111011，10101010，01010101，00010001，00100010，01000100；不合法状态有不合法状态有:0111,1000,1100,0011,0110,1001:0111,1000,1100,0011,0110,1001o设计二类操作算子设计二类操作算子:Lx:Lx、Rx,xRx,x为为m m、f f、s s、v v时分别指示农夫时分别指示农夫独自独自,带狐狸带狐狸,带小羊带小羊,带菜过河；状态空间图如下所示带菜过河；状态空间图如下所示.由于由于LxLx和和RxRx是互逆操作是互逆操作,故而解答路径可有无数条故而解答路径可有无数条,但最近的只有但最近的只有二条二条;都是都是7 7个操作步个操作步.o思考：为什么不把船的状态放到状态空间中去？思考：为什么不把船的状态放到状态空间中去？2023/3/2530解析解析:四元组四元组(m(m、f f、s s、v)v)2023/3/2531状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(3)状态空间的搜索状态空间的搜索o状态空间的搜索记为状态空间的搜索记为SE，可表示为五元组：，可表示为五元组：nSE=(S,O,E,I,G)；nE搜索引擎；搜索引擎；nI问题的初始状态，问题的初始状态，I S；nG问题的目标状态集合，问题的目标状态集合，G S。o搜索引擎搜索引擎E可以设计为可以设计为实现任何搜索算法实现任何搜索算法的控制系统。的控制系统。o基本思想基本思想通过搜索引擎通过搜索引擎E寻找一个寻找一个操作算子的调用序操作算子的调用序列列，使问题从初始状态，使问题从初始状态I变迁到目标状态变迁到目标状态G之一。之一。o解答路径解答路径初初-目变迁过程中目变迁过程中的的状态序列状态序列或相应的或相应的操作算操作算子调用序列子调用序列。2023/3/2532状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示o或图（一般图）或图（一般图）n一个状态一个状态可以可以有多个可供选择有多个可供选择的操作算子；的操作算子；n操作算子间的选择是一种操作算子间的选择是一种“或或”的关系的关系;n这样的有向图称为这样的有向图称为或图。或图。2023/3/2533状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(3)(3)状态空间的搜索状态空间的搜索o或图（一般图）或图（一般图）n一个状态可以有多个可供选择的操作算子；一个状态可以有多个可供选择的操作算子；n操操作作算算子子间间的的选选择择是是一一种种“或或”的的关关系系，这这样样的的有有向图称为向图称为或图。或图。o状态空间状态空间一般都表示为一般都表示为或图（一般图）或图（一般图）o搜搜索索图图在在搜搜索索解解答答路路径径的的过过程程中中画画出出搜搜索索时时涉涉及及到到的节点和弧线，构成所谓的的节点和弧线，构成所谓的搜索图搜索图。状态空间搜索状态空间搜索一般图搜索一般图搜索2023/3/2534状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(3)状态空间的搜索状态空间的搜索o状态空间状态空间、搜索图搜索图和和解答路径解答路径之间的关系之间的关系S0Sg2023/3/2535状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(4)(4)一般图搜索例子一般图搜索例子一般图搜索例子一般图搜索例子八数码游戏八数码游戏八数码游戏八数码游戏 oo求解的问题：求解的问题：求解的问题：求解的问题：n n给定初始布局给定初始布局给定初始布局给定初始布局(即即即即初始状态初始状态初始状态初始状态)和目标布局和目标布局和目标布局和目标布局(即即即即目标状态目标状态目标状态目标状态)，n n如何移动数码才能从初始布局到达目标布局？如何移动数码才能从初始布局到达目标布局？如何移动数码才能从初始布局到达目标布局？如何移动数码才能从初始布局到达目标布局？oo解答解答解答解答n n就是一个合法的就是一个合法的就是一个合法的就是一个合法的棋牌走步序列棋牌走步序列棋牌走步序列棋牌走步序列。初始布局初始布局目标布局目标布局移动数码移动数码2023/3/2536状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(4)(4)一般图搜索例子一般图搜索例子一般图搜索例子一般图搜索例子八数码游戏八数码游戏八数码游戏八数码游戏 oo用一般图搜索方法解决该问题的步骤：用一般图搜索方法解决该问题的步骤：用一般图搜索方法解决该问题的步骤：用一般图搜索方法解决该问题的步骤：n n1 1、为、为、为、为问题状态问题状态问题状态问题状态的表示建立数据结构的表示建立数据结构的表示建立数据结构的表示建立数据结构n n2 2、制定、制定、制定、制定操作算子操作算子操作算子操作算子集合集合集合集合n n3 3、设计、设计、设计、设计搜索引擎搜索引擎搜索引擎搜索引擎 oo第一步：为问题状态的表示建立数据结构第一步：为问题状态的表示建立数据结构第一步：为问题状态的表示建立数据结构第一步：为问题状态的表示建立数据结构n n3333的一个矩阵的一个矩阵的一个矩阵的一个矩阵S Sn n矩阵元素矩阵元素矩阵元素矩阵元素SijSij 0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,7,8,其中其中其中其中1i,j3 1i,j3 n n数字数字数字数字0 0表示空格表示空格表示空格表示空格 n n数字数字数字数字1-81-8表示相应的棋牌表示相应的棋牌表示相应的棋牌表示相应的棋牌oo八数码问题就可表示为：八数码问题就可表示为：八数码问题就可表示为：八数码问题就可表示为：2023/3/2537状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示初始布局初始布局目标布局目标布局移动数码移动数码(4)(4)一般图搜索例子一般图搜索例子一般图搜索例子一般图搜索例子八数码游戏八数码游戏八数码游戏八数码游戏 2023/3/2538状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示(4)一般图搜索例子一般图搜索例子八数码游戏八数码游戏 o第二步：制定操作算子集第二步：制定操作算子集n直观方法直观方法为每个棋牌制定一套可能的走步：左、上、右、为每个棋牌制定一套可能的走步：左、上、右、下四种移动。下四种移动。o需要需要32个操作算子个操作算子n简易方法简易方法仅为空格制定这仅为空格制定这4种走步。种走步。o仅需仅需4个操作算子个操作算子o第三步：设计搜索引擎第三步：设计搜索引擎 n问题状态空间的大小问题状态空间的大小与与问题涉及的元素问题涉及的元素个数是程个数是程指数级指数级爆炸式增长爆炸式增长（即，（即，组合爆炸问题组合爆炸问题）o如，棋盘布局（问题状态）总共有如，棋盘布局（问题状态）总共有9!=362880个个 n研究焦点研究焦点是是解决组合爆炸问题解决组合爆炸问题，通过压缩搜索空间通过压缩搜索空间，提提高搜索效率高搜索效率。2023/3/2539状态空间搜索状态空间搜索1.1.状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间及其搜索的表示状态空间状态空间、搜索图搜索图和和解答路径解答路径之间的关系之间的关系S0Sg2023/3/2540状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（1）搜索术语）搜索术语o1、节点深度、节点深度n根节点根节点指示指示初始状态初始状态，令其深度为，令其深度为0；n搜索图中的其他节点的搜索图中的其他节点的深度深度dn就可以递归地定义为就可以递归地定义为其其父节点深度父节点深度dn-1加加1：dn=dn-1+1。根节点深度根节点深度=0=0第第第第n-1n-1n-1n-1层节点层节点层节点层节点d d d dn-1n-1n-1n-1第第第第n n n n层节点层节点层节点层节点d d d dn n n n=d d d dn-1n-1n-1n-1+1+1+1+1搜索图搜索图2023/3/2541状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（1）搜索术语）搜索术语o2、节点扩展、节点扩展n应用应用操作算子操作算子将将上一状态上一状态（节点（节点ni）变迁到）变迁到下一状态下一状态（节点（节点nj）n节点节点ni称为称为被扩展节点被扩展节点（父节点）（父节点）n节点节点nj称为称为ni的的子节点子节点节点节点节点节点n n n ni i i i节点节点节点节点n n n nj j j j2023/3/2542（1 1）搜索术语）搜索术语）搜索术语）搜索术语oo3 3、路径、路径、路径、路径 n n节点节点节点节点n ni i到到到到n nj j的路径是由相的路径是由相的路径是由相的路径是由相邻节点间的邻节点间的邻节点间的邻节点间的弧线构成的弧线构成的弧线构成的弧线构成的折线折线折线折线n n要求路径是无环的要求路径是无环的要求路径是无环的要求路径是无环的o4、路径代价、路径代价相邻节点相邻节点ni和和ni+1间的间的路径代价路径代价记为记为C(ni,ni+1)n通常令通常令任意相邻节点间任意相邻节点间的路径代价相同的路径代价相同，并以，并以路径长度路径长度1 1指示。指示。n即即C(ni,ni+1)=1。状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略节点节点n ni i节点节点ni+1节点节点nj2023/3/2543状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（1 1）搜索术语）搜索术语）搜索术语）搜索术语oo4 4、路径代价、路径代价、路径代价、路径代价目标状态节点目标状态节点目标状态节点目标状态节点n n n ng g g g节点节点节点节点n n n ni i i i节点节点节点节点n n n nk k k kC(nk,ng)C(ni,nk)C(ni,ng)2023/3/2544状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2 2）一般图搜索算法）一般图搜索算法）一般图搜索算法）一般图搜索算法o符号说明：符号说明：ns-初始状态节点初始状态节点nG-搜索图搜索图nOPEN-存放存放待扩展节点待扩展节点的表的表nCLOSE-存放存放已被扩展的节点已被扩展的节点的表的表nMOVE-FIRST(OPEN)-取取OPEN表首的节点表首的节点作为作为当前要被扩展当前要被扩展的节点的节点n，同时，同时将节点将节点n移至移至CLOSE表表o一般图搜索算法划分为二个阶段：一般图搜索算法划分为二个阶段：n1、初始化、初始化 n2、搜索循环、搜索循环 2023/3/2545状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2 2）一般图搜索算法）一般图搜索算法）一般图搜索算法）一般图搜索算法o算法划分为二个阶段：算法划分为二个阶段：n1、初始化、初始化 o建立建立只包含初始状态节点只包含初始状态节点s的搜索图的搜索图G:=soOPEN:=soCLOSE:=n2、搜索循环、搜索循环oMOVE-FIRST(OPEN)-取出取出OPEN表首的节点表首的节点n作为扩展的节作为扩展的节点，同时将其移到点，同时将其移到close表表 o扩展出扩展出n的子节点的子节点,插入插入搜索图搜索图G和和OPEN表表 o适当的标记和修改指针适当的标记和修改指针o排序排序OPEN表表n通过循环地执行该算法，通过循环地执行该算法，搜索图搜索图G会因不断有新节点加入而逐会因不断有新节点加入而逐步长大，直到搜索到目标节点。步长大，直到搜索到目标节点。2023/3/2546以下面的八数码为例，看一般图的搜索算法以下面的八数码为例，看一般图的搜索算法以下面的八数码为例，看一般图的搜索算法以下面的八数码为例，看一般图的搜索算法初始布局初始布局目标布局目标布局移动数码移动数码状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略2023/3/25472023/3/25482023/3/25492023/3/25502023/3/25512023/3/25522023/3/25532023/3/25542023/3/25552023/3/25562023/3/25572023/3/25582023/3/25592023/3/25602023/3/25612023/3/25622023/3/25632023/3/25642023/3/25652023/3/2566状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2 2）一般图搜索算法）一般图搜索算法）一般图搜索算法）一般图搜索算法搜索过程中的指针修改搜索过程中的指针修改o节点节点n扩展后扩展后的子节点分为的子节点分为3类类：n(i)全新节点全新节点n(ii)已出现在已出现在OPEN表表中的节点中的节点n(iii)已出现的已出现的CLOSE表表中的节点中的节点o指针标记和修改的方法：指针标记和修改的方法：n(i)类节点：加入类节点：加入OPEN表，建立从子节点到父节点表，建立从子节点到父节点n的指针的指针n(ii)类节点、类节点、(iii)类节点类节点o比较比较经由经由老父节点老父节点、新父节点新父节点n到达到达初始状态节点初始状态节点的的路径代路径代价价 o经由新父节点经由新父节点n的代价比较小，则将原子节点指向老父节点的代价比较小，则将原子节点指向老父节点的指针，修改为指向新父节点的指针，修改为指向新父节点no(iii)类节点还得从类节点还得从CLOSE表中移出，重新加入表中移出，重新加入OPEN表。表。2023/3/2567状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略Sn4ninjn1n2n3n31n32o节点节点ni是当前扩展的节点；是当前扩展的节点；o扩展出扩展出4个后续节点；个后续节点；on1、n2是新节点是新节点，只需建立只需建立指向父节点的指针，并加入指向父节点的指针，并加入OPEN表表；2023/3/2568状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略Sn4ninjn1n2n3n31n32on4已经存在于已经存在于OPEN表，并表，并且已有父节点且已有父节点njnn4经经nj的路径代价大的路径代价大n取消取消n4指向指向nj的指针的指针n改为建立改为建立n4指向新父节点指向新父节点ni的的指针指针on3已经存在于已经存在于CLOSE表，表，并且已有父节点并且已有父节点njn需要做和需要做和n4同样的比较和指同样的比较和指针修改工作。并且要重新加入针修改工作。并且要重新加入open表。表。2023/3/2569状态空间搜索状态空间搜索2.2.一般图搜索策略一般图搜索策略一般图搜索策略一般图搜索策略（2）一般图搜索算法）一般图搜索算法oOPEN表中节点简单的排序方式表中节点简单的排序方式：n深度优先深度优先扩展当前节点后生成的子节点总是扩展当前节点后生成的子节点总是置于置于OPEN表的前端表的前端，即，即OPEN表表作为作为栈栈，后进先出后进先出，使，使搜索搜索优先向纵深方向发展优先向纵深方向发展。2023/3/2570深度优先深度优先实例实例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 4
