. .
递归算法的优缺点:
1
优点:构造清晰,可读性强,而且容易用数学归纳法来证明算法的正确性,因此它为设计○
算法、调试程序带来很大方便。
2
缺点:○ 递归算法的运行效率较低,无论是消耗的计算时间还是占用的存储空间都比非递归
算法要多。
边界条件与递归方程是递归函数的二个要素
应用分治法的两个前提是问题的可分性和解的可归并性
以比较为根底的排序算法的最坏倩况时间复杂性下界为 0(n·log2n)。
回溯法以深度优先的方式搜索解空间树 T,而分支限界法那么以广度优先或以最小消耗优先
的方式搜索解空间树 T。
舍伍德算法设计的根本思想:
设 A 是一个确定性算法,当它的输入实例为 x 时所需的计算时间记为 tA(x)。设 Xn 是
算法 A 的输入规模为 n 的实例的全体,那么当问题的输入规模为 n 时,算法 A 所需的平均
时间为
这显然不能排除存在 x∈Xn 使得 的可能性。希望获得一个随机化算法
B,使得对问题的输入规模为 n 的每一个实例均有
拉斯维加斯( Las Vegas )算法的根本思想:
设 p(x)是对输入 x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算
法应该对所有输入
t
A
(n)
t
A
(x)
x
/ |
均有
X
n
|
p(x)>0。
xX
设 t(x)是算法 obstinate 找到具体实例 x 的一个解所需的平均时间 ,s(x)和 e(x)分别是算法对于
n
具体实例 x 求解成功或求解失败所需的平均时间,那么有:
解此方程可得:
t
B
( x ) t
A
( n ) s ( n )
蒙特卡罗(Monte Carlo)算法的根本思想:
设 p 是一个实数,且 1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概
率不小于 p,那么称该蒙特卡罗算法是 p 正确的,且称 p-1/2 是该算法的优势。
如果对于同一实例,蒙特卡罗算法不会给出 2 个不同的正确解答,那么称该蒙特卡罗算法是
一致的。
线性规划根本定理:如果线性规划问题有最优解,那么必有一根本可行最优解。
e(x) t(x))t(x) p(x)s(x) (1 p(x))(
单纯形算法的特点是:
1 p ( x )
t ( x ) s ( x ) e ( x )
p ( x )
〔1〕只对约束条件的假设干组合进展测试,测试的每一步都使目标函数的值增加;
〔2〕一般经过不大于 m 或 n 次迭代就可求得最优解。
单纯形算法的根本思想就是从一个根本可行解出发,进展一系列的根本可行解的变换。每次
变换将一个非根本变量与一个根本变量互调位置,且保持当前的线性规划问题是一个与原问
题完全等价的标准线性规划问题。
图灵机由以下几局部组成:一条无限长的带〔有无穷个格子〕、一个读写头、一个有限状态
控制器以及一个程序。
NPC 形式化定义:
定义 1:语言 L 是 NP 完全的当且仅当〔1〕 L【NP;〔2〕对于所有 L’【NP 有 L’ ~pL。
如果有一个语言 L 满足上述性质(2),但不一定满足性质〔1〕,那么称该语言是 NP 难的。
所有 NP 完全语言构成的语言类称为 NP 完全语言类,就是 NPC。
定理 1 设 L 是 NP 完全的,那么〔1〕L P 当且仅当 P=NP;〔2〕假设 L p L1,且 L1
NP,那么 L1 是 NP 完全的。
团问题:
任给图 G 和整数 k.试判定图 G 中是否存在具有 k 个顶点的团.
. v .