算法设计基本方法与策略基础资料文件与下载

算法设计基本方法与策略基础

本部分概括地介绍算法设计的基本方法和策略，使学生对常用的算法设计方法和策略有一个基本的认识，便于在以后的学习中对算法进行归类整理和梳理，并使用这些基本的方法和策略来设计自己的算法。

一、算法设计的方法

1. 递推法

递推法是利用问题本身所具有的一种递推关系求解问题的一种方法。它把问题求解分成若干步，找出相邻几步的关系，从而达到求解问题的目的。

具有如下性质的问题可以采用递推法：当得到问题规模为i-1的解后，由问题的递推性质，能构造出问题规模为i的解。因此，程序可以从i=0或i=1出发，由已知i-1规模的解，通过递推，获得问题规模为i的解，直至得到问题规模为n的解。

【例1】使用递推策略计算n!（假设n<=10）

分析：计算n!的问题可以写成递推公式的形式：n! =(n-1)!*n。可以看到，n!是前一项的阶乘再乘以问题规模n。所以可以从1的阶乘出发，分别求出2!、3!、......、(n-1)!，最后求出n!。

参考程序如下：

#include <iostream>

using namespace std;

int fac(int);

int main()

{

int n, c;

cout<<"请输入n的值：";

cin>>n;

c = fac(n);

cout<<n<<"的阶乘为"<<c<<endl;

return 0;

}

int fac(int n)

{

int result=1;

for(int i=2;i<=n;i++)

result=result*i;

return result;

}

提示：递推法是一种简单有效的方法，一般用这种方法编写的程序执行效率很高，可以解决具有递推性质、个数不多、个数为定数的问题。

2.递归法

递归策略是利用函数直接或间接地调用自身来完成某个计算过程。

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

在编写程序解决一个问题时，往往将这个问题分解成若干个子问题，对每个子问题编写相应的函数，最后通过调用这些函数来解决整个问题。

递归算法具有代码简洁、可读性强的优点。递归算法的缺点是运行效率较低，递归调用会由于需要频繁保存运行状态而消耗额外的时间、占用额外的空间，递归次数过多容易造成栈溢出等。

在使用递归策略时，要注意两个条件：

① 确定递归公式：函数里直接或间接调用自身；

② 确定终止条件：必须有一个明确的递归结束条件，即递归出口。

递归法一般用于解决三类问题：

① 数据的定义是按递归定义的：例如Fibonacci数列、n！等；

② 问题解法按递归算法实现：例如八皇后问题、背包问题等；

③ 数据的结构形式是按递归定义的：如树的遍历、图的搜索等。

【例2】使用递归策略计算n!（假设n<=10）。

分析：对于计算n!的问题，可以将其分解为：n! = n*(n-1)!。可以看到，分解之后的子问题(n-1)!与原问题n!的计算方法完全一样，只是规模有所减小。同样，(n-1)!这个子问题又可以进一步分解为(n-1)*(n-2)!，(n-2)!可以进一步分解为(n-2)*(n-3)!......，直到要计算1!时，直接返回1。

参考程序如下：

#include <iostream>

using namespace std;

int fac(int);

int main()

{

int n, c;

cout<<"请输入n的值：";

cin>>n;

c = fac(n);

cout<<n<<"的阶乘为"<<c<<endl;

return 0;

}

int fac(int n)

{

if (n == 1 || n == 0)

return 1;

else

return n*fac(n-1);

}

提示：任何可以用递推法解决的问题，都可以很方便的利用递归法解决；反之，并非所有能用递归法解决的问题都能用递推法解决。

3.穷举法

穷举搜索法也称穷举法或搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。

【例3】求所有的“水仙花数”。

“水仙花数”是指一个三位整数，其各位数字立方和等于该数本身。例如，153=1³+5³+3³，所以153是水仙花数。

分析：因为“水仙花数”是三位整数，所以一定都在100～999范围内。依次搜索100～999范围内的所有整数，找到水仙花数。搜索方法利用三重循环，外循环变量i控制百位数字从1变化到9，中层循环变量j控制十位数字从0变化到9，内循环变量k控制个位数字从0变化到9。

参考程序如下：

#include <iostream>

using namespace std;

int main()

{

int i, j, k, m, n;

for(i=1; i<=9; i++) //外循环，搜索百位

for(j=0; j<=9; j++) //中层循环，搜索十位

for(k=0; k<=9; k++) //内循环，搜索个位

{

m=i*i*i+j*j*j+k*k*k;

n=100*i+10*j+k;

if(m==n)

cout<<m<<endl; //输出找到的水仙花数

}

return 0;

}

提示：穷举法的核心是要采用某种方法来确定所有的候选解。

4.迭代法

迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法。利用迭代法需要解决三个问题：

①确定迭代变量

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

②建立迭代关系式

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

③对迭代过程进行控制

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

【例4】用牛顿迭代法求一元方程2x³–4x²+3x–6=0在 x=1.5 附近的根，要求精度为10^-6。

牛顿迭代法算法描述：先给根一个初值x₁，过x₁作垂线交曲线于A点，再过A点作切线交x轴于x₂，曲线在A点的斜率为：

                                                                                  f’(x₁) = f(x₁)/(x₁–x₂)

由此式得：

                                                                                 x₂= x₁– f(x₁)/f’(x₁)

重复上述过程，一次比一次接近方程的根。当两次求得的根相差很小时，就认为 x_n+1 是方程的近似根。如图1-6所示，于是得到牛顿迭代公式：

                                                                                x_n+1= x_n –f(x_n)/f’(x_n)

图1-6 牛顿迭代法示意图

本例中，用f表示 f(x_n)，用 f1表示 f’(x_n)，得：

                                                                           f=2x_n³–4x_n²+3x_n–6=((2x_n–4)x_n+3)x_n–6

                                                                           f1=6x_n²–8x_n+3=(6x_n–8)x_n+3

完整的C++程序如下：

#include<iostream>

#include<cmath>

using namespace std;

int main()

{  

float xn, xn1, f, f1;

cout<<"请输入x的初值：";

cin>>xn1;

do

{

xn=xn1;

f=((2*xn-4)*xn+3)*xn-6;

f1=(6*xn-8)*xn+3;

xn1=xn-f/f1;

} while(fabs(xn1-xn)>=1e-6);

cout<<"方程的一个根为："<<xn1<<endl;

return 0;

}

在计算机科学中，还有一些很重要的、被广泛采用的设计算法的策略，包括分治策略、贪心策略、动态规划策略、回溯策略和分枝定界策略。下面简单介绍这些策略的基本思想，

二、分治策略

分治策略的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题，然后分别求解这些子问题，最后把各子结果合并得到整个问题的解。分解的子问题通常与原问题相似，所以可以递归地使用分治策略来求解。

【例5】用分治策略求解最大值和最小值问题。

假设有n个数，找出其中的最大值和最小值。

求解该问题最基本的算法描述如下：

#include<iostream>

using namespace std;

Template<class T>

void MaxMin(T a[],int n,T max,T min)

{

max=min=0;

for (int i=0;i<n;i++)

{

if(a[max]<a[i])

max=i;

if(a[min]>a[i])

min=i;

}

}

分析上面算法，是通过n-1次比较找出最大值或最小值，共需要2n-2次比较运算。

下面采用分治策略对这个问题进行求解。当n≤2时，识别出最大值和最小值只需要一次比较就可以解决问题。当n>2时，分治策略的解题步骤如下：

第一步，将这n个数平分成两部分A和B。

第二步，分别找出A和B中的最大值和最小值，设A中的最大值和最小值为MaxA和MinA，B中的最大值和最小值为MaxB和MinB。

第三步，比较MaxA和MaxB找出n个数中的最大值，比较MinA和MinB找出n个数中的最小值。

采用分治策略求解该问题的算法描述如下：

#include<iostream>

using namespace std;

Template<class T>

void MaxMin(T a[],int n,T max,T min)

{

if(n==2)

{

if(a[0]>a[1])

{

max=a[0];

min=a[1];

}

else

{

max=a[1];

min=a[0];

}

}

else

{

//把a划分成长为2/n的两部分A和B

MaxMin(A,n/2,maxA,minA);

MaxMin(B,n/2,maxB,minB);

max=Max(maxA,maxB);

min=Min(minA,minB);

}

}

  下面分析递归策略求解最大值和最小值问题的时间代价。算法的时间代价可表示为：

                   0                          n=1

 T(n)=  {      1                          n=2

                   T(n/2)+T(n/2)+2   n>2

其中，T(n)=2T(n/2)+2称为递归方程，直接迭代

  T(n)=2T(n/2)+2

=2(2T(n/4)+2)+2

=2 ^k-1T(2)+

=2 ^k-1+2 ^k-2

=3n/2-2

采用分治策略的算法比直接比较法的比较次数约减少1/3。可见，当n比较大时，分治策略的算法具有明显的性能优势。

三、贪心策略

贪心策略的基本思想是把一个整体最优问题分解为一系列的最优选择问题，决策一旦做出，就不能再更改。它是通过若干次的贪心选择而得出最优解(或较优解)的一种解题策略。

【例6】用贪心策略求解找零钱问题。

对于自动售货机要找给顾客零钱，并且希望付出的货币的数量最少。对于这个找零钱问题，可以使用穷举法编写程序，穷举在所有的可行解中，找出最优解。但一般采用的方法是采用贪心策略，即尽量给顾客大面值的货币，同时希望付出的货币数量最少。事实上，普通人在付款时都会自然而然地采用贪心策略。

已知应付款额和现有货币的面值，应付款额放在int v中；假设有9种面值的货币(100元、20元、10元、5元、1元、1角、5分、2分、1分)，存在在数组m中，即：int m[9] ={10000,2000,1000,500,100,10,5,2,1}。

采用贪心策略求解找零钱问题的算法描述如下：

#include<iostream>

using namespace std;

void pay(int m[],int v)

{

int i,r,n[9];

for (i=0;i<9;i++)

n[i]=0;

r=v;

i=0;

while(r>0)

{

if(m[i]<r)

{

r=r-m[i];

n[i]++;

}

else

i++;

}

for (i=0;i<9;i++)

cout<<”支付”<<m[i]/100.0<<”元的货币”<<n[i]<<”个”；

}

在找零钱这个问题上，贪心策略否能得到最优解与货币面值的集合有关。例如：要付8元钱，如果货币面值集合为5元、4元和1元，按贪心策略付出的货币是一个5元和3个1元共4个货币，而最优解是两个4元货币。如果货币面值集合为5元、2元和1元，按贪心策略付出的货币是一个5元、2个元和一个1元共3个货币，此时就是最优解。

提示：如果一个问题的最优解只能通过穷举法得到，使用贪心策略是寻找问题近似最优解的一个较好办法，它省去了为查找最优解而去穷举所有可能解而耗费的大量时间。在有些问题中，近似最优解是可以接受的。

四、动态规划策略

动态规划策略与贪心策略类似，将一个问题划分为重复的子问题，通过对相同子问题的求解来解决较大问题，即将一个问题的解决方案视为一系列决策的结果。不同的是，在贪心策略中，每采用一次贪心准则便做出一个不可撤回的决策，可能得不到问题的最优解。而在动态规划中，处理要按照某种规则进行选择，还要考察每个最优决策序列中是否包含一个最优子序列，目的是得到问题的最优解。

【例7】用递归法求Fibonacci数列中第n个数。

用递归法求Fibonacci数列的算法描述如下：

int fib(int n)

{

if（n==1 || n=2）

return 1;

else

return fib(n-1) +fin(n-2);

}

在计算Fibonacci数列过程中，fib函数调用关系如图1所示。

采用递归算法求解，程序看起来非常简单。但当问题的规模n比较大时，计算量却非常大。假设n=6，fib函数被调用了15次。在调用fib(6)时，同一值会被重复计算多次，其中，fib(4)被调用2次，fib(3)被调用3次，fib(2)被调用5次，fib(1)被调用3次。在更大规模的例子中，还有更多fib的值被重复计算，将消耗指数级时间。

动态规划策略的基本思想是如果能够保存已解决的子问题的答案，就可以避免大量重复计算，当要解决相同的子问题时，重用已保存的结果即可，从而得到多项式时间算法。

动态规划通常采用以下两种方式之一：

①自下而上：先行求解所有可能用到的子问题，然后用其构造更大问题的解。该方法在节省堆栈空间和减少函数调用数量上略有优势，但有时想找出给定问题的所有子问题并不那么直观。

②自顶向下：将问题划分为若干子问题，求解这些子问题并保存结果以免重复计算。该方法将递归和缓存结合在一起。

仍以计算Fibonacci数列问题为例，采用自下而上的方法。先计算较小的fib，然后基于其计算更大的fib。这种方法只花费线性（O(n)）时间代价，因为它包含一个n-1次的循环。而且，这一方法只需要常数（O(1)）的空间。下面是采用动态规划策略自下而上的方法对fib()函数进行的改进。

int fib(int n)

{

int i,f1=f2=1;

for(i=3;i<=n;i++)

{

f=f2;

f2=f+f1;

f1=f;

}

}

自顶向下的递归方法也被称为备忘录（memorization）方法。下面采用自顶而下的方法来改进计算Fibonacci数列的函数。在程序中先设置一个备忘录，每计算出一个新的子问题的解时，就保存起来。到递归调用函数时，首先判断是否已计算过，如果已计算过，直接取出保存结果，否则调用函数计算该子问题。这种方法只需O(n)的时间，同时需要O(n)的空间来储存子问题的计算结果。

下面是采用动态规划策略自顶而下的方法对fib()函数进行的改进。

int fib(int n)

{

int memo[n+1];

for(int i=1;i++;i<n+1)

memo[i]=0;

int f1,f2;

if（n==1 || n=2）

return 1;

if(memo[n-2]==0)

f1=fib(n-2);

else

f1=memo[n-2];

if(memo[n-1]==0)

f2=fib(n-1);

else

f2=memo[n-1];

memo[n]=f1+f2;

return f1+f2;

}

这个递归程序当n=6时，只需要调用4次fib函数，远远小于前面的15次调用，重复调用部分由对数组memo[]的判断与读取代替。可见，当n较大时，算法的效率会有非常明显的提高。

五、回溯策略

穷举法使用的手段就是搜索，列出问题的所有候选解，然后依次检查他们直到找到问题的解。当候选解数量有限并且能够通过检查所有候选解得到问题的解时，穷举法是可行的。但实际问题中候选解的数量往往很大，即使使用最快的计算机也不能在可接受的时间内得到问题的解。回溯策略和下一小节的分支定界策略就是既带有系统性又带有跳跃性的两种搜索控制策略，是对候选解进行系统搜索并使问题的求解时间大大减少的方法，他们可以避免对很大的候选解集合进行穷举式的盲目搜索，同时还能保证可以找到问题的解。所以，回溯策略和分支定界策略一般用来求解规模很大的问题。

回溯策略（回溯法）也叫试探法，它的基本思想是：在一些问题求解进程中，先选择某一种可能情况向前探索，当发现所选用的试探性操作不是最佳选择，需退回一步（回溯），重新选择继续进行试探，直到找到问题的解或证明问题无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前探索前进。如果碰到死胡同，说明前进方向已无路可走，这时，首先看其他方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。

【例8】输出自然数1到n所有不重复的排列，即n的全排列。

图2是用一个树型结构来形象地描述n（此处n=3）个自然数的所有候选解的情况，该树被称为解空间树。第1层斜线上的值为排列在第1个位置上的自然数，第2层斜线上的取值为排列在第2个位置上的自然数，第3层斜线上的取值排列在第3个位置上的自然数。从根结点到叶子结点的连线上的数值的排列就是一个候选解，如叶子结点4，对应的候选解是111，叶子结点10对应的候选解是123。如果用穷举法，需要穷举所有的候选解，即搜索整个解空间树上的每一个解，判断其是否满足条件自然数排列的条件（不能有重复），找到问题的解。

图2 n的自然数排列问题的解空间数

提示：解空间树是虚拟的，并不需要在算法开始运行时构造一棵真正的解空间树。

下面，用回溯策略求解n个自然数的排列问题。在解空间树上进行系统地搜索向下时，当发现不可能的结点时，就停止这一步搜索，退回一步，重新选择一个结点继续搜索。例如，当前搜索处于结点2，选择（试探）结点3，发现对应的排列在第2个位置上的数是1，而1已经使用过。所以，不再对结点3及以下结点进行搜索，而是退回到结点2，重新选择（试探）一个新的结点7继续进行搜索操作。

假设m_n用来存放自然数n，数组m_p用来存放排列的自然数，数组m_used用来存放是自然数否被使用过，采用回溯策略的compute函数求解n个自然数的排列问题步骤如下：

①在1～n中选择一个数，只要这个数不重复，就选中放入m_p数组中，并在m_used数组中作一个被使用的标记(将数组元素置1);

②如果已经选择了n个自然数，则找到了一个解，将该解输出；

③如果所选中的数已被使用（作了标记），就另选一个数进行试探;

④如果未作标记的数都已试探完毕，那就取消最后那个数的使用标记，退回一步，并取消这一步的选数标记，换下一个数继续进行试探，即转步骤①;

⑤完成全部数据的试探，结束。

完整的C++程序如下：

//permutation.h

#ifndef PERMUTATION

#define PERMUTATION

class permutation

{

public:

permutation(int n);

void compute(int count); //计算所有n个自然数的排列并输出

~permutation();

private:

int m_n; //自然数n；

int *m_p; //存放排列结果

int *m_used; //存放使用过的标记

};

#endif

//permutation.cpp

#include<iostream>

#include"permutation.h"

using namespace std;

permutation::permutation(int n)

{

m_n=n;

m_p=new int[n+1]; //为了程序易读性，m_p[0]空闲

m_used=new int[n+1]; //为了程序易读性，m_used[0]空闲

for(int i=1;i<=n;i++) //初始化数组m_p和数组m_used

{

m_p[i]=0;

m_used[i]=0;

}

}

void permutation::compute(int count)

{

int i;

if (count==m_n+1) //已经选出了n个元素，输出这个排列*/

{

for (i=1; i<=m_n; i++)

cout<<m_p[i]<<" ";

cout<<endl;

return;

}

for (i=1; i<=m_n; i++) //发现第count个自然数

if (!m_used[i])

{

m_p[count] = i; //把它放置在排列中

m_used[i]++; //标记该元素已被使用

compute(count+1); //搜索第count+1个自然数

m_used[i]=0; //没有成功则恢复递归前的值

}

}

permutation::~permutation()

{

delete []m_p;

delete []m_used;

}

//Chap1-5.cpp

#include<iostream>

#include"permutation.h"

using namespace std;

int main()

{

int n;

cout<<"请输入n：";

cin>>n;

permutation p(n);

p.compute(1);

return 0;

}

图3是n（n=3）个自然数全排列问题一次执行过程的搜索路径示意图。有阴影的结点都是在试探过程中，发现相应的自然数已经使用过了，不需要再搜索他们下面的结点了。可见，当n=3时，n个自然数全排列问题比穷举法对候选解的搜索减少了1/3。

图3（n=3）个自然数全排列问题一次执行过程的搜索路径

提示：回溯策略是一种深度优先的搜索策略。所谓深度优先探索是指在解空间树上进行搜索时，是从根结点尽可能地向叶子结点的方向进行。还有一种广度优先搜索的策略，是指在解空间树上按层进行搜索。在图1-8中，用深度优先搜索，搜索的结点顺序是就是图中的结点号，如果进行广度优先搜索，搜索的结点顺序变为：1、2、15、28、3、7、11、16、20、24、29、33、37、4、5、6、8、9、10、12、13、14、17、18、19、21、22、23、25、26、27、30、31、32、34、35、36、38、39、40。

六、分支定界策略

分支定界策略也叫经常被称为分支限界策略，它的基本思想是：首先确定目标值的上下界，然后一边搜索一边剪掉解空间树的某些不可能产生最优解的分支，提高搜索效率。

分支限界策略与回溯策略都可以避免对很大的候选解集合进行检查，并且能够保证找到问题的解。但回溯策略求解目标是找出解空间树中所有满足约束条件的解，分支定界策略的求解目标与回溯策略有所不同，它是找出满足约束条件的一个解，或在满足约束条件的解中找出在某种含义下的最优解。回溯策略在搜索解空间树时采用的是深度优先方式，而分支定界策略采用的是广度优先方式。

常用的分支定界策略有两种方法，一种是队列式（FIFO）分支定界法，另一种是优先队列式分支定界法。