要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量用来描述问题的对象,程序结构、函数和语句用来描述问题的算法。算法和数据结构是程序的两个重要方面。

算法是问题求解过程的精确描述,一个算法由有限条可完全机械执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止,或终止于给出问题的解,或终止于指出问题对此输入数据无解。

通常求解一个问题可能会有多种算法可供选择,选择的主要标准是算法的正确性和可靠性,简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。

算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等。另外,为了以更简洁的形式设计和描述算法,在算法设计时又常常采用递归技术,用递归描述算法。

(1)迭代法

迭代法也称辗转法,是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法(或者称为一次解法),即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法,它利用计算机运算速度快、适合重复性操作的特点,让计算机对一组指令(或步骤)进行重复执行,在每次执行这组指令(或步骤)时,都从变量的原值推出它的一个新值,迭代法又分为精确迭代和近似迭代。比较典型的迭代法如“二分法”和“牛顿迭代法”属于近似迭代法。

(2)穷举搜索法

穷举搜索法是编程中常用的一种方法,通常在找不到解决问题的规律时,对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从中找出那些符合要求的候选解作为问题的解。穷举式搜索算法包括广度优先搜索、深度优先搜索、有界深度优先搜索和一致代价搜索。

(3)递推法

递推算法是一种简单的算法,即通过已知条件,利用特定关系得出中间推论,直至得到结果的算法。递推算法分为顺推和逆推两种。

设要求问题规模为N的解,当N=1时,解或为已知,或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质,即当得到问题规模为i-1的解后,由问题的递推性质,能从已求得的规模为1,2,…,i-1的一系列解,构造出问题规模为I的解。这样,程序可从i=0或i=1出发,重复地,由已知至i-1规模的解,递推获得规模为i的解,直至得到规模为N的解。

(4)递归法

递归是设计和描述算法的一种有力的工具,它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。

能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。

(5)回溯法

回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模以继续试探的过程称为向前试探。

(6)贪婪法

贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不需要回溯。

例如平时购物找钱时,为使找回的零钱的硬币数最少,不考虑找零钱的所有各种组合方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值的币种,当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1,5和11单位的硬币,而希望找回总额为15单位的硬币。按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解应是3个5单位面值的硬币。

(7)分治法(www.daowen.com)

1)分治法的基本思想

任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算;n=2时,只要作一次比较即可排好序;n=3时只要作3次比较即可。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。

分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

如果原问题可分割成k个子问题(1<k≤n),且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。

2)分治法的适用条件

分治法所能解决的问题一般具有以下几个特征:

①该问题的规模缩小到一定的程度就可以容易地解决。

②该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。

③利用该问题分解出的子问题的解可以合并为该问题的解。

④该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪婪法或动态规划法。第四条特征涉及分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。

3)分治法的基本步骤

分治法在每一层递归上都有3个步骤:

①分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;

②解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;

③合并:将各个子问题的解合并为原问题的解。

(8)动态规划法

经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题。简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。

为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。