上海交通大学：《人工智能》课程教学资源（PPT课件）第4章 图搜索技术

第4章图搜索技术 根据问题的实际情况不断寻找可利用的 知识,从而构造一条代价较少的推理路 线,使问题得到圆满解决的过程称为搜 索。搜索实用于:结构不良问题,无成 熟算法;或有算法,但问题复杂,如 博弈。 或图搜索;与或图搜索

第4章 图搜索技术 根据问题的实际情况不断寻找可利用的 知识，从而构造一条代价较少的推理路 线，使问题得到圆满解决的过程称为搜 索。搜索实用于：结构不良问题，无成 熟算法；或有算法 ，但问题复杂，如 博弈。 或图搜索；与或图搜索

第4章图搜索技术--4.1状态 图搜索 ◆4.1.1状态图 例、八数码问题的状态图表示。 状态是描述问题求解过程中任一时刻的状况, 般用一组变量的有序组合表示。引起状态 中某些分量发生变化,从而使问题从一个状 态变为另一个状态的操作、规则、变换称为 算符。问题求解就是寻找一个从初始状态到 目标状态的算符序列的过程。问题求解过程 可描述为一个有向图,其中的节点代表状态 边表示状态转换之间的算符

第4章 图搜索技术----4.1 状态 图搜索 4.1.1 状态图 例、八数码问题的状态图表示。 状态是描述问题求解过程中任一时刻的状况， 一般用一组变量的有序组合表示。引起状态 中某些分量发生变化，从而使问题从一个状 态变为另一个状态的操作、规则、变换称为 算符。问题求解就是寻找一个从初始状态到 目标状态的算符序列的过程。问题求解过程 可描述为一个有向图，其中的节点代表状态， 边表示状态转换之间的算符

第4章图搜索技术--4.1状态 图搜索 ◆4.1.2状态图搜索 1、搜索方式 树式搜索:每次扩展所有子节点 线式搜索:每次只扩展一个子节点 可回溯(穷举式搜索)不可回溯(随机碰 撞式搜索)

第4章 图搜索技术----4.1 状态 图搜索 4.1.2 状态图搜索 1、搜索方式 树式搜索：每次扩展所有子节点 线式搜索：每次只扩展一个子节点 可回溯（穷举式搜索） 不可回溯（随机碰 撞式搜索）

2、搜索策略 搜索分为盲目搜索和启发式搜索。盲目搜索: 按预定的控制策略进行搜索,在搜索过程中 获得的中间信息不用来改进控制策略;启发 式搜索:在搜索过程中加入了与问题有关的 启发性信息,用以指导搜索朝着最有希望的 方向前进,加速问题的求解过程并找到最优 解

2、搜索策略 搜索分为盲目搜索和启发式搜索。盲目搜索： 按预定的控制策略进行搜索，在搜索过程中 获得的中间信息不用来改进控制策略；启发 式搜索：在搜索过程中加入了与问题有关的 启发性信息，用以指导搜索朝着最有希望的 方向前进，加速问题的求解过程并找到最优 解

第4章图搜索技术--41状态图搜索 3、搜索算法 树式搜索算法: 步1把初始节点放入OPEN表; 步2检查OPEN表,若为空,则问题无解,退出; 步3移出OPEN表中第一个节点并放入 CLOSED表中,并记该节点 为n; 步4考察节点n是否为目标节点,若是,则搜索成功,退出 步5若n不可扩展,则转步2; 步6扩展节点n,生成所有子节点,对这组子节点作如下处理: (1)、如果有节点n的先辈节点,则删除之 (2)、如果有已存在于OPEN表的节点,也删除之;但删除之 前要比较其返回初始节点的新路径与原路径,如果新路径“短”, 则修改这些节点在OPEN表中的原指向父节点的指针,使其指向 新的父节点

第4章 图搜索技术----4.1 状态图搜索 3、搜索算法 树式搜索算法： 步1 把初始节点放入OPEN表； 步2 检查OPEN表，若为空，则问题无解，退出； 步3 移出OPEN表中第一个节点并放入CLOSED表中，并记该节点 为n; 步4 考察节点n是否为目标节点，若是，则搜索成功，退出； 步5 若n不可扩展，则转步2； 步6 扩展节点n，生成所有子节点，对这组子节点作如下处理： （1）、如果有节点n的先辈节点，则删除之； （2）、如果有已存在于OPEN表的节点，也删除之；但删除之 前要比较其返回初始节点的新路径与原路径，如果新路径“短” ， 则修改这些节点在OPEN表中的原指向父节点的指针，使其指向 新的父节点

第4章图搜索技术--41状态图搜索 (3)、如果有已存在于 CLOSED表中的节点,则作与(2)同样的 处理,并且再将其移出 CLOSED表,放入OPEN表重新扩展 (4)、对其余子节点,配上指向父节点n的指针后放入OPEN表, 对OPEN表按某种搜索策略排序后转步2。 线式搜索算法 不可回溯的线式搜索 步1把初始节点S0放入 CLOSED表中 步2令N 步3若N是目标节点,则搜索成功,结束; 步4若N不可扩展,则搜索失败,退出。 步5扩展N,选取一个未在 CLOSED表中出现的子节点N1放入 CLOSED表中,令N=N1,转步3

第4章 图搜索技术----4.1 状态图搜索 （3）、如果有已存在于CLOSED表中的节点，则作与（2）同样的 处理，并且再将其移出CLOSED表，放入OPEN表重新扩展； （4）、对其余子节点，配上指向父节点n的指针后放入OPEN表， 对OPEN表按某种搜索策略排序后转步2。 线式搜索算法 不可回溯的线式搜索： 步1 把初始节点S0放入CLOSED表中； 步2 令N= S0 ； 步3 若N是目标节点，则搜索成功，结束; 步4 若N不可扩展，则搜索失败，退出。 步5 扩展N，选取一个未在CLOSED表中出现的子节点N1放入 CLOSED表中，令N=N1，转步3

第4章图搜索技术--41状态图搜索 可回溯的线式搜索: 步1把初始节点S。放入 CLOSED表中; 步2令N=S0 步3若N是目标节点,则搜索成功,结束; 步4若N不可扩展,则移出 CLOSED表的末端节点N, 若Na=S0,则搜索失败,退出。否则,以 CLOSED表 新的末端节点N作为N即令N=N,转步4 步5扩展N,选取一个未在 CLOSED表中出现的子节点 N1放入 CLOSED表中,令N=N1,转步3

第4章 图搜索技术----4.1 状态图搜索 可回溯的线式搜索： 步1 把初始节点S0放入CLOSED表中； 步2 令N= S0 ； 步3 若N是目标节点，则搜索成功，结束; 步4 若N不可扩展，则移出CLOSED表的末端节点Ne， 若Ne =S0 ，则搜索失败，退出。否则，以CLOSED表 新的末端节点Ne作为N,即令N=Ne，转步4 步5 扩展N，选取一个未在CLOSED表中出现的子节点 N1放入CLOSED表中，令N=N1，转步3

第4章图搜索技术--41状态图搜索 4.13穷举式搜索 1、广度优先搜索 又称宽度优先思索,优先在同一级节点中考察,只有当同一级节点扩展完 以后,才扩展下一级节点。 例、解八数码问题。初始状态:(2,8,3,4,5,6,7,1),目标状态 (1,2,3,4,5,6,7,8) 广度优先搜索算法 步1把初始节点S0放入OPEN表中; 步2若OPEN表为空,则搜索失败,退出:表中 一步3取OPEN表中前面第一个节点N放入 CLOSE 步4若目标节点Sg=N,则搜索成功,结束 步5若N不可扩展,则转步2。 步6扩展N,将其所有子节点配上指向N的指针依次放入OPEN表 的尾部,转步2

第4章 图搜索技术----4.1 状态图搜索 4.1.3 穷举式搜索 1、广度优先搜索 又称宽度优先思索，优先在同一级节点中考察，只有当同一级节点扩展完 以后，才扩展下一级节点。 例、解八数码问题。初始状态： （2，8，3，4，5，6，7，1），目标状态： （1，2，3，4，5，6，7，8） 广度优先搜索算法： 步1 把初始节点S0放入OPEN表中； 步2 若OPEN表为空，则搜索失败，退出； 步3 取OPEN表中前面第一个节点N放入CLOSED表中； 步4 若目标节点Sg =N，则搜索成功，结束; 步5 若N不可扩展，则转步2。 步6 扩展N，将其所有子节点配上指向N的指针依次放入OPEN表 的尾部，转步2

第4章图搜索技术--41状态图搜索 广度优先搜索的特点:完备、解是最优解、效率 低 2、深度优先搜索 在搜索的每一层,始终只扩展一个节点,不断地 向纵深前进,直到不能再前进时,才从当前节点 返回到上一级节点,延另一节点又继续前进 例、八数码问题的深度优先搜索

第4章 图搜索技术----4.1 状态图搜索 广度优先搜索的特点：完备、解是最优解、效率 低。 2、深度优先搜索 在搜索的每一层，始终只扩展一个节点，不断地 向纵深前进，直到不能再前进时，才从当前节点 返回到上一级节点，延另一节点又继续前进。 例、八数码问题的深度优先搜索

第4章图搜索技术--41状态图搜索 深度优先搜索算法 步1把初始节点S放入OPEN表中; 步2若OPEN表为空,则搜索失败,退出 步3取OPEN表中前面第一个节点N放入 CLOSED表中 步4若目标节点S。=N,则搜索成功,结束; 步5若N不可扩展,则转步2 步6扩展N,将其所有子节点配上指向N的返回指针依次放 入OPEN表的首部,转步2 深度优先搜索策略的特点:不完备、找到的解不一定是最优 解

第4章 图搜索技术----4.1 状态图搜索 深度优先搜索算法： 步1 把初始节点S0放入OPEN表中； 步2 若OPEN表为空，则搜索失败，退出； 步3 取OPEN表中前面第一个节点N放入CLOSED表中； 步4 若目标节点Sg =N，则搜索成功，结束; 步5 若N不可扩展，则转步2。 步6 扩展N，将其所有子节点配上指向N的返回指针依次放 入OPEN表的首部，转步2。 深度优先搜索策略的特点：不完备、找到的解不一定是最优 解