算法设计心得体会(2)

算法设计心得体会

算法设计与分析学习心得

班级：物联网1201 姓名：刘潇学号：29

一、实验内容：

这学期的算法与设计课，老师布置了这四个问题，分别是货郎担问题，动态生成二维数组，对话框下拉列表，排序问题。

二、学习掌握：

基本程序描述：

货郎担问题：货郎担问题属于易于描述但难于解决的著名难题之一，至今世界上还有不少人在研究它。货郎担问题要从图g的所有周游路线中求取具有最小成本的周游路线，而由始点出发的周游路线一共有！条，即等于除始结点外的n一1个结点的排列数，因此货郎担问题是一个排列问题。货郎担的程序实现了利用穷举法解决货郎担问题，可以在城市个数和各地费用给定的情况下利用穷举法逐一计算出每一条路线的费用，并从中选出费用最小的路线。从而求出问题的解

费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本

思想是对包含具有约束条件的最优化问题的所有可行解的解空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。

Mfc：在下拉列表框中添加内容程序，在下拉列表对应的函数中利用addstring添加需要的内容。首先定义下拉列表框为ccombox型，并定义其属性名，利用addstring函数可以任意添加需要的内容。a排序问题:快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程中产生的两个区域分别包含n-1个元素和1个元素的时候。其算法的时间复杂度为O(n 2),在最好的情况下每次划分的基准恰好为中值，可得其算法时间复杂度为O(n㏒n)。算法的实现和理解和代码实现完全是两回事，想要完全掌握一种算法，需要动手实践，用代码实现，才能理解透彻，真正掌握。b 对话框下拉列表：这个项目简单易懂，轻松实现。

三.疑问与总结：

货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方

法来解决货郎担的问题是更适合现实解决问题的。我认为程序可以用switch函数来将函数分成几个部分更人性化，比如分为解决问题的的选项，输出结果选项，退出程序选项等。再有就是费用矩阵的值可以从文件中读取，而结果也可以直接放在指定文件中，这样在实际应用中比较广泛。

动态生成二维数组的程序我认为如果按照规范性，我的方法是中规中矩的，毕竟再向下延伸，生成三维的数组，需要三层的指针来实现。但是就程序的简化程度和计算机处理时间来说，我认为这样双层指针的算法有些太占用内存，毕竟要给行和列各分配n个空间。我通过与同学的交流，我发现可以用1位数组来实现二维的n*n的数组。首先分配n*n 的空间，

然后通过循环在一行的数据达到n时自动换行。这样程序得到了一定的简化，并且减少了一定的内存使用。我认为这种方法是比较贴合实际的。

四.心得体会

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

如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。

算法分析与设计

学习总结

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

学院信息科学与工程学院

专业届次

学生姓名学号

二○一三年一月十五日

算法分析与设计学习总结

本学期通过学习算法分析与设计课程，了解到：算法是一系列解决问题的清晰指令，代表着用系统的方法描述解决问题的策略机制。算法能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能

用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。

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

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

经典的算法主要有：

1、穷举搜索法

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

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

2、迭代算法

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

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

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

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

3、递推算法

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

4、递归算法

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

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

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

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

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

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

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

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

储。

举例如下：

Fibonacci数列

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

void fibonacci(int n)

{

fib[0] = 1;

fib[1] = 1;

for (int i=2; i fib[i] = fib[i-1]+fib[i-2];

}

5、分治算法

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

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

分治策略的算法设计模式

Divide_and_Conquer

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

Return merge //合并子问题

}

6、贪心算法

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

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

建立数学模型来描述问题

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

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

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

贪心算法的一般流程:

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;

｝

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

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

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

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

可行函数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 bestx[i] = x[i];

bestw = cw;

}

return;

}

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

r -= w[t];

//搜索左子树

if(cw+w[t] {

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、分支限界算法

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

《算法设计与分析》课程的心得体会

以最少的成本、最快的速度、最好的质量开发出合适各

种各样应用需求的软件，必须遵循软件工程的原则，设计出高效率的程序。一个高效的程序不仅需要编程技巧，更需要合理的数据组织和清晰高效的算法。这正是计算机科学领域里数据结构与算法设计所研究的主要内容。一些著名的计算机科学家认为，算法是一种创造性思维活动，并且处于计算机科学与技术学科的核心。

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

如果一个算法有缺陷，或不适合某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂性和时间复杂度来衡量。算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。计算机系统中的操作系统、语言编译系统、数据库管理系统以及各种各样的计算机应用系统中的软件，都必须使用具体的算法来实现。算法设计与分析是计算机科学与技术的一个核心问题。因此，学习算法无疑会增强自己的竞争力，提高自己的修为，为自己增彩。那么，什么是算法呢？算法是指解决问题的方法或

过程。算法

满足四个性质，即输入、输出、确定性和有限性。为了了解算法，这个学期马老师带我们走进了算法的世界。

马老师这学期提出不少实际的问题，以及解决问题的算法。我在此只说比较记忆深刻的问题，即0-1背包的问题。

0-1背包问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

首先，0-1背包问题具有最优子结构性质和子问题重叠性质，适于采用动态规划方法求解。动态规划算法与分治法类似，其基本思想是将待求解问题分解成若干个子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的，若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费过多的时间。动态规划法又和贪婪算法有些一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。

用动态规划法解决问题的思路如下：

最优决策序列由最优决策子序列组成。假设f (i,y)表示剩余容

量为y，剩余物品为i, i+1, ?, n时的最优解的值，即：

f (n,y) = Pn,if y≥Wn

f (n,y) = 0, if 0≤y≤Wn

和

f(i,y)=max(f(i+1,y),f(i+1,y-Wi)+Pi) y≥Wi

f(i,y)=f(i+1,y) 0≤y≤Wi

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的，所以有必要将它详细解释一下：“将前i件物品放入容量为y的背包中”这个子问题，若只考虑第i件物品的策略，那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为y的背包中”，价值为f[i-1][y]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为y-Wi的背包中”，此时能获得的最大价值就是f[i-1][y-Wi]再加上通过放入第i件物品获得的价值Pi。

用贪心算法解决问题的基本思路如下：

由所有解元素组合成问题的一个可行解；从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步do求出可行解的一个解元素；

该算法存在问题：首先不能保证求得的最后解是最佳的；其次不

能用来求最大或最小解问题，并且只能求满足某些约束条件的可行解的范围。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。所以0-1背包问题也可以用回溯法解决。其基本思路是可先将物品依其单位重量价值从大到小排序，此后只要顺序考察各物品即可，这是为了便于计算上界，。在实现时，由bound计算当前结点处的上界。在搜索解空间树时，只要其左儿子节点是一个可行结点，搜索就进入左子树，在右子树中有可能包含最优解是才进入右子树搜索。否则将右子树剪去。

当然0-1背包问题还有许多的解决方案，此处就不一一列出。不过通过0-1背包问题，我深刻体会到算法的魅力，体会到同一个问题用不同的方法解决的妙处。学无止境，《算法设计与分析》仅仅是我学习算法知识入门课，我不会停下脚步，在此之后我依然会努力学习算法知识。

朱凌峰

分析与设计总结

算法是一系列解决问题的清晰指令，也就是说，能够对

一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

一个算法应该具有以下五个重要的特征：

1、有穷性：一个算法必须保证执行有限步之后结束；

2、确切性：算法的每一步骤必须有确切的定义；

3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5、可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

算法复杂度

算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率

来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看

成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

一个算法应该具有以下五个重要的特征：

1、有穷性：一个算法必须保证执行有限步之后结束；

2、确切性：算法的每一步骤必须有确切的定义；

3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；

4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

5、可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

常用算法分为以下五种:

分治法

在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题??直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序

算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)??

常用算法之回溯法

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

最优化原理是动态规划的基础。“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的。

贪心算法贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生

整体最优解或者是整体最优解的近似解。、

分支限界法在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题??直到最后子问题可以简单的直接求解，原问