概要

枚举方法也是一种搜索算法,即对问题的所有可能解的状态集合进行一次扫描或遍历。

在具体的程序实现过程中,可以通过循环和条件判断语句来完成。 枚举法常用于解决“是否存在”或“有多少种可能”等类型的问题。

例如,求解不定方程的问题就可以采用列举法。 虽然枚举法本质上属于搜索策略,但是它与回溯法有所不同。

因为适用枚举法求解的问题必须满足两个条件:

⑴可预先确定每个状态的元素个数n;

⑵状态元素a1,a2,…,an的可能值为一个连续的值域。

枚举策略的基本思想

枚举法的特点是算法比较简单,在用枚举法设计算法时,重点注意优化,减少运算工作量。将与问题有关的知识条理化、完备化、系统化,从中找出规律,减少枚举量。

枚举方法的优化: 枚举算法的时间复杂度:状态总数*单个状态的耗时

主要优化方法

⑴ 减少状态总数 ⑵ 降低单个状态的考察代价

优化过程从以下几个方面考虑

⑴ 枚举对象的选取

⑵ 枚举方法的确定

⑶ 采用局部枚举或引进其他算法

最后修改: 2012年11月12日 星期一 11:02