算法设计与分析

枚举算法

1.枚举算法基本原理

“大道至简”,枚举算法是最朴素和最简单的一种算法思维。

枚举算法,也称之为穷举算法,就是按照问题本身的性质,一一列举出该问题所有可能的解,并在逐一列举的过程中,检验每个可能解是否是问题的真正解。若是,则采纳这个解;否则抛弃它。在列举的过程中,既不能遗漏也不能重复。如果有遗漏,则可能造成算法求解结果不正确;如果重复比较多,则将显著降低算法执行效率。

枚举算法具有以下三个突出的特点:

解的高准确性和全面性,因为枚举算法会检验问题的每一种可能情况,所以,只要时间足够,枚举算法求解的答案肯定是正确的(比如说最优化问题,枚举算法求解出来的解能保证是最优解);同时,枚举算法还能方便地求解出问题的所有解。 实现简单,枚举算法常常通过循环来逐一列举和验证可能解,用高级程序设计语言来表达的话,枚举算法一般由多重for循环语句组成,程序逻辑结构清晰简单。 效率提升空间比较大,枚举算法可直接用于求解规模比较小的问题和问题实例,但是,当问题规模比较大时,枚举算法的效率通常比较低,需要进一步优化。

枚举算法是计算机问题求解最常用的方法之一,常用来解决那些通过公式推导、规则演绎的方法不能解决的问题,也用于解决一些规模比较小的问题。枚举算法求解问题的过程可以分为以下三步(“枚举三步”):

确定枚举对象。枚举对象是枚举算法的关键要素,一般需要若干参数来描述,每个参数包括自身的物理含义和取值范围等要素,这些参数能表示问题以及问题解的本质特征。一般地,这些参数之间相互独立,而且,参数数目越少,问题解的枚举空间的维度也越小;每个参数的取值范围越小,问题解的搜索空间也越小。本质上,确定和刻画枚举对象的过程就是一个数学建模的过程。

逐一列举可能解。根据枚举对象的参数构造循环,一一列举其表达式的每一种取值情况。

逐一验证可能解。根据问题解的要求,一一验证枚举对象表达式的每一个取值,如果满足条件,则采纳它;否则,抛弃之。


2.典型例题

直线穿越点

一元三次方程求解

绳子的长度

河里面的石头


3.课件下载

Algorithm-3-Brute force.pptx