算法:常用的基础算法:穷举、迭代、递归和回溯

穷举、迭代、递归和回溯这些算法属于“通用算法”,它们在解决许多问题中都有应用。

穷举

在有限的范围内,可以对所有的值都进行试验和判断,从而找到满足条件的值
穷举的基本模式

  • for(;;){ if(); }
    时间复杂度很高。

迭代

多次利用同一公式进行计算,每次将计算的结果再代入公式进行计算,从而逐步逼近精确解
迭代的基本模式

  • while() { x = f(x); }

利用迭代算法解决问题,需要做好以下三个方面的工作:

确定变量

在可以用迭代算法解决的问题中,至少存在一个直接或间接地不断由旧值递推出新值的变量,这个变量就是迭代变量。

建立关系式

所谓迭代关系式,指如何从变量的前一个值推出其下一个值的公式(或关系)。迭代关系式的建立是解决迭代问题的关键,通常可以使用递推或倒推的方法来完成。

过程控制

在什么时候结束迭代过程?这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况:一种是所需的迭代次数是个确定的值,可以计算出来;另一种是所需的迭代次数无法确定。对于前一种情况,可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况,需要进一步分析出用来结束迭代过程的条件。

递归

递归(recursive)就是一个过程调用过程本身。在递归调用中,一个过程执行的某一步要用到它的上一步(或上几步)的结果
递归的基本模式

  • f(n){ f(n-1); }
    边界条件与递归方程是递归函数的二个要素。

回溯

回溯法也叫试探回溯法,先选择某一可能的线索进行试探,每一步试探都有多种方式,将每一方式都一一试探,如果不符合条件就返回纠正,反复进行这种试探再返回纠正,直到得出全部符合条件的答案或是问题无解为止。
回溯的基本模式

  • x++; if(…) x--;

对回溯的算法优化
为了避免生成那些不可能产生最佳解的问题状态,要不断地利用限界函数(bounding function)来处死那些实际上不可能产生所需解的活结点,以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法;在将来的文章中详细说明。