第一章数值分析2008(绪论).ppt

《第一章数值分析2008(绪论).ppt》由会员分享，可在线阅读，更多相关《第一章数值分析2008(绪论).ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、海军航空工程学院二0五教研室数值分析数值分析 海军航空工程学院二0五教研室教材及参考书目&教材教材 (Text Book)数值分析与算法数值分析与算法 徐士良徐士良 编著编著（机械工业出版社）（机械工业出版社）（华中科技大学出版社）（华中科技大学出版社）&参考书目参考书目(Reference)Numerical Analysis (Seventh Edition)数值分析数值分析 （第七版（第七版 影印版）影印版）Richard L.Burden&J.Douglas Faires （高等教育出版社）高等教育出版社）数值方法数值方法 金一庆、陈越金一庆、陈越 编著编著（机械工业出版社）（机械工业

2、出版社）数值分析数值分析 李庆扬、易大义、王能超李庆扬、易大义、王能超 编著编著海军航空工程学院二0五教研室数值分析的作用数值数值分析分析输入复杂问题或运算输入复杂问题或运算 计算机计算机近似解近似解海军航空工程学院二0五教研室绪论1 1 绪论绪论 1.1 1.1 数值分析数值分析 研究对象与特点研究对象与特点 1.2 1.2 数值计算的误差数值计算的误差 1.2.1 1.2.1 误差来源与分类误差来源与分类 1.2.2 1.2.2 误差与有效数字误差与有效数字 1.2.3 1.2.3 数值计算中应注意的几个原则数值计算中应注意的几个原则 1.3 1.3 算法算法 1.3.1 1.3.1 算法

3、的基本概念算法的基本概念 1.3.2 1.3.2 数值型算法的特点数值型算法的特点 1.3.3 1.3.3 算法设计基本方法算法设计基本方法 1.3.4 1.3.4 算法的复杂度算法的复杂度海军航空工程学院二0五教研室1.11.1数值分析数值分析 研究对象与特点研究对象与特点 数值分析是研究适合于在计算机上使用的实际可数值分析是研究适合于在计算机上使用的实际可行、理论可靠、计算复杂性好的数值计算方法行、理论可靠、计算复杂性好的数值计算方法 第一，面向计算机，要根据计算机特点提供实际第一，面向计算机，要根据计算机特点提供实际可行的算法可行的算法 。第二，要有可靠的理论分析，数值分析中的算法第二，

4、要有可靠的理论分析，数值分析中的算法理论主要是连续系统的离散化及离散型方程数值理论主要是连续系统的离散化及离散型方程数值求解。求解。第三，要有良好的复杂性及数值试验第三，要有良好的复杂性及数值试验 海军航空工程学院二0五教研室要求要求 本课程简单介绍数值方法及其理论，大部分本课程简单介绍数值方法及其理论，大部分定理的证明需要大家自己去学习掌握，着重介绍定理的证明需要大家自己去学习掌握，着重介绍具体的算法设计及编程技巧，作为基本要求让大具体的算法设计及编程技巧，作为基本要求让大家做一些计算机上的数值试验，它对加深算法的家做一些计算机上的数值试验，它对加深算法的理解是很有好处的。理解是很有好处的。

5、海军航空工程学院二0五教研室1.21.2数值计算的误差数值计算的误差 1.2.11.2.1误差来源与分类误差来源与分类 本课程只研究数值求解数学问题时产生的误差，本课程只研究数值求解数学问题时产生的误差，它们主要有以下三类。它们主要有以下三类。1 1截断误差或方法误差截断误差或方法误差 2 2舍入误差舍入误差 3 3输入数据误差输入数据误差 海军航空工程学院二0五教研室1.2.11.2.1误差来源与分类误差来源与分类1 1 1 1截断误差或方法误差截断误差或方法误差它它是是指指将将数数学学问问题题转转化化为为数数值值计计算算问问题题时时产产生生的的误误差差，通常是用有限过程近似无限过程时产生的

6、误差。通常是用有限过程近似无限过程时产生的误差。海军航空工程学院二0五教研室1.2.11.2.1误差来源与分类误差来源与分类2 2 2舍入误差 数值计算时由于计算是有限位的，所以原始数据、中间结果和最后结果都要舍入，这就产生舍入误差。在十进制运算中一般采用四舍五入。例如例如1/31/3写成写成0.333 30.333 3，3.141 63.141 6等等，都有等等，都有舍入误差。舍入误差。海军航空工程学院二0五教研室1.2.11.2.1误差来源与分类误差来源与分类3 33 3输入数据误差输入数据误差 称为初始误差，这些误差对计算也将造成影响，称为初始误差，这些误差对计算也将造成影响，但分析初始

7、误差与对舍入误差分析相似，因此可将但分析初始误差与对舍入误差分析相似，因此可将它归入第二类。它归入第二类。由于对大规模数值计算问题舍入误差目前尚无由于对大规模数值计算问题舍入误差目前尚无有效方法进行定量估计，所以我们主要进行定性分有效方法进行定量估计，所以我们主要进行定性分析析.但对误差估计的基本概念及较简单的数值运算误但对误差估计的基本概念及较简单的数值运算误差估计还需作简单介绍。差估计还需作简单介绍。海军航空工程学院二0五教研室1.2.2 1.2.2 误差与有效数字误差与有效数字1 1 1 1误差的定义误差的定义 绝对误差绝对误差 /*absolute error*/*absolute e

8、rror*/其中其中x x为精确值，为精确值，x x*为为x x的近似值。的近似值。，例如：，例如：工程上常记为工程上常记为，称为绝对误差限，称为绝对误差限 /*accuracy*/*accuracy*/，的上限记为的上限记为注：注：注：注：e*e*e*e*理论上讲是唯一确定的，可能取正理论上讲是唯一确定的，可能取正理论上讲是唯一确定的，可能取正理论上讲是唯一确定的，可能取正，也可能取负。也可能取负。也可能取负。也可能取负。e*e*e*e*0 0 0 0 不唯一，当然不唯一，当然不唯一，当然不唯一，当然 e*e*e*e*越小越具有参考价值。越小越具有参考价值。越小越具有参考价值。越小越具有参考

9、价值。海军航空工程学院二0五教研室1.2.2 误差与有效数字2 1 1误差的定义误差的定义 相对误差相对误差 /*relative error*/x 的的相对误差上限相对误差上限/*relative accuracy*/定义为定义为注：从注：从注：从注：从 的定义可见，的定义可见，的定义可见，的定义可见，实际上被实际上被实际上被实际上被偷换偷换偷换偷换成了成了成了成了 ，而后才考察，而后才考察，而后才考察，而后才考察其上限。那么这样的偷换是否其上限。那么这样的偷换是否其上限。那么这样的偷换是否其上限。那么这样的偷换是否合法合法合法合法？严格的说法是，严格的说法是，严格的说法是，严格的说法是，与

10、与与与 是否反映了是否反映了是否反映了是否反映了同一数量级同一数量级同一数量级同一数量级的误差？的误差？的误差？的误差？关于此问题的详细讨论可见教材。关于此问题的详细讨论可见教材。关于此问题的详细讨论可见教材。关于此问题的详细讨论可见教材。海军航空工程学院二0五教研室1.2.2 误差与有效数字3 2 2有效数字有效数字 用科学计数法，记用科学计数法，记 （其中（其中 ）。若）。若 （即（即 的截取按四舍五入规则），则称的截取按四舍五入规则），则称 为有为有n 位有效数字，精确到位有效数字，精确到 。例：例：问：问：有几位有效数字？有几位有效数字？证明：证明：有有 位有效数字，精确到小数点后第位

11、有效数字，精确到小数点后第 位。位。43海军航空工程学院二0五教研室1.2.2 误差与有效数字误差与有效数字4 4 3.有效数字与相对误差的关系有效数字与相对误差的关系 有效数字有效数字 相对误差限相对误差限已知已知 x*有有 n 位位有效数字有效数字，则其，则其相对误差限相对误差限为为海军航空工程学院二0五教研室1.2.2 误差与有效数字误差与有效数字5 5 相对误差限相对误差限 有效数字有效数字已知已知 x*的的相对误差限相对误差限可写为可写为则则可见可见 x*至少至少有有 n 位位有效数字有效数字。海军航空工程学院二0五教研室1.2.2 误差与有效数字64.函数的误差估计函数的误差估计

12、/*Error Estimation for Functions*/问题问题：对于：对于 y =f(x)，若用若用 x*取代取代 x，将对将对y 产生什么影响？产生什么影响？分析分析：e*(y)=f(x*)f(x)e*(x)=x*x=f()(x*x)x*与与 x 非常接近时，可认为非常接近时，可认为 f()f(x*)，则有：则有：|e*(y)|f(x*)|e*(x)|即：即：x*产生的误差经过产生的误差经过 f 作用后被放大作用后被放大/缩小了缩小了|f(x*)|倍。故称倍。故称|f(x*)|为为放大因子放大因子 或或 绝对条件数绝对条件数海军航空工程学院二0五教研室1.2.2 误差与有效数字

13、误差与有效数字7 7 相对误差条件数相对误差条件数 f 的条件数在某一点是的条件数在某一点是小小大大，则称，则称 f 在该点是在该点是好条件的好条件的 坏条件的坏条件的。注：关于多元函数注：关于多元函数 的讨论，请参阅教材。的讨论，请参阅教材。海军航空工程学院二0五教研室1.2.3 1.2.3 数值计算中应注意的几个原则数值计算中应注意的几个原则1 1 1.1.关于数值稳定性的算法。关于数值稳定性的算法。一一个个程程序序往往往往要要进进行行大大量量的的四四则则运运算算才才能能得得出出结结果果,每每一一步步的的运运算算均均会会产产生生舍舍入入误误差差。在在运运算算过过程程中中,舍舍入入误误差差能

14、能控控制制在在某某个个范范围围内内的的算算法法称称之之为为数数值稳定的算法值稳定的算法,否则就称之为不稳定的算法。否则就称之为不稳定的算法。海军航空工程学院二0五教研室1.2.3 1.2.3 数值计算中应注意的几个原则数值计算中应注意的几个原则2 2 例：计算例：计算 公式一：公式一：注意此公式注意此公式精确精确成成立立记为记为则初始误差则初始误差海军航空工程学院二0五教研室1.2.3 1.2.3 数值计算中应注意的几个原则数值计算中应注意的几个原则3 3考察第考察第n步的误差步的误差我们有责任改变。我们有责任改变。造成这种情况的是造成这种情况的是不稳定的算法不稳定的算法 /*unstable

15、 algorithm*/迅速积累，误差呈递增走势。迅速积累，误差呈递增走势。可见初始的小扰动可见初始的小扰动 公式二：公式二：注意此公式与公式一注意此公式与公式一在理论上在理论上等价等价。方法：先估计一个方法：先估计一个IN,再反推要求的再反推要求的In(n N)。可取可取海军航空工程学院二0五教研室1.2.3 1.2.3 数值计算中应注意的几个原则数值计算中应注意的几个原则4 4取取海军航空工程学院二0五教研室1.2.3 1.2.3 数值计算中应注意的几个原则数值计算中应注意的几个原则5 5 考察反推一步的误差：考察反推一步的误差：以此类推，对以此类推，对 n 1n1时）。时）。写成递归函数

16、有：写成递归函数有：intint fib(intfib(int n)n)if(n=0)return 0;if(n=0)return 0;if(n=1)return 1;if(n=1)return 1;if(n1)return fib(n-1)+fib(n-2);if(n1)return fib(n-1)+fib(n-2);海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-递归法递归法3 3 递递归归算算法法的的执执行行过过程程分分递递推推和和回回归归两两个个阶阶段段。在在递递推推阶阶段段，把把较较复复杂杂的的问问题题（规规模模为为n n）的的求求解

17、解推推到到比比原原问问题题简简单单一一些些的的问问题题（规规模模小小于于n n）的的求求解解。例例如如本本题题中中，求求解解fib(n)fib(n)，把把它它推推到到求求解解fib(n-1)fib(n-1)和和fib(n-2)fib(n-2)。也也就就是是说说，为为计计算算fib(n)fib(n)，必必须须先先计计算算fib(n-1)fib(n-1)和和fib(n-fib(n-2)2)，而而计计算算fib(n-1)fib(n-1)和和fib(n-2)fib(n-2)，又又必必须须先先计计算算fib(n-3)fib(n-3)和和fib(n-4)fib(n-4)。依依次次类类推推，直直至至计计算算

18、fib(1)fib(1)和和fib(0)fib(0)，分分别别能能立立即即得得到到结结果果1 1和和0 0。在在递递推推阶阶段段，必必须须要有终止递归的情况。要有终止递归的情况。海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-递归法递归法4 4 在编写递归函数时要注意，函数中的局部变在编写递归函数时要注意，函数中的局部变量和参数只局限于当前调用层，当递推进入量和参数只局限于当前调用层，当递推进入“简简单问题单问题”层时，原来层次上的参数和局部变量便层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列被隐蔽起来。在一系列“简单问题简单问题”层，它

19、们各层，它们各有自己的参数和局部变量。有自己的参数和局部变量。由于递归引起一系列的函数调用，并且可能由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如计算斐算法时，通常按递推算法编写程序。例如计算斐波那契数列的第波那契数列的第n n项的函数项的函数fib(n)fib(n)应采用递推算法，应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计

20、算出要求的第计算出下一项，直至计算出要求的第n n项。项。海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-回溯法回溯法1 1 回回溯溯法法也也称称为为试试探探法法，该该方方法法首首先先暂暂时时放放弃弃关关于于问问题题规规模模大大小小的的限限制制，并并将将问问题题的的候候选选解解按按某某种种顺顺序序逐逐一一枚枚举举和和检检验验。当当发发现现当当前前候候选选解解不不可可能能是是解解时时，就就选选择择下下一一个个候候选选解解；倘倘若若当当前前候候选选解解除除了了还还不不满满足足问问题题规规模模要要求求外外，满满足足所所有有其其他他要要求求时时，继继续续

21、扩扩大大当当前前候候选选解解的的规规模模，并并继继续续试试探探。如如果果当当前前候候选选解解满满足足包包括括问问题题规规模模在在内内的的所所有有要要求求时时，该该候候选选解解就就是是问问题题的的一一个个解解。在在回回溯溯法法中中，放放弃弃当当前前候候选选解解，寻寻找找下下一一个个候候选选解解的的过过程程称称为为回回溯溯。扩扩大大当当前前候候选选解解的的规规模模，以以继继续续试探的过程称为向前试探。试探的过程称为向前试探。海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-回溯法回溯法2 2【问题问题】组合问题组合问题问问题题描描述述：找找出出从从自自

22、然然数数1 1，2 2，n n中中任任取取r r个数的所有组合。个数的所有组合。采采用用回回溯溯法法找找问问题题的的解解，将将找找到到的的组组合合以以从从小小到到大大顺顺序序存存于于a0a0，a1a1，ar-1ar-1中中，组组合合的元素满足以下性质：的元素满足以下性质：（1 1）ai+1aiai+1ai，后一个数字比前一个大；后一个数字比前一个大；（2 2）ai-i=n-r+1ai-i=n-r+1。海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-回溯法回溯法3 3 首首先先放放弃弃组组合合数数个个数数为为r r的的条条件件，候候选选组组合合从从

23、只只有有一一个个数数字字1 1开开始始。因因该该候候选选解解满满足足除除问问题题规规模模之之外外的的全全部部条条件件，扩扩大大其其规规模模，并并使使其其满满足足上上述述条条件件（1 1），候候选选组组合合改改为为1 1，2 2。继继续续这这一一过过程程，得得到到候候选选组组合合1 1，2 2，3 3。该该候候选选解解满满足包括问题规模在内的全部条件，因而是一个解。足包括问题规模在内的全部条件，因而是一个解。在在该该解解的的基基础础上上，选选下下一一个个候候选选解解，因因a a 22上上的的3 3调调整整为为4 4，以以及及以以后后调调整整为为5 5都都满满足足问问题题的的全全部部要要求求，得得

24、到到解解1 1，2 2，4 4和和1 1，2 2，5 5。由由于于对对5 5不不能能再再作作调调整整，就就要要从从a2a2回回溯溯到到a1a1，这这时时，a1=2a1=2，可可以以调调整整为为3 3，并并向向前前试试探探，得到解得到解1 1，3 3，4 4。重重复复上上述述向向前前试试探探和和向向后后回回溯溯，直直至至要要从从a0a0再再回回溯溯时，说明已经找完问题的全部解。时，说明已经找完问题的全部解。海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-回溯法回溯法4 4运用回溯法解题通常包含以下三个步骤：运用回溯法解题通常包含以下三个步骤：（1

25、1）针对所给问题，定义问题的解空间；）针对所给问题，定义问题的解空间；（2 2）确定易于搜索的解空间结构；）确定易于搜索的解空间结构；（3 3）以以深深度度优优先先的的方方式式搜搜索索解解空空间间，并并且且在在搜搜索过程中用剪枝函数避免无效搜索；索过程中用剪枝函数避免无效搜索；海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-回溯法回溯法5 5 【问题问题】n n皇后问题皇后问题问问题题描描述述：求求出出在在一一个个nnnn的的棋棋盘盘上上，放放置置n n个个不能互相捕捉的国际象棋不能互相捕捉的国际象棋“皇后皇后”的所有布局。的所有布局。海军航空工

26、程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-贪婪法贪婪法1 1 贪贪婪婪法法是是一一种种不不追追求求最最优优解解，只只希希望望得得到到较较为为满满意意解解的的方方法法。贪贪婪婪法法一一般般可可以以快快速速得得到到满满意意的的解解，因因为为它它省省去去了了为为找找最最优优解解要要穷穷尽尽所所有有可可能能而而必必须须耗耗费费的的大大量量时时间间。贪贪婪婪法法常常以以当当前前情情况况为为基基础础作作最最优优选选择择，而而不不考考虑虑各各种种可可能能的的整整体体情情况况，所以贪婪法不要回溯。所以贪婪法不要回溯。海军航空工程学院二0五教研室1.3.3 1.3.3

27、 算法算法-算法设计基本方法算法设计基本方法-贪婪法贪婪法2 2 例例如如平平时时购购物物找找钱钱时时，为为使使找找回回的的零零钱钱的的硬硬币币数数最最少少，不不考考虑虑找找零零钱钱的的所所有有各各种种方方案案，而而是是从从最最大大面面值值的的币币种种开开始始，按按递递减减的的顺顺序序考考虑虑各各币币种种，先先尽尽量量用用大大面面值值的的币币种种，当当不不足足大大面面值值币币种种的的金金额额时时才才去去考考虑虑下下一一种种较较小小面面值值的的币币种种。这这就就是在使用贪婪法。是在使用贪婪法。这这种种方方法法在在这这里里并并不不总总是是最最优优，是是因因为为银银行行对对其其发发行行的的硬硬币币种

28、种类类和和硬硬币币面面值值的的巧巧妙妙安安排排。如如只只有有面面值值分分别别为为1 1、5 5和和1111单单位位的的硬硬币币，而而希希望望找找回回总总额额为为1515单单位位的的硬硬币币。按按贪贪婪婪算算法法，应应找找1 1个个1111单单位位面面值值的的硬硬币币和和4 4个个1 1单单位位面面值值的的硬硬币币，共共找找回回5 5个硬币。但最优的解应是个硬币。但最优的解应是3 3个个5 5单位面值的硬币。单位面值的硬币。海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-分治法分治法1 1 任任何何一一个个可可以以用用计计算算机机求求解解的的问问题

29、题所所需需的的计计算算时时间间都都与与其其规规模模N N有有关关。问问题题的的规规模模越越小小，越越容容易易直直接接求求解解，解解题题所所需需的的计计算算时时间间也也越越少少。例例如如，对对于于n n个个元元素素的的排排序序问问题题，当当n=1n=1时时，不不需需任任何何计计算算；n=2n=2时时，只只要要作作一一次次比比较较即即可可排排好好序序；n=3n=3时时只只要要作作3 3次次比比较较即即可可，。而而当当n n较较大大时时，问问题题就就不不那那么么容容易易处处理理了了。要要想想直直接接解解决决一一个个规规模模较较大大的问题，有时是相当困难的。的问题，有时是相当困难的。分分治治法法的的设

30、设计计思思想想是是，将将一一个个难难以以直直接接解解决决的的大大问问题题，分分割割成成一一些些规规模模较较小小的的相相同同问问题题，以以便各个击破，分而治之。便各个击破，分而治之。海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-分治法分治法2 2【问题问题】循环赛日程表循环赛日程表 问问题题描描述述：设设有有n=2n=2k k个个运运动动员员要要进进行行网网球球循循环环赛。现要设计一个满足以下要求的比赛日程表：赛。现要设计一个满足以下要求的比赛日程表：（1 1）每个选手必须与其他）每个选手必须与其他n-1n-1个选手各赛一次；个选手各赛一次；（2

31、 2）每个选手一天只能参赛一次；）每个选手一天只能参赛一次；（3 3）循环赛在）循环赛在n-1n-1天内结束。天内结束。请请按按此此要要求求将将比比赛赛日日程程表表设设计计成成有有n n行行和和n-1n-1列列的的一一个个表表。在在表表中中的的第第i i行行，第第j j列列处处填填入入第第i i个个选选手手 在在 第第 j j天天 所所 遇遇 到到 的的 选选 手手。其其 中中 1in1in，1jn-11jn-1。海军航空工程学院二0五教研室1.3.3 1.3.3 算法算法-算法设计基本方法算法设计基本方法-分治法分治法3 3 按按分分治治策策略略，我我们们可可以以将将所所有有的的选选手手分分

32、为为两两半半，则则n n个个选选手手的的比比赛赛日日程程表表可可以以通通过过n/2n/2个个选选手手的的比比赛赛日日程程表表来来决决定定。递递归归地地用用这这种种一一分分为为二二的的策策略略对对选选手手进进行行划划分分，直直到到只只剩剩下下两两个个选选手手时时，比比赛赛日日程程表表的的制制定定就就变变得得很很简简单单。这这时时只只要要让让这这两个选手进行比赛就可以了。两个选手进行比赛就可以了。海军航空工程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A*算法算法 一种启发式搜索算法一种启发式搜索算法在在解解决决问问题题的的时时候候常常常常会会估估计计状

33、状态态离离目目标标到到底底有有多多接接近近，进进而而对对多多种种方方案案进进行行选选择择，把把这这这这种种方方法法用用到到搜搜索索中中来来，可可以以用用一一个个状状态态的的估估价价函函数数来来估估计计它它到到目目标标状状态态的的距距离离。这这个个估估计计函函数数和和问问题息息相关，体现了一定的智能。题息息相关，体现了一定的智能。F(s)=H(s)+G(s)F(s)=H(s)+G(s)ss问题的任何一种状态问题的任何一种状态HsHs的估价函数的估价函数GG到达到达s s状态之前的代价状态之前的代价FsFs的启发函数，也就是到达目标的总代价的启发函数，也就是到达目标的总代价 的估计的估计海军航空工

34、程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A*算法算法【问题问题】移动绿色方块到达红色方块移动绿色方块到达红色方块海军航空工程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A*算法算法海军航空工程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A*算法算法海军航空工程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A*算法算法海军航空工程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A

35、*算法算法海军航空工程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A*算法算法海军航空工程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A*算法算法1 1、增加开始方块到待扩展列表中、增加开始方块到待扩展列表中2 2、重复以下过程、重复以下过程1 1）在在待待扩扩展展列列表表中中，找找到到F F值值最最低低的的方方块块，并并将它做为当前方块将它做为当前方块2 2）将当前方块放置到已扩展列表中）将当前方块放置到已扩展列表中3 3）对于当前方块的）对于当前方块的8 8个相邻方块个相邻方块如如果果是是障障碍碍物物或

36、或已已在在已已扩扩展展列列表表中中，则则忽忽略略，否否则则如如果果它它不不在在待待扩扩展展列列表表中中，则则将将其其加加入入到到待待扩扩展展列列表表中中，并并将将其其父父方方块块设设为为当当前前方方块块，并并计计算算其其G G，H H和和F F值值；如如果果它它已已在在待待扩扩展展列列表表中中，则则利利用用G G值，计算其是否是一种更好的选择。值，计算其是否是一种更好的选择。海军航空工程学院二0五教研室1.3.4 1.3.4 算法算法-算法设计基本方法算法设计基本方法-A-A*算法算法4 4）搜索停止，当下列条件满足：）搜索停止，当下列条件满足：a)a)目标方块被放进待扩展列表中目标方块被放进

37、待扩展列表中找到路径找到路径或或b)b)直直到到待待扩扩展展列列表表空空也也没没有有发发现现目目标标方方块块寻径失败。寻径失败。3 3、保保存存路路径径从从目目标标方方块块开开始始，依依次次找找到到其其父方块，串在一起即为求解路径。父方块，串在一起即为求解路径。海军航空工程学院二0五教研室1.3.5 1.3.5 算法算法-算法设计基本方法算法设计基本方法-工兵寻径工兵寻径海军航空工程学院二0五教研室1.3.5 1.3.5 算法算法-算法设计基本方法算法设计基本方法-工兵寻径工兵寻径当当要要行行走走工工兵兵时时，首首先先判判断断该该工工兵兵是是否否在在铁铁路路线线上上，如如果果不不在在铁铁路路线

38、线上上且且目目标标位位置置与与当当前前位位置置相相邻邻，则则可可以以到到达达目目的的地地，否否则则则则不不然然；如如果果工工兵兵在在铁铁路路线线上上，则则调调用用工工兵兵自自动动寻寻径径算算法法，考考察察工兵是否可以到达目的地。工兵是否可以到达目的地。海军航空工程学院二0五教研室1.3.5 1.3.5 算法算法-算法设计基本方法算法设计基本方法-工兵寻径工兵寻径在在工工兵兵自自动动寻寻径径过过程程中中，根根据据其其当当前前位位置置、目目标标位位置置和和用用来来寻寻径径的的一一个个工工兵兵关关键键位位置置，进进行行递递归归寻寻径径。通通过过上上述述分分析析，我我们们知知道道工工兵兵关关键键位位置

39、置分分为为两两种种情情况况，一一种种关关键键位位置置在在棋棋盘盘四四角角区区域域中中，另另一一种种在在中中间间区区域域中中。如如果果是是前前者者，又又分分为为三三种种情情况况，关关键键位位置置在在每每个个角角区区域域第第一一行行的的左左端端、中中间间和和右右端端。关关键键位位置置在在左左端端时时，首首先先判判断断当当前前位位置置和和目目标标位位置置是是否否相相邻邻，如如果果相相邻邻，则则可可以以到到达达目目的的地地，否否则则，转转到到以以当当前前位位置置左左侧侧棋棋盘盘一一角角的的右右上上角角关关键键位位置置、当当前前区区域域中中间间关关键键位位置置和和当当前前区域右端关键位置进行递归寻径。区

40、域右端关键位置进行递归寻径。海军航空工程学院二0五教研室1.3.6 1.3.6 算法算法-算法设计基本方法算法设计基本方法-数值法数值法1 1 尽尽管管许许多多实实际际问问题题的的求求解解有有现现成成的的公公式式化化或或固固定定的的直直接接解解法法，例例如如，五五次次以以下下的的多多项项式式方方程程有有公公式式解解法法，计计算算定定积积分分有有牛牛顿顿-莱莱布布尼尼兹兹公公式式等等，但但工工程程上上的的绝绝大大多多数数实实际际问问题题还还没没有有解解析析解解，或或者者很很难难用用解解析析的的方方法法来来求求解解。例例如如，五五次次以以上上的的多多项项式式方方程程目目前前还还没没有有有有效效的的

41、公公式式解解法法，所所有有的的超超越越方方程程更更是是没没有有公公式式解解；当当被被积积函函数数的的源源函函数数不不能能用用初初等等函函数数表表示示时时，无无法法利利用用牛牛顿顿-莱莱布布尼尼兹兹公式计算定积分。公式计算定积分。海军航空工程学院二0五教研室1.3.6 1.3.6 算法算法-算法设计基本方法算法设计基本方法-数值法数值法2 2 有有的的问问题题虽虽然然有有解解析析解解，但但由由于于函函数数关关系系太太复复杂杂，或或者者实实际际上上不不能能用用，因因而而也也没没有有实实用用价价值值。因因此此，用用数数值值法法求求解解已已成成为为计计算算机机法法的的一一种种重重要要方方法法，被被大大

42、量量地地用用于于解解决决数数值值计计算算的的问问题题。本本课课程将陆续介绍各种数值型问题的数值方法。程将陆续介绍各种数值型问题的数值方法。海军航空工程学院二0五教研室1.3.7 1.3.7 算法的复杂度算法的复杂度1 1 主要包括时间复杂度和空间复杂度主要包括时间复杂度和空间复杂度 1 1算法的时间复杂度算法的时间复杂度 是指执行算法所需要的计算工作量。是指执行算法所需要的计算工作量。为为了了能能够够比比较较客客观观地地反反映映出出一一个个算算法法的的效效率率，在在计计算算一一个个算算法法的的工工作作量量时时，不不仅仅应应该该与与所所使使用用的的计计算算机机、程程序序设设计计语语言言以以及及程

43、程序序编编制制者者无无关关，而而且且还还应应该该与与算算法法实实现现过过程程中中的的许许多多细细节节无无关关。为为此此，可可以以用用算算法法在在执执行行过过程程中中所所需需基基本本运运算算的的次数来计算算法的工作量。次数来计算算法的工作量。海军航空工程学院二0五教研室1.3.7 1.3.7 算法的复杂度算法的复杂度2 2 基基本本运运算算反反映映了了算算法法运运算算的的主主要要特特征征，因因此此，用用基基本本运运算算的的次次数数来来度度量量算算法法工工作作量量是是客客观观的的也也是是实实际际可可靠靠的的，有有利利于于比比较较同同一一问问题题的的几几种种算算法法的的优优劣劣。例例如如，在在考考虑

44、虑两两个个矩矩阵阵相相乘乘时时，可可以以将将两两个个数数之之间间的的乘乘法法运运算算作作为为基基本本运运算算，而而对对于于所所用用的的加加法法运运算算可可以以忽忽略略不不计计。又又如如，当当需需要要在在一一个个表表中中进进行行查查找找时时，可可以以将将两两个个基基本本点点元元素素之之间间的比较作为基本运算。的比较作为基本运算。海军航空工程学院二0五教研室1.3.7 1.3.7 算法的复杂度算法的复杂度3 3 算算法法所所执执行行的的基基本本运运算算次次数数还还与与问问题题的的规规模模有有关关。例例如如，两两个个2020阶阶矩矩阵阵相相乘乘与与两两个个1010阶阶矩矩阵阵相相乘乘，所所需需要要的

45、的基基本本运运算算次次数数显显然然是是不不同同的的，前前者者需需要要更更多多的的运运算算次次数数。因因此此，在在分分析析算算法法的的工工作量时，还必须对问题的规模进行度量。作量时，还必须对问题的规模进行度量。综综上上所所述述，算算法法的的工工作作量量用用算算法法所所执执行行的的基基本本运运算算次次数数来来度度量量，而而算算法法所所执执行行的的基基本本运运算算次次数是问题规模的函数，即：数是问题规模的函数，即：算法的工作量算法的工作量=f(n)=f(n)海军航空工程学院二0五教研室1.3.7 1.3.7 算法的复杂度算法的复杂度4 4在在同同一一问问题题规规模模下下，如如果果算算法法执执行行所所

46、需需的的基基本本运运算算次次数数取取决决于于某某一一特特定定输输入入时时，有有两两种种方方法法来来分析算法的工作量。分析算法的工作量。（1 1）平均性态）平均性态是是指指用用各各种种特特定定输输入入下下的的基基本本运运算算次次数数的的带带权权平均值来试题算法的工作量平均值来试题算法的工作量（2 2）最坏情况复杂性）最坏情况复杂性所所谓谓最最坏坏情情况况分分析析，是是指指在在规规模模为为N N时时，算算法法所所执行的基本运算的最大次数。执行的基本运算的最大次数。海军航空工程学院二0五教研室1.3.7 1.3.7 算法的复杂度算法的复杂度5 5 2 2算法的空间复杂度算法的空间复杂度 一一个个算算法法的的空空间间复复杂杂度度，一一般般是是指指执执行行这这个个算算法法 所所需需要要的的内内存存空空间间，包包括括算算法法程程序序所所占占的的的的空空间间、输输入入的的初初始始数数据据所所占占的的存存储储空空间间以以及及算算法法执行过程中所需要的额外空间。执行过程中所需要的额外空间。