算法分析与设计报告

百度文库 - 让每个人平等地提升自我

1

中 国 地 质 大 学

研究生课程论文封面

课程名称 算法分析与设计

教师姓名

研究生姓名

研究生学号

研究生专业 计算机技术

所在院系 计算机学院

类别: B.硕士

日期: 2014 年 1 月 8 日

百度文库 - 让每个人平等地提升自我

2 评 语

对课程论文的评语:

平时成绩： 课程论文成绩：

总 成 绩： 评阅人签名：

注：1、无评阅人签名成绩无效；

2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；

3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。

百度文库 - 让每个人平等地提升自我

3 第一章 算法导引

算法

算法：用计算机求解问题的步骤、规则

内存空间——>初始状态—————>终止状态

有限状态机

算法的五个特性：

输出：一个算法产生一个或多个输出

从内存——>认识状态

输入：一个算法有0个输入或多个输入

input a，b

无二义性：算法的每一种运算必须要有确切的定义，即每一种运算应该执行何种动作必须是相当清楚的、无二义性的（人和计算机、智能、确定的、机器；人机象棋：搜索）。

能行性：

（1）人能做，机器没法做：能够形式化，没有办法写出算法

（2）股票预测、彩票：模型

有限性：可计算问题、有限的、可忍耐

算法设计：自动化、自动程序设计、公式发现、公式挖掘、知识发现

算法验证：设计—表示（语言）—确认—分析—测试程序

算法分析

数学模型：

1.串行算法，冯诺依曼机

2.均匀存贮，存贮空间足够大

3.基本运算时间确定

基本概念：

1.问题规模：与参数有关

2.频率计数

不分析算法具体执行时间，分析问题复杂性：问题规模增大时的规律

根据复杂性，将算法分为两类：

1.多项式时间算法P：C，㏒n，n，n㏒n，n2（理论上可行，实际上也可行）

2.指数时间算法NP：2n，n！，nn（理论上可行，实际上不可行）

O(l)

O(2n)< O(n!)< O(nn)

解决方法：降低算法设计复杂度

分析算法时间与问题规模：

确定f(n)=O(g(n))上界和f(n)=Ω(g(n))下界

小结

老师首先带领我们回顾了本科阶段的算法基础相关知识，对于没有系统学习过算法知识的我来说，更是一种知识入门，使我对这门课程有一些初步的了解。然后在对算法进行分析时，不分析算法具体的执行时间，而是分析问题的复杂性（问题规模增大时的规律）。根据算法的特点可以将要求解的问题分为两类：离散型和连续型。离散型问题需要讨论问题的规模，如果是多项式时间复杂度则称为P问题；如果是指数时间复杂度则称为NP问题。对于连续型问题，需要讨论算法的收敛性。

百度文库 - 让每个人平等地提升自我

4 第二章 分治法

一般方法

在求解问题时，为了将问题简化，将实际问题转变为数学问题，将数学问题转变为代数问题，将代数问题转变为解方程问题，将解方程问题转变为解线性方程组问题。

求解问题的技术：

1.化难为易的校正技术：例如求f(x)=a-x2=0；

2.化粗为精的松弛技术：直接法，间接法，例如求圆的面积（割圆法）

3.化大为小的缩减技术：f(n)=n*f(n-1)，f(1)=1问题性质不变

分治法的思想：将整个问题分为若干个小问题分而治之，问题的性质不变。它的求解可用一个递归过程来表示。

二分检索

已知一个按非降次序排列的元素表a1,a2,…,an，要求判定某给定元素x是否在该表中出现。问题规模O(㏒n)

归并分类（排序）

Procedure mergesort(low,high)

if low

then mid |(low+high)/2」

call mergesort(low,mid)

call mergesort(mid+1,high)

call mergesort(low,mid,high)

end if

问题规模O(n㏒n)

快速分类

反复对产生的文件进行划分

斯特拉森矩阵乘法

***mllnmnABC问题规模O(n3)

小结

分治法是一种用空间换时间的技术，通过将大规模的问题划分为小规模问题进行求解来降低求解难度，采用分治技术，问题首先必须能够分解，而且分解后，问题的性质并没有发生变化。采用分治技术的目的只是并行算法设计，降低算法时间复杂度。在本章老师主要讲解了分治法的基本递归求解，二分检索、归并分类、快速分类、斯特拉森矩阵乘法以及它们的时间复杂度的求解。

第三章 贪心法

一般方法

概念：有n个输入，问题的解是这n个输入的一个子集，子集满足一组条件（约束条件），子集可能有很多，满足条件的子集叫做可行解，根据问题，人们设计一个函数，通过函数极值的计算，找到一个最优的可行解，叫做最优解。

离散优化问题

连续函数优化问题的分类： 百度文库 - 让每个人平等地提升自我

5 1.函数优化问题：f(x)：高维、非线性、不连续、没有明确的解析式；这类问题的求解方法有：解方程法、迭代法（最速下降法、共轭方向法、牛顿迭代法等）、随机优化（演化计算）等。

2.模型参数优化：此类问题的求解方法一般是：根据所给问题或者曲线，然后预测方程，对预测方程中的参数进行优化求解。

3.模型发现问题：自动程序设计，一般是输入散点，要求给出拟合曲线。解决方法有基因表达式程序设计等。

优化问题分类：

1.有约束优化与无约束优化

2.线性优化与非线性优化

3.静态优化与动态优化（实时性）

4.确定性优化与随机优化

5.单目标优化与多目标优化（矛盾或不协调的）

贪心算法是一种分级处理方法，它根据问题性质找到一种度量标准

背包问题

部分背包问题的数学模型为：假设背包容量为m，有n件物品，每种物品i的重量为wi，其效益值为pi，问如何装包，在背包的容量范围内装出的值最多。

1maxniiixp

1niiixwM

xi∈{0,1} 0/1背包问题

xi∈[0,1] 部分背包问题

老师以书上的题目为例，根据按效益值由大到小的装、按质量由小到大的装和按单位质量效益值由大到小的装（pi/wi）三种方法来寻找最优解。经过计算可知按单位质量效益值由大到小的装包获得的结果最好。

最小生成树问题

设G=(V,E)是一个无向连通图，如果G的生成子图T=(V,E’)是一棵树，则称T是G的一棵生成树。根据边成本由小到大排序，找到最优的生成树。

小结

贪心算法适用于求解从给定的n个输入中找到一个满足约束条件的子集的问题。满足约束条件的子集称为可行解，满足目标函数的可行解称为最优解。用贪心算法求解问题的关键在于找出求解问题的量度标准。本章老师主要讲了贪心算法的适用领域，详细讲解了背包问题及最小生成树的算法及其时间复杂度的求解。为了便于学生理解，老师联系自己曾经做过的毕业设计的凸多边形问题，讲述了是如何对问题进行分析和寻找解决方案的，而且讲解了为何贪心算法无法用于求解凸多边形问题，使同学们更好的领悟和体会贪心法的应用范围。

第四章 动态规划

一般方法

求解优化问题的方法：

1.多阶段决策：可以把问题分成若干阶段 百度文库 - 让每个人平等地提升自我

6 2.最优性原理：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列（找到一个递推关系式）。

多段图问题

多段图G=(V,E)，求源点s到汇点t的最短路径

设cost(i,j)表示从源点到第i个阶段的j点的最短路径：

1,(,)min{(1,)(,)}ilVljEcostijcostilclj

设Bcost(i,j)表示从第i个阶段的j点到汇点的最短路径：

1,(,)min{(1,)(,)}ilVljEBcostijbcostilclj

每对结点之间的最短路径

单源最短路径问题O(n2)

任意两点间最短路径问题O(n3)

设Ak代表i，j两个结点间考虑了1-k结点时最短路径，A0(i,j)就是成本矩阵

A0(i,j)=C(i,j)

An(i,j)=min{ An-1(i,j), An-1(i,n)+ An-1(n,j)}

Ak(i,j)=min{ Ak-1(i,j), Ak-1(i,k)+ Ak-1(k,j)}

最优二分检索树

设a1< a2< a3<…< an，n个符号

a1 a2 a3 … an

P(1) P(2) P(3) … P(n)

E0 E1 E2 E3 En-1 En

Q(0) Q(1) Q(2) Q(3) Q(n-1) Q(n)

10()()1nniiPiQi

检索成本的计算方法：

10()*()()*(()1)nniiiiPilevelaQilevelE