搜索求解策略
2020-01-27 12:25:05 24 举报AI智能生成
搜索求解策略，概述搜索的概念及常见搜索策略的相关知识。
作者其他创作
大纲/内容
搜索的概念
搜索的基本问题
搜索过程是否一定 能找到解
当搜索过程找到解时是否一定是最佳解
搜索过程的时间和空间复杂性如何
搜索过程是否终止运行或是否陷入一个死循环
主要过程
从初始或目的状态出发，并作为当前状态
扫描操作算子集，并将适用当前状态的一些操作算子作用于上
面得到新的状态，并建立指向父结点的指针
面得到新的状态，并建立指向父结点的指针
检查所生成的新状态是否满足结束状态
满足，得到问题的解
不满足，将新状态作为当前状态，返回
第2步，继续搜索
第2步，继续搜索
搜索策略
数据驱动
从初始状态出发正向搜索
目的驱动
从目的状态出发逆向搜索
状态空间的搜索策略
状态空间表示法
(S,O,S0,G)
S状态集合
O操作算子
S0包含问题的初始状态
G若干具体状态
状态空间的图描述
有向图描述
图的结点表示问题状态
图的弧度表示状态之间的关系，即求解问题的步骤
盲目的图搜索策略
回溯策略
路径状态表
新的路径状态表
不可解状态表
宽度优先搜索策略
完备搜索，只要问题有解，就一定能找的到解，并且一定是最优解
缺点：盲目性太大，产生很多无用节点，搜索效率低
例题：八数码问题
深度优先搜索策略
找到的不一定是最优解，且由于深度的限制，可能会找不到解
例题：卒子穿阵问题
启发式图搜索策略
启发式策略
启发方法
使用该方法的搜索状态空间的算法
启发信息和估价函数
启发信息分类
陈述性启发性信息
过程性启发信息
控制性启发信息
f(n)=g(n)+h(n)
f(n):估价函数定义为从初始结点经过n结点
g(n):从初始状态到n结点的实际代价
h(n):从n结点到目的结点的最佳路径的估计代价
A搜索算法
定义
基于估价函数的加权启发式图搜索策略
步骤
1.把附有f(S0)的初始结点S0放入open表
2.若open表为空，则搜索失败退出
3.移出open表中第一个结点N放入closed表中，并顺序编号n
4.若目标结点把附有f(S0)的初始Sg=N，则搜索成功，结束
5.若N不可扩展，则转步骤2
6.扩展N，生成一组附有f(x)的子结点，对这组子结点作如下处理
A*搜索算法及其特性分析
A*算法：h(n)<=h*(n)
h*(n)为状态n到目的状态的最优路径的代价
h(n)定义为A搜索算法的启发函数
特性
可采纳性
单调性
信息性
0 条评论
下一页
