算法设计与分析.docx
《算法设计与分析.docx》由会员分享，可在线阅读，更多相关《算法设计与分析.docx（15页珍藏版）》请在冰点文库上搜索。
算法设计与分析
算法设计与分析
第1章绪论
算法理论研究的是算法的设计技术和算法的分析技术，前者是指面对一个问题，如何设计一个有效的算法，后者则是对已设计的算法，如何评价或判断其优劣。
二者是相互依存的，设计出的算法需要检验和评价，对算法的分析反过来又将改进算法的设计。
1.1算法的基本概念
算法的概念在计算机科学领域几乎无处不在，在各种计算机软件系统的实现中，算法设计往往处于核心地位。
例如，操作系统是现代计算机系统中不可缺少的系统软件，操作系统的各个任务都是一个单独的问题，每个问题由操作系统中的一个子程序根据特定的算法来实现。
用什么方法来设计算法，如何判定一个算法的优劣，所设计的算法需要占用多少时间资源和空间资源，在实现一个软件系统时，都是必须予以解决的重要问题。
1.1.1为什么要学习算法
用计算机求解任何问题都离不开程序设计，而程序设计的核心是算法设计。
一般来说，对程序设计的研究可以分为四个层次：
算法、方法学、语言和工具，其中算法研究位于最高层次。
算法对程序设计的指导可以延续几年甚至几十年，它不依赖于方法学、语言和工具的发展与变化。
例如，用于数据存储和检索的Hah算法产生于20世纪50年代，用于排序的快速排序算法发明于20世纪60年代，但他们至今仍被人们广为使用，可是程序设计方法已经从结构化发展到面向对象，程序设计语言也变化了几代，至于编程工具很难维持三年不变。
所以，对于从事计算机专业的人士来说，学习算法是非常必要的。
学习算法还能够提高人们分析问题的能力。
算法可以看作是解决问题的一类特殊方法——它不是问题的答案，而是经过精确定义的①、用来获得答案的求解过程。
因此，无论是否涉及计算机，特定的算法设计技术都可以看作是问题求解的有效策略。
著名的计算机科学家科努思（Donald·Knuth）是这样论述这个问题的：
“受过良好训练的计算机科学家知道如何处理算法，如何构造算法、操作算法、理解算法以及分析算法，这些知识远不只是为了编写良好的计算机程序而准备的。
算法是一种一般性的智能工具，一定有助于我们对其他学科的理解，不管是化学、语言学、音乐还是另外①
算法固有的精确性限制了它所能够解决的问题种类，比如说，我们无法找到一个使人生活快乐的算法，也不能找到一个使人富有和出名的算法。
的学科。
为什么算法会有这种作用呢？
我们可以这样理解：
人们常说，一个人只有把知识教给别人，才能真正掌握它。
实际上，一个人只有把知识教给计算机，才能真正掌握它，也就是说，将知识表述为一种算法比起简单地按照常规去理解事物，用算法将其形式化会使我们获得更加深刻的理解。
”
算法研究的核心问题是时间（速度）问题。
人们可能有这样的疑问：
既然计算机硬件技术的发展使得计算机的性能不断提高，算法的研究还有必要吗？
计算机的功能越强大，人们就越想去尝试更复杂的问题，而更复杂的问题需要更大的计算量。
现代计算技术在计算能力和存储容量上的革命仅仅提供了计算更复杂问题的有效工具，无论硬件性能如何提高，算法研究始终是推动计算机技术发展的关键。
下面看几个例子。
1.检索技术
20世纪50~60年代，检索的对象是规模比较小的数据集合。
例如，编译系统中的标识符表，表中的记录个数一般在几十至数百这样的数量级。
70~80年代，数据管理采用数据库技术，数据库的规模在K级或M级，检索算法的研究在这个时期取得了巨大的进展。
90年代以来，Internet引起计算机应用的急速发展，海量数据的处理技术成为研究的热点，而且数据驻留的存储介质、数据的存储方法以及数据的传输技术也发生了许多变化，这些变化使得检索算法的研究更为复杂也更为重要了。
近年来，智能检索技术成为基于Web信息检索的研究热点。
使用搜索引擎进行Web信息检索时，经常看到一些搜索引擎前50个搜索结果中几乎有一半来自同一个站点的不同页面，这是检索系统缺乏智能化的一种表现。
另外，在传统的Web信息检索服务中，信息的传输是按“Pull”的模式进行的，即用户找信息。
而采用“Puh”的方式，是信息找用户，用户不必进行任何信息检索，就能方便地获得自己感兴趣的信息，这就是智能信息推送技术。
这些新技术的每一项重要进步都与算法研究的突破有关。
2.压缩与解压缩
随着多媒体技术的发展，计算机的处理对象由原来的字符发展到图像、图形、音频、视频等多媒体数字化信息，这些信息数字化后，其特点就是数据量非常庞大，同时，多媒体所需的高速传输速度也是计算机总线所不能承受的。
因此，对多媒体数据的存储和传输都要求对数据进行压缩。
声音文件的MP3压缩技术说明了压缩与解压缩算法研究的巨大成功，一个播放3～4分钟歌曲的MP3文件通常只需3MB左右的磁盘空间。
3.信息安全与数据加密
2
来盗用你的信用卡！
”这的确是一个可怕的情景。
所以，在电子商务中，信息安全是最关键的问题，保证信息安全的一个方法就是对需要保密的数据进行加密。
在这个领域，数据加密算法的研究是绝对必须的，其必要性与计算机性能的提高无关。
1.1.2算法及其重要特性
算法（Algorithm）被公认为是计算机科学的基石。
通俗地讲，算法是解决问题的方法，严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列，此外，算法还必须满足下列五个重要特性：
⑵输出：
一个算法有一个或多个输出。
既然算法是为解决问题而设计的，那么算法实现的最终目的就是要获得问题的解。
没有输出的算法是无意义的。
⑶有穷性：
一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成。
⑷确定性：
算法中的每一条指令必须有确切的含义，不存在二义性。
并且，在任何条件下，对于相同的输入只能得到相同的输出。
⑸可行性：
算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
问题
输出输入算法（确定性、有穷性、可行性）
图1.1算法的概念
概念回顾算法和程序不同。
程序（Program）是对一个算法使用某种程序设计语言的具体实现，原则上，算法可以用任何一种程序设计语言来实现。
算法的有穷性意味着不是所有的计算机程序都是算法。
1.1.3算法的描述方法
算法设计者在构思和设计了一个算法之后，必须清楚准确地将所设计的求解步骤记录下来，即描述算法。
常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。
下面以欧几里德算法（用辗转相除法求两个自然数m和n的最大公约数）为例进行介绍。
3
⑴自然语言
用自然语言描述算法，最大的优点是容易理解，缺点是容易出现二义性，并且算法通常都很冗长。
欧几里德算法用自然语言描述如下：
①输入m和n；
②求m除以n的余数r；
③若r等于0，则n为最大公约数，算法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。
⑵流程图
用流程图描述算法，优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言。
欧几里德算法用流程图描述如图1.2所示。
在计算机应用早期，使用流程图描述算法占有统治地位，但实践证明，除了一些非常简单的算法以外，这种描述方法使用起来非常不方便。
如今，只能在早期有关算法的教材中找到它的踪影了。
⑶程序设计语言
用程序设计语言描述的算法能由计算机直接执行，而缺点是抽象性差，使算法设计者拘泥于描述算法的具体细节，忽略了“好”算法和正确逻辑的重要性，此外，还要求算法设计者掌握程序设计语言及其编程技巧。
开始欧几里德算法用C++语言书写的程序如下：
#include
intr=m%n;while（r!
=0）{
m=n;n=r;
r=m%n;}
returnn;}
voidmain（）{
cout<
伪代码（Peudocode）是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。
至于算法中自然语言
4
输入m和nr=m%nYNm=nn=r输出n结束图1.2用流程图描述算法
r=0的成份有多少，取决于算法的抽象级别，抽象级别高的伪代码自然语言多一些。
计算机科学家从来没有对伪代码的书写形式达成过一种共识，只是要求了解任何一种现代程序设计语言的人都能很好地理解。
欧几里德算法采用符合C++语法的伪代码描述如下：
算法1.1——欧几里德算法1.r=m%n;2.循环直到r=02.1m=n;2.2n=r;2.3r=m%n;3.输出n;伪代码不是一种实际的编程语言，但在表达能力上类似于编程语言，同时极小化了描述算法的不必要的技术细节，是比较合适的描述算法的方法，被称为“算法语言”或“第一语言”。
1.1.4算法设计的一般过程
算法是问题的解决方案，这个解决方案本身并不是问题的答案，而是能获得答案的指令序列。
不言而喻，由于实际问题千奇百怪，问题求解的方法千变万化，所以，算法的设计过程是一个灵活的充满智慧的过程，它要求设计人员根据实际情况具体问题具体分析。
可以肯定的是，发明（或发现）算法是一个非常有创造性和值得付出的过程。
②
在设计算法时，遵循下列步骤可以在一定程度上指导算法的设计。
1．理解问题
在面对一个算法任务时，算法设计者往往不能准确地理解要求他做的是什么，对算法希望实现什么只有一个大致的想法就匆忙地落笔写算法，其后果往往是写出的算法漏洞百出。
在设计算法时需要做的第一件事情就是完全理解要解决的问题，仔细阅读问题的描述，手工处理一些小例子。
对设计算法来说，这是一项重要的技能：
准确地理解算法的输入是什么？
要求算法做的是什么？
即明确算法的入口和出口，这是设计算法的切入点。
2．预测所有可能的输入
算法的输入确定了该算法所解问题的一个实例。
一般而言，对于问题P，总有其相应的实例集I，则算法A若是问题P的算法，意味着把P的任一实例input∈I作为算法A的输入，都能得到问题P的正确输出。
②
这个一般过程并不是一个绝招，能为任意的问题设计算法，一个公认的事实是——这样的绝招是不存在的。
5
3.通用分治递推式
递归算法分析的第三种技术是利用通用分治递推式：
cT（n）kaT（nb）cnn1n1
其中a，b，c，k都是常数。
这个递推式描述了大小为n的原问题分成若干个大小为n/b的子问题，其中a个子问题需要求解，而cnk是合并各个子问题的解需要的工作量。
下面使用扩展递归技术对通用分治递推式进行推导，并假定n=bm。
nT（n）aTcnkbnna（aT2c）cnkbbaT
（1）ammm1knncm1accnkbbkkkncamimibi0camibiki0m
bkmcai0amibk这个求和是一个几何级数，其值依赖于比率ra，注意到am=alogbn=nlogba，有
以下三种情况：
1，由于am=nlogba，所以T（n）=O（nlogba）。
1ri0m
（2）r=1：
rim1logbn1，由于am=nlogba=nk，所以T（n）=O（nklogbn）。
（1）r<1：
rii0mrm11mmkmk（3）r>1：
rO（rm），所以，T（n）=O（ar）=O（b）=O（n）。
r1i0mi对通用分治递推式的推导概括为下面的主定理：
O（nlogba）T（n）O（nklogbn）kO（n）abkabkabk16
1.2.5算法的后验分析
前面我们介绍了如何对非递归算法和递归算法进行数学分析，这些分析技术能够在数量级上对算法进行精确度量。
但是，数学不是万能的，实际上，许多貌似简单的算法很难用数学的精确性和严格性来分析，尤其在做平均效率分析时。
算法的后验分析（Poteriori）也称算法的实验分析，它是一种事后计算的方法，通常需要将算法转换为对应的程序并上机运行。
其一般步骤如下：
1.明确实验目的
在对算法做实验分析时，可能会有不同的目的，例如，检验算法效率理论分析的正确性；比较相同问题的不同算法或相同算法的不同实现间的效率，等等，实验的设计依赖于实验者要寻求什么答案。
2.决定度量算法效率的方法，为实验准备算法的程序实现
实验目的有时会影响，甚至会决定如何对算法的效率进行度量。
一般来说，有以下两种度量方法：
⑴计数法。
在算法中的适当位置插入一些计数器，来度量算法中基本语句（或某些关键语句）的执行次数。
⑵计时法。
记录某个特定程序段的运行时间，可以在程序段的开始处和结束处查询系统时间，然后计算这两个时间的差。
对于某些典型的算法（例如TSP问题），研究人员已经制定了一系列输入实例作为测试的基准，但大多数情况下，需要实验人员自己确定实验的输入样本。
一般来说，通常需要确定：
⑴样本的规模。
一种可借鉴的方法是先从一个较小的样本规模开始，如果有必要再加大样本规模。
⑵样本的范围。
一般来说，输入样本的范围不要小得没有意义，也不要过分大。
此外，还要设计一个能在所选择的样本范围内产生输入数据的程序。
⑶样本的模式。
输入样本可以符合一定的模式，也可随机产生。
根据一个模式改变输入样本的好处是可以分析这种改变带来的影响，例如，如果一个样本的规模每次都会翻倍，可以通过计算T（2n）/T（n），考察该比率揭示的算法性能是否符合一个基本的效率类型。
如果对于相同规模的不同输入实例，实验数据和实验结果会有很大不同，则需要考虑是否包括同样规模的多个不同输入实例。
例如排序算法，对于同样数据集合的不同初始排列，算法的时间性能会有很大差别。
17
4.对输入样本运行算法对应的程序，记录得到的实验数据
作为实验结果的数据需要记录下来，通常用表格或者散点图记录实验数据，散点图就是在笛卡儿坐标系中用点将数据标出。
以表格呈现数据的优点是直观、清晰，可以方便地对数据进行计算，以散点图呈现数据的优点是可以确定算法的效率类型。
例如表1.1是对某算法采用计数法得到的实验数据，图1.7是一个典型的散点图。
表1.1表格法记录实验数据
规模次数100011,966200024,303执行次数或时间300039,992400053,010500067,272600078,692700091,2748000113,0639000129,799
问题规模n图1.7典型的散点图
5.分析得到的实验数据
根据实验得到的数据，结合实验目的，对实验结果进行分析，并根据实验结果不断调整实验的输入样本，经过对比分析，得出具体算法效率的有关结论。
算法的数学分析和实验分析的基本区别是：
数学分析不依赖于特定输入，缺点是适用性不强，尤其对算法做平均性能分析时。
实验分析能够适用于任何算法，但缺点是其结论依赖于实验中使用的特定输入实例和特定的计算机系统。
实际应用中，可以采用数学分析和后验分析相结合的方式来分析算法。
此时，描述算法效率的函数是在理论上确定的，而其中一些必要的参数则是针对特定计算机或程序根据实验数据得来。
1.3实验项目——求最大公约数
1.实验题目
求两个自然数m和n的最大公约数。
2.实验目的
⑴复习数据结构课程的相关知识，实现课程间的平滑过渡；
18
⑵掌握并应用算法的数学分析和后验分析方法；⑶理解这样一个观点：
不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。
3.实验要求
⑴至少设计出三个版本的求最大公约数算法；
⑵对所设计的算法采用大O符号进行时间复杂性分析；
⑶上机实现算法，并用计数法和计时法分别测算算法的运行时间；⑷通过分析对比，得出自己的结论。
4.实现提示
设m和n是两个自然数，m和n的最大公约数记为gcd（m,n），是能够同时被m和n整除的最大整数。
下面给出求最大公约数三个版本的算法思想，注意算法中没有对输入数据进行校验。
算法1.4——连续整数检测1．t=min{m,n};2.m除以t，如果余数为0，则执行步骤3，否则，执行第4步；3．n除以t，如果余数为0，返回t的值作为结果，否则，执行第4步；4．t=t-1，转第2步；例如，要计算gcd（66,12），首先令t=12，因为66除以12余数不为0，将t减1，而12除以11余数不为0，再将t减1，重复上述过程，直到t＝6，此时12除以6的余数为0并且66除以6的余数为0，则gcd（66,12）＝6。
算法1.5——欧几里德算法1.r=m%n;2.循环直到r=02.1m=n;2.2n=r;2.3r=m%n;3.输出n;例如，要计算gcd（66,12），因为66除以12的余数为6，再将12除以6，余数为0，则gcd（66,12）＝6。
算法1.6——分解质因数1．将m分解质因数；2．将n分解质因数；3．提取m和n中的公共质因数；4．将m和n中的公共质因数相乘，乘积作为结果输出；
19
例如，要计算gcd（66,12），首先分解质因数66=2某3某11，12＝2某2某3，然后提取二者的公共质因数2某3，则gcd（66,12）＝2某3＝6。
严格地说，算法1.6还不能称为一个真正意义上的算法，因为其中求质因数的步骤没有明确定义（该步骤应该得到一个质因数的数组），如何提取m和n中的公共质因数也没有定义清楚，请读者将这个算法补充完整。
阅读材料——人工神经网络与BP算法
人工神经网络（ArtificialNeuralNetwork，简称ANN）是一个以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作状态响应而进行信息处理。
人工神经网络技术与计算机技术的结合，为人类进一步研究模拟人类智能及了解人脑思维的奥秘开辟了一条新途径。
人类对人工神经网络的研究可以追溯到1943年，心理学家W.S.McCuloch和数理逻辑学家W.Pitt最早提出的人工神经网络模型——M-P模型，这是第一个用数理语言描述人脑的信息处理过程的模型，从此开创了神经科学理论研究的新纪元；1969年，人工智能的创始人之一M.Minky和S.Papert出版了有较大影响的《感知器》一书，指出感知器功能上的局限性，该论点极大地影响了人工神经网络的研究，至此进入了人工神经网络发展史上长达10年的低潮期。
进入80年代后，随着计算机科学、生物技术和光电技术等领域学科的迅速发展，人工神经网络的研究进入到了一个新的大发展阶段。
1982年美国生物学家、物理学家J.Hopfield提出了Hopfield网络模型；1985年
D.E.Rumelhart和J.LMcclelland提出了误差反向传播算法（Back-PropagationAlgorithm，简称BP算法），成为至今为止影响较大的一种网络学习方法；1992年，Holland用模拟生物进化的方式提出了遗传算法，用来求解复杂优化问题；1995年Mitra把人工神经网络与模糊逻辑理论、生物细胞学说以及概率论相结合提出了模糊神经网络，使得神经网络的研究取得了突破性进展。
人工神经网络是由许多人工神经元按一定规则连接构成的，其互连模式有许多的种类，常见的一种分类是前馈网络和反馈网络。
1988年，以美国学者Rumelhart、Hinton和William等为首，提出了基于BP算法的多层前向神经网络，成功地解决了多层神经网络中隐含层神经元连接权值的学习问题。
该网络模型一经问世，立即受到众多学者的关注，并取得了很大发展。
目前，该网络是最常用、最流行、最成熟的人工神经网络。
其学习方式采用误差反向传播算法，具有很强的非逻辑归纳特性。
理论研究表明：
一个三层的前馈神经网络能够模拟任何复杂的非线性系统。
图1是三层前向神经网络拓扑结构图。
20
Y11WijY12WjkY13jk输入层隐含层输出层
图1三层前向神经网络拓扑结构图
说明：
Yi1为输入层结点i的输入，Yk3为输出层结点k的输出，Yj2为隐含层结点j的输出，Tk为输出层结点k对应的教师信号，Wij为结点i和结点j间的连接权值，Wjk为结点j和结点k间的连接权值，k为输出层结点k的阀值，j为隐含层结点j的阈值。
BP算法的主要思想是，学习过程由信号的正向传播与误差的逆向传播两个过程组成，正向传播时，模式作用于输入层，经隐含层处理后，传向输出层。
若输出层未能得到期望的输出，则转入误差的逆向传播阶段，将输出误差按某种形式，通过隐含层向输入层逐层返回，并“分摊”给各层的所有单元，从而获得各层单元的参考误差（称误差信号），以作为修改各单元间权值的依据。
这种信号正向传播与误差逆向传播的各层权矩阵的修改过程，是周而复始地进行的，权值不断修改的过程也就是网络的学习（或称训练）过程。
此过程一直进行到网络输出的误差逐渐减小到可接受的程度或达到设定的学习次数为止。
设隐含层和输出层的激活采用S型函数；
f（某）1
1e某由于BP算法要求网络的输入输出函数具有可微分性，而S型函数具有此特性。
从形式上看，S型函数的输出曲线两端平坦，中间部分变化激烈；从生理学角度看，一个人对远远低于或高于他智力和知识水平的问题，往往很难产生强烈的思维反应；从数学角度看，S型函数具有可微分性，且具有饱和非线性，可以增加网络的非线性映射能力，因此S型函数更接近于生物神经元的信号输出形式，所以选用S型函数作为BP网络的输出函数。
误差函数（网络的实际输出向量Yk与教师信号向量Tk的误差）采用二乘误差函数；
1NE（TkYk）2
2K1BP算法的一般框架如下：
21
1．初始化网络权值W（t）和阈值（t）；
其中，W（t）和（t）为较小的随机数，t为学习次数，初始值为0；
2．输入一个学习样本（某k,Tk），其中k＝（1,2,,n），n为样本数；
3．计算隐含层各结点的输出值；
4．计算输出层结点的输出值；
5．计算输出层结点和隐含层结点之间权值的修正量；
6．计算隐含层结点和输入层结点之间权值的修正量；
7．基于步骤5的修正量来修正输出层和隐含层连接权值矩阵和阈值向量；
8．基于步骤6的修正量来修正隐含层和输入层连接权值矩阵和阈值向量；
9．判断全部学习样本是否未取完，若取完，则转步骤2，否则9.1计算误差函数；9.2若小于规定的误差上限，则算法结束；9.3若已达到学习次数，则算法结束；否则t＝t＋1，转步骤2；人工神经网络具有以分布方式存储知识、并行方式处理、较强的容错能力，并且它具有可以逼近任意的非线性函数以及有很强的自学习、自适应及联想记忆功能等特征，吸引了众多研究人员的兴趣，并在相关领域取得了显著的进展。
例如：
自动化领域中的系统识别和神经控制器以及智能检测，经济领域中的市场预测和信贷分析，工程领域中的汽车工程、军事工程、水利工程、化学工程，信息领域中的信号处理、模式识别、数据压缩，医学领域中的生物活动分析、医学专家系统等。
参考文献
[1]周春光等.计算智能.吉林大学出版社,2001
[2]李晓峰.人工神经网络BP算法的改进与应用.四川大学学报.2000
（2）
习题1
1．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。
请用伪代码描述这个版本的欧几里德算法。
2.图论诞生于七桥问题。
出生于瑞士的伟大数学家A欧拉（LeonhardEuler，1707—1783）提出并解决了
D该问题。
七桥问题是这样描述的：
一个人是否能在
C一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在
波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，右面是这条河以及河上的两个B岛和七座桥的草图。
请将该问题的图模型抽象出来，第2题图并判断此问题是否有解。
3．计算π值的问题能精确求解吗？
设计求解π值的算法。
4．设计算法求数组中相差最小的两个元素（称为最接近数）的差。
要求分别给出伪代
22
码和C++描述。
5．对于下列函数，请指出当问题规模增加到4倍时，函数值会增加多少？
（1）log2n
（2）n（3）n（4）n2（5）n3（6）2n
6．考虑下面的算法，回答下列问题：
//n
（1）该算法求的是什么？
intStery（intn）为非负整数{
（2）该算法的基本语句是什么？
S=0;
（3）基本语句执行了多少次？
for（i=1;i<=n;i++）（4）该算法的效率类型是什么？
S=S+i某i;
returnS;（5）对该算法进行改进，分析改进算法的效率；
}（6）如果算法不能再改进了，请证明这一点。
7．使用扩展递归技术求解
升级会员 