算法设计与分析

SearchStrategy

1.搜索基本原理

与分治策略、动态规划和贪心算法相比,搜索技术不需要进行子问题划分,也没有直接的递推公式的求解,它是在状态空间图中一步一步地探索问题的解。

状态空间搜索是一种通用的问题求解方法,它首先把问题描述转换为一个状态空间图,然后设计特定的图遍历方法在状态空间中搜索问题的解。需要注意的是,为了提高搜索的效率,在遍历状态空间时需要添加优化技术,比如剪枝策略用于尽可能避免不必要的无效搜索,启发式信息用来加速朝目标状态逼近的速度。

简单地说,搜索 = 图遍历(枚举) + 优化策略

2.搜索算法设计步骤

搜索算法一般包括以下两个步骤:

(1)定义问题的状态空间图。
(2)确定状态空间图的搜索方式,并用剪枝策略避免无效搜索。

典型的搜索策略包括:

1)深度优先搜索
2)宽度优先搜索
3)回溯法;
4)分支限界法;
5)启发式搜索。

3.典型例题

1)装载问题

2)求和组合

3)骑士骑马

4)八数码问题


4.课件下载

Algorithm-7-Search Methods.pptx

Adversarial-1

Adversarial-2