中国科普博览-亚博安卓

数学技术之算法概述篇(8)

6.算法分类及其简介

对数学技术中的方法和算法进行合理、有效与清晰的分类，很重要，但并不容易，也不简单，研究得到的结果甚多，因此也就有各种各样的把方法和算法进行分类的标准及分类结果。如把算法按结构类型分为基本算法、数据结构算法、数论与代数算法、计算几何算法、图论算法、动态规划以及数值分析算法、加密算法、排序算法、检索算法、随机化算法、并行算法等等。再如把算法按计算结果分为两类：确定性算法，计算结果常取决于输入值；非确定算法，对于一个或一组给定的输入值，算法的结果并不是唯一的或确定的。又如把算法按计算类型分为数值型算法、非数值型算法和混合型算法三种：对一个数学问题求数值解，属数值型算法，如方程求根、矩阵计算、线代数方程组求解、数值积分、微分方程求解等；非数值型算法也不少，如数据排序算法、检索查询算法等。非数值型算法应用十分广泛，如图书检索、人事管理、文字处理、模式匹配等；混合型算法更多。实际上，解决实际问题中利用的算法，既有数值型算法、又有非数值型算法，多是混合的。
在计算机程序设计中，数据形式的表示主要有两大类：数值型和字符型(非数值型)。数值型数据是指定义成数值形式的数据。这种数据可以直接进行加、减、乘、除等运算，运算的结果还是数值型的，所表达的是实数，具有计算上的意义。另一种数据形式为非数值型的数据，如字符型数据，所表达的是字符，如‘a’，‘b’，‘c‘等等，具有存储意义。
在计算机中可以识别的字符，一般都对应于一个asii码，asii码为数值型的数据。asii码值的改变，对应的字符也会改变。所以，非数值型的数据，本质上也是数值型的数据。为了接近人的思维习惯，方便程序的编写，计算机高级语言，划分了数据的类型：
数值型数据有：实型数（含整型数，定点数，浮点数，单精度和双精度类数等）和复型数两大类；非数值型数据类型更多，有：字符型，布尔型，字符串型等。
计算机上，可用的数值型算法很多。在求解方程的算法中，常用的算法之一是迭代法，也叫逐次逼近法。迭代法的计算比较简单，也比较容易在计算机上编程实现。求方程组的近似解要选择适当的迭代公式和初值，使得收敛速度快、误差小。在线代数方程组的解法中，常用的有塞德尔迭代法、共轭斜量法、超松弛迭代法等。
在计算方法中，数值逼近也是常用的基本算法，就是用简单的函数、在误差允许范围内、代替比较复杂的函数，或者代替不能用解析表达式表示的函数。
微分方程的数值解法也是近似算法。常微分方程的算法有欧拉算法、龙格-库塔方法、阿塔姆斯方法。偏微分方程的初值问题或边值问题，目前常用的是有限差分法、有限元素法等。有限差分法的基本思想是用离散的、只含有限个未知数的差分方程去代替连续变量的微分方程和定解条件，求出差分方程的解作为所求偏微分方程的近似解。
蒙特卡罗方法，又称统计模拟方法，是一类基于“随机数”的计算方法，常用于高维非线性问题的计算。
算法与计算机的发展相辅相成，相互促进。大量数值计算的需要，促使计算机体系结构及性能不断更新，而计算机的发展又推动着算法的发展，如并行机和并行算法就是其中的一例。为适应现代计算机的飞速发展，对算法提出了新的要求，对原有算法提出了重新评价、筛选、改造和创新。与此同时，也涌现了许多新概念、新方法，它们技巧性强，在时间复杂度、空间复杂度和计算精度等方面各占一定优势，应用广泛，效果显著，如快速傅立叶变换算法fft等。
算法和不同学科结合，出现了不少具有学科特点的算法，如计算力学、计算物理、计算化学、计算经济学等。
因此如何简单、方便、有效地介绍算法就成为一个问题。下面拟以三个方面向大家介绍算法：① 按照算法思路分类进行介绍，② 按常用算法逐一进行介绍，③ ？按算法应用领域进行解释，供参考。
下面按算法的基本思路进行分类并对其进行一些简单介绍。
1？迭代法
迭代法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。迭代法常用于求方程或方程组根的近似求解。
2？递推法
递推法是根据具体问题，建立递推关系，再通过递推关系求解的方法。其中递推关系是表示关于正整数参变量的一类特殊关系，从给定的初值出发，通过这种关系一步一步地通过递推获得所需结果。这种递推通常采用循环迭代的方法，如循环累乘、循环累加等。
3？递归法
程序调用自身的编程技巧称为递归（recursion）。一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归算法解题通常很简洁，但是由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，所以递归算法的执行效率相对较低。一般来说，递归要有、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
4？穷举法
穷举法是编程中常用到的一种方法，通常在找不到解决问题的规律时对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。
5？回溯法
回溯法是一种选优的搜索方法，按照选优的条件向前搜索，以达到目标，但是当搜索到某一步的时候，发现原先的选择并不优或者达不到目标，就退回一步重新选择，这种走不通就退回再走的技术就是回溯法。
6？贪心法
贪心法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
实现该算法的过程：1)？从问题的某一初始解出发；2)？当能朝给定总目标前进一步执行；3)？求出可行解的一个解元素；4)？由所有解元素组合成问题的一个可行解。
7 分支界限法
是一个用途十分广泛的算法，运用这种算法的技巧性很强，不同类型的问题解法也各不相同。
分支界限法的基本思想是对有的的所有（数目有限）空间进行搜索。该算法在具体执行时，把全部可行的不断分割为越来越小的（称为分支），并为每个子集内的解的值计算一个下界或（称为定界）。在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支，这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。这一过程一直进行到找出为止，该可行解的值不大于任何子集的界限。因此这种算法一般可以求得。
与一样，这种方法也是用来为问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其比高，但它的优点是与类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法更高。
8 分治法
分治法就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解就是诸子问题的解的合并。分治法的基本步骤：
1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；
3）合并：将各个子问题的解合并为原问题的解。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。
9 动态规划法
是一种在数学和中使用的、用于求解包含重叠子问题的最优化问题的方法。其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。
动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此读者在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。