文档介绍：补充1 常用的算法简介
1
算法
算法是解决问题方法的精确描述,但并不是所有问题都有算法,有的问题经研究可行,则有相应的算法。有些问题不能说明可行,则没有相应的算法,但不是说明这类问题没有结果。例如:猜想问题,有结果,然而目前还没有算法。上述所谓的可行,就是指算法的研究。
算法的性质
解题算法是一有穷动作序列
动作序列仅有一个初始的动作
序列中每个动作的后继动作是确定的
序列的终止表示问题得到解答或问题没有解答
算法的分类
数值算法
非数值算法
2
数值算法和非数值算法
数值算法
迭代法:迭代法适用于方程或方程组求解,使用间接方法求方程近似根的一种常用算法。
递推法:详见后页
递归法:详见后页
插值法:详见后页
差分法:通过差分方程求解微分方程近似解。
非数值算法
穷举搜索法:搜索所有可能的情形,从中找出符合要求的解。
递归法:详见后页
回溯法:详见后页
贪婪法:详见后页
分治法: 思想是把一个规模为n的问题,分解为若干个规模较小的问题,使得从这些规模较小问题的解易于构造整个问题的解。
3
递推法
递推法实际上是需要抽象为一种递推关系,然后按照递推关系式求解。递推法通常表现为两种方式:一个是简单到一般,另一个是将一个复杂问题逐步推到一个已知的简单的问题。这两种方式反映了两种不同的递推方向,前者往往用于计算级数,后者往往于回归配合成为递归。
4
插值法
插值法称为内插法。往往只知道它在某区间中若干点的函数值,这时候做出适当的特定的函数,使得在这些点上取已知值,并且在这区间内其他各点上就用这特定函数所取的值作为函数f(x)的近似值,这种方法成为插值法。如果这个特定函数是多项式,就称为"插值多项式"或"内插多项式"
5
贪婪法
贪婪法是一种可以快速的得到满意解(但不一定是最优解)的方法。方法的"贪婪"性反映在对当前的情况,总是做最大限度的选择。即满足条件的均选人,然后分别展开,最后选得一个问题得解。这个方法不考虑回溯,也不考虑每次选择是否符合最优解的条件,但最终能得到接近最优结果的选择
货郎担问题
背包问题
"背包问题"的基本描述是:有一个背包,能盛放的物品总重量为 S,设有 N 件物品,其重量分别为w1,w2,...,wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品的重量之和等于 S 。
6
回溯法
回溯法是一种选优的搜索方法,按照选优的条件向前搜索,以达到目标,但是当搜索到某一步的时候,发现原先的选择并不优或者达不到目标,就退回一步重新选择,这种走不通就退回再走的技术就是回溯法。
八皇后问题(也可以用递归等其他算法求解)
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8*8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。
四色问题(也可以用递归等其他算法求解)
人们在实践中得到的结论是:在每张地图上,最多使用四种颜色,就能给所有公共边界的地区着上不同的颜色。
实践中有这样的结果,要在理论上予以证明却不那么容易。这是数学史上的一个困扰人们多年的著名难题。为了圆满地解决图着色问题,人们已经奋斗了一百多
7
递归算法(重点掌握)
递归是一种特别有用的工具,不仅在数学中广泛应用,在日常生活中也常常遇到。
8
递归算法
在数学中几个熟知的数学定义:
(2) 若t1,t2是树,则也是树
9
递归
递归算法包括递推和回归两部分:
递推
就是为了得到问题的解,将它推到比原问题更简单的问题求解。
例如:n!=f(n),为了计算f(n),将它推到比原问题更简单的问题f(n-1),即f(n)=f(n-1)*n,而计算f(n-1)比计算f(n)简单,因为f(n-1)比f(n)更加接近已知解0!=1
使用递推要注意
(1)递推应有终止之时,例如当n=0时,0!=1为递推终止条件,所谓终止条件就是指在此条件下问题的解时明确的,缺少终止条件会使算法失败。
(2)简单问题表示离递推终止条件更接近的问题。简单的问题与原问题其解的算法是一致的,其差别主要反映在参数上,例如,f(n-1)比计算f(n)更简单,因为f(n-1)比f(n)参数少1。参数变化使问题递推到有明确解。
10