首页 > 代码库 > 枚举算法
枚举算法
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.优缺点:
枚举法的优点:由于枚举算法一般是现实问题的“直译”,且是建立在考察大量状态、甚至是穷举所有状态的基础之上的,因此比较直观,易于理解,其算法的正确性也比较容易证明。
枚举法的缺点:枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价,因此效率比较低。
枚举算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。