算法设计与分析课程论文

算法设计与分析课程论文

1．引言

算法设计与分析是数据结构的有力补充，从中可以了解到算法设计的奥妙以及对数据结构中的数据存储结构更深层次的运用。计算机算法设计与分析是面向设计的、处于核心地位的一门学科。算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。算法设计是一件非常困难的工作，常用的算法设计方法有：分治法、贪心方法、动态规划、回溯法、分枝－限界法、基本检索与周游方法、遗传算法等。

本文主要对算法设计与分析中的递归算法以及动态规划算法进行了总结、分析以及对具体问题的编程实现。

2．递归算法分析

2.1递归算法简介与特点

递归就是在函数或子过程的内部，直接或间接地调用自己的算法；递归算法是从下往上进行思维，需要对问题有全局的了解；在使用递归算法时，必须至少测试一个可以终止递归的条件，并且还必须对在合理的递归调用次数内未满足此类条件的情况进行处理，如果没有一个在正常情况下可以满足的条件，则过程将陷入执行无限循环的高度危险之中；递归算法的描述非常简洁而易于理解，但因重复计算和较大的堆栈消耗使递归算法的解题的运行效率较低；并不是所有的语言都支持递归，在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，递归次数过多容易造成栈溢出等不利编程的因素，所以一般不提倡用递归算法设计程序。

2.2递归过程

递归过程是直接调用自己或通过一系列的过程调用语句间接调用自己的过程。在一个过程的运行期间调用另一个过程时，在执行被调用过程之前，系统要先把所有的实在参数返回地址等信息传递给被调用的过程保存，为被调用过程的局部变量分配存储空间，将控制转移到被调用入口。接下来从被调过程返回调用过程要保存被调用过程的计算结果，释放被调用过程的数据区，依照被调过程保存的返回地址将控制转移到调用过程。该过程服从后调用先返回的原则。

2.3递归算法的优缺点

递归算法易于理解，结构清晰，所编写的代码简洁精练，可读性好，有利于代码的维护。然而递归算法的效率却较低，占用较大的内存开销，消耗更多的系统堆栈，算法的空间复杂度大，故可以实现的深度是有限制的。而且要考虑函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。

2.4递归算法的适用范围

由于递归算法的运行效率较低，堆栈容易溢出的特点， 递归算法适用于问题规模较小且那些不存在简明的数学模型以阐明问题的本质，或者存在数学模型，但是难于实现的问题，这样可以减少代码的复杂度。

递归算法所适用的问题一般有这样的特征：为求解规模为N的问题，设法先将它分解为规模较小的子问题，然后从这些子问题的解构造出整个问题的解，并且这些子问题也能采用同样的分解和综合方法，分解成规模更小的子问题，并从这些更小的子问题的解构造出较大规模的问题的解，特别地，当规模N=1时，能直接得解。例如很多的数学函数是递归定义的（阶乘函数）、有的数据结构（广义表，二叉树）还有一类本身没有明显的递归结构但用递归求解更为简单的问题（汉诺塔问题，八皇后问题）。

2.5递归与递推的关系

①递推法是求解递归方程的基本方法，对于某些递归关系可由逐级递推求得递归方程的解。

②递归算法会引起一系列的函数调用，并且可能会有一系列的重复计算，所以当某个递归算法能较方便地转化成递推算法时，通常按递推算法编写程序。

③递归算法的执行过程分递推与回归两个阶段。在递推阶段，把较复杂的问题(规模为N)的求解推到比原问题简单一些的问题(规模小于N)的求解。在回归阶段，当获得最简单的情况后，逐级返回，依次获得稍复杂问题的解。递推是利用问题本身所具有的递推关系对问题求解的一种方法。采用递推法建立起来的算法一般要有重要的递推性质，即当求得问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列的解，构造出问题规模为i的解。若设这种问题的规模为N，当N=0或N=1时，解或为已知，或能很容易地求得。

2.6用递归算法来解决“骨头的诱惑”问题

2.6.1问题描述

一只小狗在一个古老的迷宫里找到一根骨头，当它叼起骨头时，迷宫开始颤

抖，它感觉到地面开始下沉。它才明白骨头是一个陷阱，它拼命地试着逃出迷宫。

迷宫是一个N×M 大小的长方形，迷宫有一个门。刚开始门是关着的，并且这个门会在第T 秒钟开启，门只会开启很短的时间（少于一秒），因此小狗必须恰好在第T 秒达到门的位置。每秒钟，它可以向上、下、左或右移动一步到相邻的方格中。但一旦它移动到相邻的方格，这个方格开始下沉，而且会在下一秒消失。所以，它不能在一个方格中停留超过一秒，也不能回到经过的方格。

小狗能成功逃离吗？

2.6.2问题分析

小狗要在迷宫中到处搜寻可以逃离道路，如果找到则成功逃离，如果找不到则会被困住。

此骨头的诱惑问题可以用典型的递归与回溯方法进行求解。对问题进行建模并用非形式化语言描述如下：

① 递归搜索阶段：给定小狗当前位置，按照一定的顺序对下一步的走向进行深度递归搜索，算法需要保存现场。

② 回溯恢复阶段：当某条路径的终点并不是出口时，算法需要回退，这就恢复现场，一边从另一个方向进行搜索。

③ 结束条件：当搜索了所有的路径，让没有找到出口，则结束算法，此结果代表没有出路；当找到一个出口，同样结束算法，此结果代表找到出路，递归路径即为小狗逃离路径。

2.6.3程序设计

C语言实现的主要代码如下：

int fun(int si,int sj,int time)

{

int i;

int g,h;

if(si==di && sj==dj && time==t)

return 1;

for(i=0; i

g = si+move[i][0];

h = sj+move[i][1];

if(maze[g][h] == '.') {

maze[g][h] = 'X'; // 走过之后，设置为墙壁

if(fun(g,h,time+1)) // 递归下一分支是否有通路

return 1;

maze[g][h] = '.'; // 回溯，恢复现场

}

}

return 0;

}

3．动态规划分析

3.1动态规划简介与特点

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

3.2动态规划基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

3.3适合动态规划解决的问题

① 具有最优子结构性，即原问题的最优解包含子问题的最优解。

② 子问题重叠性，也就是说子问题之间不是独立的，一个子问题在下一阶段决 策中可能被多次使用到。对有分解过程的子问题还表现在：自顶向下分解问题时，每次产生的子问题并不总是新问题，有些子问题会反复出现多次。

3.4算法设计步骤

① 找出最优解的性质，并刻划其结构特征。

② 递归地定义最优值。

③ 以自底向上的方式计算出最优值。

④ 根据计算最优值时得到的信息，构造最优解。

3.5用动态规划来解决“0/1背包”问题

3.5.1问题描述

给定 n 种物品和 1 个背包。物品 i 的重量是 wi，其价值为 vi，背包的容量为 C。问应如何装入背包中的物品，使得装入背包中物品的总价值最大？ 在选择装入背包的物品时，对每种物品 i 只有两种选择，即装入背包、不装入背包。不能将物品 i 装入背包多次，也不能只装入部分的物品 i。该问题称为 0/1 背包问题。

3.5.2问题分析

令V(i,j)表示在前i(1

(1) V(i,0)=V(0,j)=0

(2) V(i,j)=V(i-1,j) j

V(i,j)=max{V(i-1,j) ,V(i-1,j-wi)+vi) } j>wi

(1)式表明：如果第i个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；

(2)式表明：如果第i个物品的重量小于背包的容量，则会有一下两种情况：

(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi;

(b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。

显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最

优解。

3.5.3程序设计

C语言实现的主要代码如下：

int KnapSack(int n,int w[],int v[],int x[],int C)

{

} return V[n-1][C]; int i,j; for(i=0; i=0; i--) { } printf(

4．总结

递归和动态规划是算法设计中的重要方法，它们涉及面很广泛，本文只是对其进行了初步探讨，还有很多更加深入的东西等着大家去深入研究。作为算法设计的经典方法，它们并不会随着时间的流逝而丧失意义，相反，它对我们的算法设计研究提供了重要的思路以及指导。

参考文献

[1] 余祥宣，崔国华，邹海明.计算机算法基础[M].武汉：华中科技大学出版社，2003.

[2] 吕国英，任瑞征，钱宇华.算法设计与分析：清华大学出版社.

[3] 应莉 0-1背包问题及其算法 计算机与现代化 （2009）06-0024-03.