[自制]07工硕算法分析参考资料

算法的知识结构 算法概述 经典算法 分治法 递归与分治 动态规划 贪心法 回溯法 分支限界法 NP 完全性理论 现代算法简介 第一算法概述 1 什么是算法 什么是算法 书本 算法是由若干条指令组成的有穷序列 具有性质 输入 输出 确定性 有限性 程序与算法的主要 区别 能行性 课堂 寻找解的过程 Search 递归反复的寻找最优解 research 算法复杂性 算法所需的计算机资源 包括时间复杂度 T n 计算所用的时间 和空间复杂度 S n 计 算所用的内存空间 n 是输入量的规模 问题的复杂性与算法复杂性区别 问题复杂性是固定的 涉及 NP 完全性理论 算法复杂性依据算法不同而 不同 一个问题可以有多种算法 2 复杂度表示方式 复杂度表示方式 n 渐近复杂度上界 n 渐近复杂度下界 n 非紧上界 n 非紧下界 n n 紧渐近界 确界 紧渐近 即上界与下界紧夹住中间范围 使得得到的复杂性分析结果较为精确 3 算法性质算法性质 1 传递性 f n g n g n h n f n h n f n g n g n h n f n h n f n g n g n h n f n h n f n g n g n h n f n h n f n g n g n h n f n h n 2 反身性 f n f n f n f n f n f n 3 对称性 f n g n g n f n 4 互对称性 f n O g n g n f n f n g n g n f n 5 算术运算 O f n O g n O max f n g n O f n O g n O f n g n O f n O g n O f n g n O cf n O f n g n O f n O f n O g n O f n 4 复杂度排序 复杂度排序 O 1 O C O loglogn O logn O O O n O nlogn O n2 O n3 O 2n O 3n O n g k f 2k 则 g k 2g k 1 2k 1 1 对此式用递推法就可以解出 第三各种算法 动态规划 贪心法 回溯法 分支限界法 动态规划 条件 最优子结构 重叠子问题 备忘录方法 解法 根据最优子结构 将问题分解为子问题 求子问题的最优解 由于有些子问题是相同的 重叠子问题 因此通过备忘录方法 将解过的子问题的解用备忘录记录起来 在递归遇到相同问题时则搜索备忘录 搜 索备忘录是线性复杂度 优点 带有记忆的算法 可以牺牲空间复杂度 降低时间复杂度 提高效率 缺点 需要满足一定条件 要求整体最优解所以复杂度还是较高 解 0 1 背包问题思路 书上的解法复杂度 O 2n 分解子问题 只装入一个物品 确定在各种不同载重量的背包下 能够得到的最大价值 然后装入前两个物品 确定在各种不同载重量的背包下 能够得到的最大价值 直到装入 n 个物体 最后在载重量 m 的背包下即最大价值 最优子结构 一个物体 j 容量的背包问题得到最优解 追加物体 扩大容量用同样的方式也能得到最优解 重叠子问题 在增加各种不同载重量的背包中 虽然增加了背包的容量 但增加的容量不足以增加新物品 则子 问题重叠 增加一件物品 但当前设定的背包容量已经放不下多余物品 子问题重叠 举例 有5个物品 其重量分别为2 2 6 5 4 价值分别为6 3 5 4 6 背包的载重量为10 要求装入物品重量最 少而物品价值最大 求装入背包的物品及其总价值 根据上述思路 列成表格如下 容量 物品数量 012345678910 000000000000 100666666666 200669999999 300669999111114 4006699910111314 50066991212151515 底色灰色并且加下划线的是搜索的过程 在容量为4的背包中放入1个物体 价值最大为6 然后依次到9 再到 15 根据这样的思路去列递归式 解得装入背包的物体为x 1 1 0 0 1 解旅行商问题 TSPLIB 思路 书上没有 pdf 有 pdf 的解法复杂度 O n22n 分解子问题 如 1 2 3 4 个城市 则用 d 1 2 3 4 表示从城市 1 到 城市 2 3 4 所组成的网络 的费用 即 d 1 2 3 4 min c12 d 2 3 4 c13 d 3 2 4 c14 d 4 2 3 c12代表城市 1 到城市 2 的费用 和 c21不一样 d 2 3 4 表示城市 2 到 城市 3 4 所组成的网络 的费用 又 d 2 3 4 min c23 d 3 4 c24 d 4 3 再分解得到 d 3 4 c34 d 4 c34 c41 其中 表示网络出口 即城市 4 回到城市 1 的费用 最优子结构 某城市到剩余各城市所组成网络的最小费用 合起来是整体问题的最小费用 所以从最小的问题即 类似 d 3 4 的最小费用这种情况 倒推回去最后得到 d 1 2 3 4 的最小费用 重叠子问题 d 4 d 2 d 3 这些问题将会重复出现 举例 4 个城市的费用矩阵 解法示意图 比如 d 3 4 c34 d 4 c34 c41 2 3 5 则倒推回去就可以得到按这条路径 d 1 2 3 4 会是什么值 最 后得到 d 1 2 3 4 min 3 7 6 10 7 14 10 路径顺序是 1 2 3 4 1 的走法费用最低 贪心法 条件 最优子结构 贪心选择性质 解法 尽量选择当前看来最好的选择 得到局部最优解 然后合并为原问题的解 优点 求局部最优解 复杂度没有求整体最优解高 缺点 最终求得的解未必是最优解 注意 分数背包问题可以用动态规划和贪心法解 但 0 1 背包不能用贪心法来解 解出来的值可能非常差 解分数背包问题思路 O nlogn 先计算所有物品的单位重量价值 然后按所得结果进行排序 依次选择单位重量价值最高的物品放入背包 解旅行商问题 TSPLIB 思路 书上没有 网上有提到贪心爬山法解 TSP 问题 pdf 有贪婪法解 TSP 尽量选择当前费用最低的路径去走 得到的不一定是整体费用最小的路径 只选择一个城市作为出发城市 所需 时间是 O n2 n 个城市都可以作为出发城市 所需时间是 O n3 回溯法 条件 有 通用解题法 之称 解法 构造出解空间 形成树 然后以深度优先进行搜索 搜索到的活节点其值已经超出约束条件时 就成为死 节点 跳过搜索下一分支 约束条件有很多 条件太苛刻可能会导致搜索无法继续 条件太宽松可能会使 搜索达不到优化的效果 优点 可以通用搜索问题的解 搜索解空间中满足约束条件的所有解 解 0 1 背包问题思路 O n2n 构造问题的子集树 物体 1 2 3 的选择 1 与不选 0 得到解空间 然后构造课本 P139 的子集树 子集树 一定是完全二叉树 但排列树就不一定是而且通常不是完全二叉树 A BC DEFG HIJKLMNO 1 1 11 1 11 0 000 0 0 0 A B C 等代表选择的状态 子集树三层深度代表三个物体 左边路径选择 右边不选的排列法是其中 一种 而实际中也可以进行其它的排列方法 由于是深度优先 所以排列方法不同可能搜索的时间不同 剪枝 即将这棵树的某些子树剪掉 在搜索时跳过这些子树 加快搜索 在 0 1 背包问题中 可以用目标 值作为剪枝的条件 比如当前搜索到的价值最大是 ABDI 那么假设搜索到 E 时 发现其价值加上后面价值最高 的物品的价值都已经达不到 ABDI 路径的值 就可以将 E 设为死结点 跳过 JK 不搜索了 此外 也可以用贪心法将此问题当作分数背包问题来解 得出一个同样规模条件的分数背包的最优解 然后 根据此解估算子树是否可能会达到最优解 如果连分数背包的宽松条件都不能满足 那么这棵子树就可以判定无 法满足求最优解的条件 可以判定为死结点了 在 pdf 的例子中解法如下 题目 有载重量M 50 的背包 物体重量分别为5 15 25 27 30 物体价值分别为12 30 44 46 50 求最优装入背包 的物体及价值 1 p total 为0 计算p est 94 5 大于p total 生成结点1 2 3 4 部分解 1 1 1 0 2 在结点4 计算p est 94 3 大于p total 继续向下搜索生成结点5 得到价值为86 的可行解 1 1 1 0 0 保 存 在解向量X 中 p total 更新为86 经过剪枝的解题步骤 解旅行商问题思路 O n 构造问题的排列树 按经过城市的序列构造课本 P140 的排列树 A CDE FGHIJK 2 322443 B LMNOPQ 43 4 22 1 3 4 3 解题思路类似于 0 1 背包问题 在 pdf 的例子中解法如下 分支限界法 pdf 写得比较复杂 这里不列出 条件 同回溯法 解法 构造出解空间树 然后以广度优先进行搜索 使搜索朝着解空间上有最优解的分支推进 以便尽快地找出 一个最优解 优点 搜索解空间中满足约束条件的一个解 注 回溯法和分支限界法的根本区别在于搜索顺序的问题 两者各有其作用 个人理解复杂度应该也相同 解 0 1 背包问题 A BC DEFG HIJKLMNO 1 1 11 1 11 0 000 0 0 0 解旅行商 TSP 问题 A CDE FGHIJK 2 322443 B LMNOPQ 434232 1 3 4 分支限界法在搜索时 由于无法从一开始就得到目标值 所以往往剪枝用的是其它条件 相比回溯法 有时广度 优先的搜索可以更快地向搜索目标 最优解 收敛 第四NP 问题和 NP 完全问题 纯属个人理解 不一定正确 NP 完全性理论研究问题的复杂性而非算法复杂性 是问题本身的特性刻画 P 类可以理解为多项式时间算法的问题 NP 类可以理解为指数级别时间算法的问题 指数级别时间算法的问题是否存在多项式时间算法现在还没有确定 即 NP P 还没有被证明 NPC 设想中属于 NP 问题而在 P 问题之外 即完全是 NP 的 被认为不可能存在有多项式时间算法的一类 问题 如果研究出 NPC 问题有多项式时间算法的话 则 NP P 但目前 NPC 尚未证明是否有多项式时间算 法 对于 NP 问题 虽然可能不能确定找出问题的解 但可以验证一个解是否是问题的解 这是因为 COOK 定理 COOK 定理 布尔表达式的可满足性问题 SAT 是 NP 完全的 当我们可以证明另一个问题 XX 是可以规约到 SAT 问题的话 就能说明 XX 问题是 NP 完全的 第五遗传算法 也是个人理解 不一定正确 传统算法是局部优化法 而现代算法是全局优化法 传统算法依赖出示条件 与求解空间有紧密关系 可以 促使算法最快地收敛到局部解 但同时对解域有约束 利用约束加快收敛 有些方法至少依赖一阶导数 遗传算法将搜索空间映射为遗传空间 用优胜劣汰的进化现象来收敛问题解 分为两步 编码和操作 编码 将解空间 即可能的所有解 编码为一个向量 染色体 向量的每个元素称为基因 通过操作染色 体并计算其适应值 设定一个适应值函数来计算 选择最好的染色体来获得最优解 基本操作 选择 抽取染色体样本 交换 基因互换 变异 基因通过某种方式进行变化 如二进制取反 举例 0 1 背包问题 n 4 的遗传算法解题思路 编码 物体 1 2 3 4 选与不选用 0 1 表示 则解为 0 0 0 0 或 0 0 0 1 或 1 0 1 0 或 1 0 1 1 操作 选择 按某种方式 比如随机抽取等 将各种解分组 种群 在种群中按某种方式 如随机抽取 适应度比 例法 赌轮选择机制等 选取染色体 比如选 1 0 1 1 或 0 0 0 1 交换 将被选择出的两个父母染色体的部分码值 基因 进行交换 比如选 1 0 1 1 或 0 0 0 1 按某种方式 比 如随机生成 产生一个位置 比如 3 则将两个染色体第 3 个码交换 结果是 1 0 0 1 和 0 0 1 1 变异 比如二进制码的变异 就是按某种方式产生一个位置 将该位置的码取反 老种群通过选择 交换 变异的操作后产生新种群 计算新种群的适应度 按适应度再选择 交换 变异 一代一代 的种群逐步向适应度最高的 最优解靠拢 图式定理 计算适应度时 保留某些好的图式 比如保留编码中包含片断为 0 1 0 这样的图式的染色体适应 度可能是比较高的 则按照保留这种图式来计算适应度 TSP 这类排列问题 比