第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表中的原指向父节点的指针，使其指向 新的父节点