搜索算法
2
搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。
3
搜索常用的方法
枚举
状态空间搜索算法
深度优先搜索
广度优先搜索
双向广度优先搜索
回溯法
分枝限界法
A*算法
4
枚举法
要求生成问题域中的每一个解元素,选出其中满足问题约束的元素,然后再找出一个期望元素(如使目标函数达到最值的元素)
5
从可能的集合中一一枚举各元素,用题目给定的检验条件判定哪些是无用的,哪些是有用的。能使命题成立者,即为问题的解。
6
(1)建立问题的数学模型,确定问题的可能解的集合(可能解的空间)。
(2)逐一枚举可能解集合中的元素,验证是否是问题的解。
7
For each s in S //S是问题所有可能解的集合
If s is a solution then
begin
write(s);
exit;
end;
8
旅行商问题
要求找出一条n个给定城市间的最短路径,使到在回到出发的城市之前,对每个城市都只访问一次
用图的顶点代表城市,边的权重表示城市间的距离,这个问题可以转化为求一个图的最短哈密顿回路
9
哈密顿回路可以定义为n+1个相邻节点vi0,…,vin-1,vi0的一个序列
可以通过生成n-1个中间城市的组合来得到所有的旅行路线,计算这些路线的长度,然后求得最短的线路
算法时间复杂度 O(n!)
10
对于枚举算法,程序优化的主要考虑方向是:通过加强约束条件,缩小可能解的集合的规模。
[计算机软件及应用]搜索算法1 来自淘豆网m.daumloan.com转载请标明出处.
