首页 > 代码库 > 枚举算法

枚举算法

1.枚举法的基本思想

根据实际问题设计多重循环,一一枚举所有可能的状态,并用问题给定的约束条件检验哪些状态是需要的,哪些状态是不需要的。能使命题成立的状态,即为其解。虽然枚举法本质上属于搜索策略,但是它与后面讲的回溯法或宽度优先搜索有所不同。

2.枚举条件

①可预先确定每个状态的元素个数n。如百钱买百鸡问题,3文钱一只鸡的状态元素个数可预先确定;

②可预先确定每个状态元素a1,a2,…,an的值域。

3.框架结构

设a11为状态元素ai的最小值;aik为状态元素ai的最大值(1<=i<=n),即状态元素a1,a2,…an的值域分别为a11<=a1<=a1k, a21<=a2<=a2k,……ai1<=ai<=aik,…
    an1<=an<=ank。
   for(a1=a11;a1<=a1k;a1++)
      for(a2=a21;a2<=a2k;a2++)
         .....
        for(ai=ai1;ai<=aik;ai++)
             .....
            for(an=an1;an<=ank;an++)
                 if(状态(a1,...,ai...,an)满足检验条件)输出问题的解;

4.优缺点

枚举法的优点:由于枚举算法一般是现实问题的“直译”,且是建立在考察大量状态、甚至是穷举所有状态的基础之上的,因此比较直观,易于理解,其算法的正确性也比较容易证明。
枚举法的缺点:枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。

枚举算法