包邮算法设计与分析

第1章 算法概述 ································· 1 1.1 引言·············································· 3 1.2 算法的概念····································· 4 1.3 算法复杂性分析······························· 8 1.4 本章小结······································· 16 习题···················································· 17 第2章 递归与分治策略 ······················19 2.1 递归············································· 22 2.2 分治策略······································· 28 2.3 分治法求解查找问题························ 30 2.4 分治法求解排序问题························ 33 2.5 分治法求解复杂计算问题·················· 38 2.6 分治法求解组合问题························ 51 2.7 本章小结······································· 55 习题···················································· 56 第3章 动态规划算法··························59 3.1 动态规划的基本概念························ 62 3.2 备忘录方法···································· 64 3.3 动态规划算法的总体设计思想和 基本要素······································· 65 3.4 矩阵连乘问题································· 67 3.5 *长公共子序列问题························ 74 3.6 0-1背包问题 ·································· 80 3.7 *大子段和问题······························ 83 3.8 凸多边形*优三角剖分····················· 88 3.9 本章小结······································· 90 习题···················································· 91 第4章 贪心算法 ································94 4.1 生活中的贪心算法··························· 96 4.2 贪心算法的基本思想························ 98 4.3 活动安排问题································100 4.4 *优装载问题································104 4.5 哈夫曼编码···································108 4.6 贪心算法的正确性验证····················116 4.7 本章小结······································117 习题···················································117 第5章 回溯法·································· 120 5.1 回溯法的基本思想··························122 5.2 回溯法的算法框架··························123 5.3 装载问题······································127 5.4 批处理作业调度问题·······················130 5.5 符号三角形问题·····························133 5.6 0-1背包问题 ·································135 5.7 *大团问题···································138 5.8 旅行商问题···································141 5.9 连续邮资问题································145 5.10 回溯法的效率分析 ························148 5.11 本章小结·····································149 习题···················································149 第6章 分支限界法··························· 154 6.1 分支限界法的基本思想····················157 6.2 装载问题······································161 6.3 布线问题······································171 6.4 0-1背包问题 ·································177 目 录 算法设计与分析(文前+1-4).indd 7 2022/3/9 15:25:03 算法设计与分析 VIII 6.5 *大团问题···································182 6.6 旅行商问题···································185 6.7 本章小结······································189 习题···················································190 第7章 随机算法 ······························ 193 7.1 随机算法的设计思想·······················196 7.2 随机数发生器································197 7.3 数值随机算法································199 7.4 舍伍德算法···································200 7.5 拉斯维加斯算法·····························203 7.6 蒙特卡罗算法································208 7.7 本章小结······································210 习题···················································210 第8章 线性规划与网络流················· 212 8.1 线性规划概述································215 8.2 单纯形法的设计思想与步骤··············221 8.3 单纯形法的描述与分析····················232 8.4 网络*大流问题·····························235 8.5 *小费用流问题·····························244 8.6 本章小结······································257 习题···················································257 参考文献 ·········································· 261