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

一、实验内容：

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

二、学习掌握：

基本程序描述：

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

（2）费用矩阵：费用矩阵的主要内容是动态生成二维数组。首先由键盘输入自然数，费用矩阵的元素由随机数产生，并取整，把生成的矩阵存放在二维数组中，最后把矩阵内容输出到文件和屏幕上。它采用分支界限法，分支限界法的基本思想是对包含具有约束条件的最优化问题的所有可行解的解（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的解空间不断分割为越来越小的子集，并为每个子集内的解计算一个下界或上界。动态生成二维n*n的数组程序利用指针表示数组的行和列，并逐一分配空间，在输入n的数值后，系统自动分配空间，生成n*n的数组，并产生随机数填充数组，最后将结果输入到指定文件中。

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

三.疑问与总结：

货郎担的问题，我认为穷举法相对比而言是比较初级的方法，费时耗力，适合在练习时选用，但是在实际问题中不建议采用。克鲁斯卡尔或者普里姆算法求取最小生成树的方法来解决货郎担的问题是更适合现实解决问题的。我认为程序可以用switch函数来将函数分成几个部分更人性化，比如分为解决问题的的选项，输出结果选项，退出程序选项等。再有就是费用矩阵的值可以从文件中读取，而结果也可以直接放在指定文件中，这样在实际应用中比较广泛。

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

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

四.心得体会

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

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

 

第二篇：算法设计与分析总结

第一章 绪论

1、重要特性

1.输入

2.输出

3.有穷性

4.确定性

5.可行性

2、描述算法的方法

1.自然语言：优点是直观易懂，缺点是容易出现二义性

2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言

3.程序设计语言：优点是计算机直接运行，缺点是抽象性差

4.伪代码：

3、递归算法分析

1.猜测技术

2.扩展递归技术

3.通用分治递归推式

第二章 NP完全理论

第三章 蛮力法

3.1 蛮力法的设计思想

蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;

关键——依次处理所有元素。

3.2 查找问题中的蛮力法

3.2.1 顺序查找O(n)

3.2.2串匹配问题

BF O(n*m)

BMP O(n+m)

BM O(n*m)

3.3 排序问题中的蛮力法

3.3.1 选择排序O(n²)

3.3.2 起泡排序O(n²)

3.4 组合问题中的蛮力法

3.4.1 生成排列对象O(n!)

3.4.2 生成子集O(2ⁿ)

3.4.3 0/1背包问题O(2ⁿ)

3.4.4 任务分配问题O(n!)

3.5 图问题中的蛮力法

3.5.1 哈密顿回路问题O(n!)

3.5.2 TSP问题O(n!)

3.6 几何问题中的蛮力法

3.6.1 最近对问题O(n²)

3.6.2 凸包问题O(n³)

3.7 实验项目——串匹配问题

第四章 分治法

4.1 分治法的设计思想

设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

步骤：（1）划分（2）求解子问题（3）合并

4.2 排序问题中的分治法

4.2.1 递归排序O(nlog₂n)

4.2.2 快速排序O(nlog₂n)

4.3 组合问题中的分治法

4.3.1 最大字段和问题O(nlog₂n)

4.3.2棋盘覆盖问题O(4^k)

4.3.3 循环赛日程安排问题O(4^k)

4.4 几何问题中的分治法

4.4.1 最近对问题O(nlog₂n)

4.4.2 凸包问题O(nlog₂n)

4.5 实验项目——最近对问题

第五章 减治法

5.1 减治法的设计思想

原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。

5.2 查找问题中的减治法

5.2.1 折半查找O(log₂n)

5.2.2 二叉查找树O(log₂n)

5.3 排序问题中的减治法

5.3.1 堆排序O(log₂n)

5.3.2 选择问题O(log₂n)

5.4 组合问题中的减治法

5.4.1 淘汰塞冠军问题O(n)

5.4.2 假币问题O(log₂n)

5.5 实验项目——8枚硬币问题

第六章 动态规划法

6.1动态规划法的设计思想

将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。

步骤：

将原始问题分解为相互重叠的子问题，确定动态规划函数；

求解子问题，填表；

根据表，自底向上计算出原问题的解。

6.2 图问题中的动态规划法

6.2.1 TSP问题O(2ⁿ)

6.2.2 多段图的最短路径问题O(n+m)

6.3 组合问题中的动态规划法

6.3.1  0/1背包问题O(n*C)

6.3.2 最长公共子序列问题O(n*m)

 .

6.4 查找问题中的动态规划法

6.4.1 最优二叉查找树O(n^3)

6.4.2 近似串匹配问题

6.5 实验项目——最大子段和问题

第七章 贪心法

7.1 贪心法的设计思想

贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。

贪心法的关键在于决定贪心策略。

7.2 图问题中的贪心法

7.2.1 TSP问题O(2ⁿ)

7.2.2 图着色问题

7.2.3 最小生成树问题O(2ⁿ)

7.3 组合问题中的贪心法

7.3.1 背包问题O(nlog₂n)

7.3.2 活动安排问题O(nlog₂n)

7.3.3 多机调度问题O(n*m)

7.4 实验项目——哈夫曼编码

第八章 回溯法

8.1 回溯法的设计思想

从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。

步骤：

确定解向量和分量的取值范围，构造解空间树；

确定剪枝函数；

对解空间树按深度优先搜索，搜索过程中剪枝；

从所有的可能解中确定最优解。

8.2 图问题中的回溯法

8.2.1 图着色问题

8.2.2 哈密顿回路问题

8.3 组合问题中的回溯法

8.3.1 八皇后问题

8.3.2 批处理作业调度问题

8.4 实验项目——0/1背包问题

第九章 分支界限法

9.1 分支限界法的设计思想

1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] ，并确定限界函数；

2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；

3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；

4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；

5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。

步骤：

确定解空间树

确定限界函数

按广度优先搜索解空间树，计算限界函数的值，填入PT表

从PT表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。

9.2 图问题中的分支限界法

9.2.1 TSP问题

9.2.2 多段图的最短路径问题

9.3 组合问题中断饿分支限界法

9.3.1 任务分配问题

9.3.2 批处理作业调度问题

5

9.4 实验项目——电路布线问题

第十章 概率算法