@markheng 2017-01-10T08:57:29.000000Z 字数 4097 阅读 2165

算法复习

算法设计与分析

算法效率

问题的下界
$O()$ 和 $\Omega()$

$O$ 表示上界，最坏情况的时间复杂度
$\Omega$ 表示最优情况的时间复杂度，是下界
$\Theta$ 表示确界，包含最优和最坏两种情况

随机算法

算法的性能比（W12）

r (s a) = f ( s a ) f ( s * ), s * 是 最 佳 解

$r(s_a) = \frac{f(s_a)}{f_(s^*)},s^*是最佳解$
对于问题的所有实例，它们可能的

r(sa) $r(s_a)$ 的最佳（也就是最低）上界，被称为该算法的性能比，计作

RA $R_A$
性能比是一个来指出近似算法质量的主要指标，我们需要那些

RA $R_A$ 尽量接近1的近似算法。

随机算法
它是在接收输入的同时，为了随机选择的目的，还接收一串随机比特流并且在运行过程中使用该比特流的算法。

蒙特卡洛算法和拉斯维加斯算法
都是随机算法
MonteCarlo算法总产生解，正确或者错误的都有
LasVegas算法产生正确解，或者没有解

随机化快速排序
快速排序的效率为 $O(n log n)$ ,最坏为 $O(n^2)$
随机化快排是随机排列序列中的元素或者随机选择主元，这样算法就不依赖于输入数列的顺序。
效率为 $O(nlogn)$

算法思想

分治策略的两种情形

图书馆找书子问题的解即问题的解
评三好学生子问题结果需要整合处理（合并）

分治策略的变种

二分法
分解并在解决之前合并法divide and marriage before conquest:
A variant of divide and conquer in which subproblems created in the "divide" step are merged before the "conquer" step.
管道传输分治法pipelined divide and conquer:
A divide and conquer paradigm in which partial results from recursive calls can be used before the calls complete. The technique is often useful for reducing the depth of an algorithm.

二分搜索
二分搜索在已排序的数组中搜索某个元素所执行的元素比较次数不超过 $(\lfloor log n\rfloor + 1)$ ,复杂度为 $O(log n)$

减治法的三种变形 W5

减去一个常量(a constant) DFS，BFS
减去一个常数因子(a constant factor) 折半查找
减去的规模是可变的(variable size desrease) 二分查找

变治思想 W5

转变为同样问题的一个更简单或者更方便的实例——实例化简, 预排序，红黑，分裂等AVL树的查找都是相当于对二叉树进行了预处理，方便查找
变换为同样实例的不同表现——改变表现，2-3树，2-3-4树查找，堆排序，化简为线性规划问题
改变为另一个问题的实例，这种问题的算法是已知的问题的简化——问题化简LCM最小公约数

数据结构

AVL树
2-3树

AVL树
在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。
2-3树
2–3树是平衡树，意味着右边，左边，中间的子树的元素数量都是相同或接近的。

多项式近似

多项式近似方案
PAS、FPAS
多项式等价

多项式时间: 时间复杂度表示为数据规模的多项式
伪多项式时间: 时间复杂度表示为输入数据数值规模N的多项式，但是运行时间却与N的二进制成指数关系，这样的时间复杂度的算法称为伪多项式时间的算法。
多项式等价: 如果一个问题能够在多项式时间解决，同时另一个问题就也能够被解决，那么就称这两个问题为多项式等价地问题

判定问题并不总是多项式相等于对应的优化问题。

每个优化问题均伴随着几个判定问题，我们希望找到其中与优化问题多项式等价的。

多数问题均有其响应的多项式等价的判定问题，所以NP完备性也适用于优化问题的复杂性评估。

问题归约
如果可以使用求解P2的算法为子程序求解P1，则称P1归约为P2。、
有P2至少跟P1一样难

多项式归约
P2的解法用于P1花费了单位时间，则称为多项式归约

问题转换
是一种特殊的归约

对于P1的每一个实例I1 均可在多项式时间内构造P2 的一个实例I2，使得

当且仅当I2为肯定实例时， I1为肯定实例。

则称P1多项式转化为P2。

若P1多项式时间转化为P2，P2 至少与P1 一样难；但不表明P1与P2一样难

P和NP问题

启发式算法: 通过计算的代价来找到最优解，而不保证灵活和最优性，很多情况下又来表述一个可行解是多么地接近最优解
NP问题的难度
P类和NP类问题
P类; 如果判别问题P1存在多项式算法，那么P1即属于P类问题
NP类: 判别问题P1属于NP类问题，当P1中的每一个肯定实例都有一个多项式的验证。
we say that a recognition problem P1 is in the class NP, if for every yes instance I of P1, there is a short (i.e., polynomial length) verification that the instance is a yes instance.
NP正式化定义: P1属于NP，如果证书检验算法和多项式p (▪) 满足
- P1的每一个肯定实例I均有一证书CR(I);
- AL能在p(│I│) 时间内验证CR(I) 的正确性

P中所有问题属于NP

NP完备性 NP-completeness: 表露一些没有有效算法的问题是等价的，如果能够对这类问题中的一个设计出有效算法，那么就能都对其它的每一个问题设计有效算法，把这类“计算上等价”的问题，称为NP完备性问题。

NP完备问题：难，且没有有效算法

P1是NP完备的，当
1. P1属于NP，且
2. 所有其他NP的问题可以多项式转化为P1

NP完备问题举例

汉密尔顿回路

划分问题

3覆盖问题

NP难: 判定问题P1是NP难的，当所有其他的NP类问题都能够多项式归约为P1

NP难问题比NPC要广，它包含了所有NP问题以及非NP问题

其它算法

遗传算法，依靠交叉和变异得到解
禁忌算法，禁忌期
蚁群算法
退火算法

分治法

主元素问题

参考

逆序问题

参考

动态规划

算法过程
动态规划中的决策序列

分支定界

题目样例
线路题

根据线路（l1, l2, l3,...,ln）的取舍构建一颗m层二叉搜索树。第i层的所有左分支表示铺设线路li，右分支表示不铺设。如果存在可行解，遍历此二叉树即可得到最优解。
前进：当前节点未被剪枝并且仍有子节点即可继续前进
分支：第i层左分支表示不选择路径 $l_i$ ，右分支表示选择路径 $l_i$ 。先遍历左分支，后遍历右分支。
回溯：当遍历找到问题的解时回溯，遇到被剪枝的节点，回溯。从左分支返回时，访问右分支，从右分支返回时，返回父节点。
剪枝：剪枝条件如下
- 有环路
- 当前地井数+地井数下界 > UMAX
- 当前跨区铺设线路数 + 跨区铺设线路数下界 > DMAX
- 当前费用 + 费用下界 >= 已知最优方案的费用
子问题的下界为费用下界、地井数下界、跨区线路数下界。费用下界是根据剩余站点数量定义的，累计最小的路线花费即可得到。由于限制被极度弱化，所以非常粗糙，但是正确有效。另两个下界类似。
父问题的上界是已知最优方案的费用，显然正确有效
程序代码如下

按费用从小到大排序所有路线l1,l2,...,lm
排序计算子问题下界：
    1。地井数下界：剩余站点数量->最小地井数
    2。跨区线路数下界：剩余站点数量->最小跨区线路数
search(空集, l1)
返回最优结果
def search(线路集合S，当前线路l):
    判断线路集合S是否合格，条件如下：
        1。无环路
        2。当前地井数 + 地井数下界 <= UMAX
        3。当前跨区铺设线路数 + 跨区铺设线路数下界 <= DMAX
        4。当前费用 + 构成网络还需要的边的数量 * l的费用 < 已知最优方案的费用
    如果合格：
        当前网络已经覆盖所有站点:
            记S为已知最优
        否则若剩下的线路数有可能使所有站点构成网络:
            search(S ∪ {l}, l的下一条路线)
            search(S, l的下一条路线)

税费题

这个答案好像有问题，仅供参考
1)
可以根据除A外的51个国家定义一棵若干层二叉搜索树。每个节点的左分支表示选择其代表的国家为下一个贸易顺序上的国家，右分支则表示不选择。构造搜索树需要两个辅助变量，之前的贸易顺序S（s为S的最后一个国家）和这一轮否决的国家V，初始S=，V=空集。任取可以和s国贸易的国家c（不属于S和V）置于树的当前生成位置，然后用(S' = 和V' = 空集)生成左子树，用(S' = S和V' = V ∪ {c})生成右子树。如果c不存在或者s = B则终止当前子树的生成。如此反复可以建立一棵二叉搜索树。
2)
前进：当前节点未被剪枝并且仍有子节点即可继续前进。
分支：先遍历左分支，后遍历右分支。
回溯：左右分支都被遍历时返回父节点，达到回溯条件（当前时间 + s国与B国贸易的最小税费对应的时间 <= t）时直接回溯。
剪枝：
剪枝条件如下：
1。当前税费 + s国与B国贸易的最小税费 >= 已知最优方案的税费
2。当前时间 + s国与B国贸易的最短时间 > t
3)
子问题的下界为税费下界和时间下界，均由dijkstra算法算法得到，表示某国与B国贸易的最小税费和最短时间。两个结果均由弱化限制的方法得到，所以是正确的，计算复杂度也不高，当然有效。
父问题的上界是已知最优方案的税费，显然正确有效。
4)

使用dijkstra算法得到子问题下界：
    1。税费下界：某国与B国贸易的最小税费，顺便记录对应的时间和贸易顺序
    2。时间下界：某国与B国贸易的最短时间
search(<A>)
返回最优结果
def search(贸易顺序S):
    令s为S的最后一个国家
    判断S是否合格，条件如下：
        1。当前税费 + s国与B国贸易的最小税费 < 已知最优方案的税费
        2。当前时间 + s国与B国贸易的最短时间 <= t
    如果合格：
        当前时间 + s国与B国贸易的最小税费对应的时间 <= t:
            记<S, s国与B国贸易的最小税费对应贸易顺序(不包括s)>为已知最优
        否则对所有可以与s国贸易的不属于S的国家c:
            search(<S, c>)