算法分析与设计

学习总结

题目：算法分析与设计学习总结

学 院 信息科学与工程学院 专 业 届 次 学生姓名 学 号

二○一三年一月十五日

算法分析与设计学习总结

本学期通过学习算法分析与设计课程，了解到：算法是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。

设计的算法要具有以下的特征才能有效的完成设计要求，算法的特征有：（1）有穷性。算法在执行有限步后必须终止。（2）确定性。算法的每一个步骤必须有确切的定义。（3）输入。一个算法有0个或多个输入，作为算法开始执行前的初始值，或初始状态。（4）输出。一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。（5）可行性。在有限时间内完成计算过程。

算法设计的整个过程，可以包含对问题需求的说明、数学模型的拟制、算法的详细设计、算法的正确性验证、算法的实现、算法分析、程序测试和文档资料的编制。算法可大致分为基本算法、数据结构的算法、数论与 代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法和并行算法。

经典的算法主要有：

1、 穷举搜索法

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

穷举算法特点是算法简单，但运行时所花费的时间量大。有些问题所列举书来的情况数目会大得惊人，就是用高速计算机运行，其等待运行结果的时间也将使人无法忍受。我们在用穷举算法解决问题是，应尽可能将明显不符合条件的情况排除在外，以尽快取得问题的解。

2、 迭代算法

迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或方程组）的过程，为实现这一过程所使用的方法统称为迭代法。迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行：

（1）选一个方程的近似根，赋给变量x0。

(2) 将x0的值保存于变量x1，然后计算g(x1),并将结果存于变量x0。

（3）当x0与x1的差的绝对值还小于指定的精度要求时，重复步骤（2）的计算。 若方程有根，并且用上述方法计算出来的近似根序列收敛，则按上述方法求得的x0就认为是方程的根。

3、 递推算法

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

4、 递归算法

递归算法是一种直接或间接的调用自身的算法。

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

模较大问题的解。特别的，当规模n=0或1时，能直接得解。

递归算法解决问题的特点有：

（1） 递归就是在过程或函数里调用自身

（2） 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口

（3） 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低

（4） 在递归调用的过程中系统为每一层的返回点、局部变量等开辟堆栈来存

储。

举例如下：

Fibonacci数列

int fib[50]; //采用数组保存中间结果

void fibonacci(int n)

{

fib[0] = 1;

fib[1] = 1;

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

fib[i] = fib[i-1]+fib[i-2];

}

5、 分治算法

分治算法是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单地直接求解，原问题的解即子问题解的合并。

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

分治策略的算法设计模式

Divide_and_Conquer（P）

{

if (|P|＜＝n0 ) return adhoc(P)；

divide P into smaller substances P1，P2，…，Pk；

for (i＝1; i＜＝k; k＋＋)

yi＝Divide-and-Conquer（Pi） //递归解决Pi

Return merge（y1，y2，…，yk） //合并子问题

}

6、 贪心算法

贪心算法也称贪婪算法。它在对问题求解时，总是做出在当前看来是最好的选择。它不从整体最优上考虑，所得出的仅是在某种意义上的局部最优解。

贪心算法的基本思路如下：

（1） 建立数学模型来描述问题

（2） 把求解的问题分成若干个子问题

（3） 对每一子问题求解，得到子问题的局部最优解

（4） 把子问题的局部最优解合成原来问题的一个解

贪心算法的一般流程:

Greedy(A)

{

S={ }; //初始解集合为空集

while (not solution(S)) //集合S没有构成问题的一个解

{

x = select(A); //在候选集合A中做贪心选择

if feasible(S, x) //判断集合S中加入x后的解是否可行

S = S+{x};

A = A-{x};

}

return S;

｝

（1）候选集合A：问题的最终解均取自于候选集合A。

（2）解集合S：解集合S不断扩展，直到构成满足问题的完整解。

（3）解决函数solution：检查解集合S是否构成问题的完整解。

（4）选择函数select：贪心策略，这是贪心算法的关键。

（5）可行函数feasible：解集合扩展后是否满足约束条件。

7、 动态规划算法

动态规划算法是一种在数学和计算机科学中用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。

动态规划算法的步骤

(1)找出最优解的性质，并刻画其结构特征；

(2)递归地定义最优值（写出动态规划方程）；

(3)以自底向上的方式计算出最优值；

(4)根据算法最优值时得到的信息，构造一个最优值。

动态规划算法的有效性依赖于问题本身所具有的两个重要的性质：最优子结构性质和子问题重叠性质。

(1)最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

(2)重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。

8、 回溯算法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。当探索到某一步时，发现原先的选择并不优或达不到目标，就回退一步重新选择，这种走不通就退回再走的技术成为回溯法，满足回溯条件的某个状态的点称为“回溯点”。迷宫问题算法所采用的就是回溯算法。

回溯算法解决问题的过程是先选择某一可能的线索进行试探，每一步试探都有多种方式，将每一方式都一一试探，如有问题就返回纠正，反复进行这种试探在反复纠正，直到得出全部符合条件的答案或是问题无解为止。由于回溯方法的本质是深度优先的方法在解的空间树中搜索，就要从堆栈中找到回溯的前一个位置继续试探。

装载问题回溯算法数据结构

#define NUM 100

int n; //集装箱的数量 int c; //轮船的载重量 int w[NUM]; //集装箱的重量数组 int x[NUM]; //当前搜索的解向量 int r; //剩余集装箱的重量 int cw; //当前轮船的载重量 int bestw; //当前最优载重量 int bestx[NUM]; //当前最优解 算法实现

//形参表示搜索第t层结点

void Backtrack(int t)

{

//到达叶子结点

if(t>n)

{

//更新最优解

if(cw>bestw)

{

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

bestx[i] = x[i];

bestw = cw;

}

return;

}

//更新剩余集装箱的重量

r -= w[t];

//搜索左子树

if(cw+w[t]<=c)

{

x[t] = 1;

cw += w[t];

Backtrack(t+1);

cw -= w[t];

}

//搜索右子树

if(cw+r>bestw)

{

x[t]=0;

Backtrack(t+1);

}

r += w[t]; //恢复状态

}

9、 分支限界算法

分支限界算法是一种在表示问题解空间的树上进行系统搜索的方法。该方法使用了广度

优先策略，同时采用最大收益（或最小损耗）策略来控制搜索的分支。

分支限界法的基本思想是对包含具有约束条件的最优化问题的所有可行解的解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。在每次分支后，对所有界限超出已知可行解的那些子集不再做进一步分支，解的许多子集可不予考虑，从而缩小了搜索的范围。这一过程一直进行到找出可行解的值不大于任何子集的界限为止。这种算法一般可以求得最优解。 分支结点的选择

从活结点表中选择下一个活结点作为新的扩展结点，分支限界算法通常可以分为两种形式：

1、 FIFO（First In First Out）分支限界算法

按照先进先出（FIFO）原则选择下一个活结点作为扩展结点，即从活结点表中取出结点的顺序与加入结点的顺序相同。

2、 最小耗费或最大收益分支限界算法

在这种情况下，每个结点都有一个耗费或收益。

根据问题的需要，可能是要查找一个具有最小耗费的解，或者是查找一个具有最大收益的解。

提高分支限界算法的效率

实现分支限界算法时，首先确定目标值的上下界，边搜索边减掉搜索树的某些分支，提高搜索效率。

在搜索时，绝大部分需要用到剪枝。“剪枝”是搜索算法中优化程序的一种基本方法，需要通过设计出合理的判断方法，以决定某一分支的取舍。

若我们把搜索的过程看成是对一棵树的遍历，那么剪枝就是将树中的一些“死结点”，不能到达最优解的枝条“剪”掉，以减少搜索的时间。

装载问题

装载问题分支限界算法的数据结构

#define NUM 100

int n; //集装箱的数量

int c; //轮船的载重量

int w[NUM]; //集装箱的重量数组

算法实现

int MaxLoading()

{

queue<int> Q;

Q.push(-1);

int i = 0;

int Ew = 0;

int bestw = 0;

int r = 0;

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

r += w[j];

//搜索子空间树

while (true)

{

//检查左子树

int wt = Ew+w[i];

if (wt<=c) //检查约束条件

{

if (wt>bestw) bestw = wt;

//加入活结点队列

if (i<n-1) Q.push(wt);

}

//检查右子树

//检查上界条件

if (Ew+r>bestw && i<n-1)

Q.push(Ew);

//从队列中取出活结点

Ew = Q.front();

Q.pop();

if (Ew==-1) //判断同层的尾部

{

if (Q.empty()) return bestw;

//同层结点尾部标志

Q.push(-1);

//从队列中取出活结点

Ew = Q.front();

Q.pop();

i++;

r -= w[i];

}

}

return bestw;

}

在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。

谢谢老师的指导，学习算法分析与设计使我对软件基础知识中算法的地位有了充分的了解,虽然课程结束了，但我依然还会继续学习算法分析与设计，以后我将充分利用所学到我实际的开发项目中。

 

第二篇：算法设计与分析书中概念总结

6递推步骤

7算法描述（盒图 PAD图之类的老师说看看但我不懂怎么考）

1. 算法的基本性质

（1） 目的性：算法有明确的目的，算法能够完成赋予它的功能。

（2） 分步性：算法为完成其复杂的功能，由一系列计算机可执行的步骤组成。

（3） 有序性：算法的步骤是有序的，不可能随意改变算法步骤的执行顺序。

（4） 有限性：算法是有限的指令顺序，算法所包含的步骤是有限的。

（5） 操作性：有意义的算法总是对某些对象进行操作，使其改变状态完成其功能。

2. 算法的考量

对于算法的分析和评估，一般考虑正确性、可维护性、可读性、运算量、占用存储空间等方面考虑。三条主要标准：

（1） 算法实现所耗费的时间。

（2） 算法实现所耗费的空间，其中主要考虑辅助存储空间。

（3） 算法易于理解、易于编码、易于调试。

3. 什么是迭代

迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。

4. 分治法求解的过程

分治法求解问题的过程是，将整个问题分解成若干个小问题后分而治之。如果分解得到的子问题相对来说还太大，则可反复使用分治策略将这些子问题分成更小的同类型子问题，直至产生方便求解的子问题，必要时逐步合并这些子问题的解，从而得到问题的解。

（1） 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问

题。

（2） 解决：若子问题规模较小而容易被解决则直接解决，否则继续分解为更小的子

问题，直至容易解决。

（3） 合并：将已求解的各个子问题的解，逐步合并为原问题的解。

5. 动态规划策略

基本思想：把求解问题分成许多阶段或多个子问题，然后按顺序求解各个子问题。 基本步骤：

（1） 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意，着

若干个阶段一定要是有序的或者可排序的。

（2） 选择状态：将问题发展到各个阶段时所出现的各个客观情况用不同的状态表

示出来。当然，状态的选择要满足无后效性。

（3） 确定决策并写出状态转移方程：状态转移就是根据上一阶段的状态和决策来

导出本阶段的状态。这就像是“递推”，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

6. 递推