近似算法的设计与分析
￥ 34.65 4.4折 ￥ 79 九五品
仅1件
作者堵丁柱,葛可一,胡晓东 著
出版社高等教育出版社
ISBN9787040319675
出版时间2011-08
版次1
装帧平装
开本16开
纸张胶版纸
页数426页
字数99999千字
定价79元
上书时间2024-05-25
商品详情
- 品相描述：九五品
- 商品描述
-
基本信息
书名:近似算法的设计与分析
定价：79.00元
作者:堵丁柱,葛可一,胡晓东 著
出版社：高等教育出版社
出版日期：2011-08-01
ISBN：9787040319675
字数：520000
页码：426
版次：1
装帧：平装
开本：16开
商品重量：
编辑推荐
近似算法是处理难解的组合优化问题的一个非常重要和有效的方法。它可以在多项式时间内求得问题的一个解，并使其目标函数值与优解的目标函数值之比不超过一个常数。
内容提要
近似算法是处理难解的组合优化问题的一个非常重要和有效的方法。它可以在多项式时间内求得问题的一个解，并使其目标函数值与优解的目标函数值之比不超过一个常数。本书将通过大量具有代表性的组合优化问题，介绍近似算法设计和分析中的三种主要方法：贪婪算法、限制方法和松弛方法；所讨论的问题来源于不同的研究和应用领域，其中包括通信网络设计，光纤网络，无线自组织网络和传感器网络，生物信息学，社会网络，工业工程和信息管理系统等。此外，本书还将介绍有关组合优化问题不可近似性的一些基本结果。本书的每一章后面都配有相关内容的习题和历史注记。 《近似算法的设计与分析》可作为计算机科学和运筹学专业高年级本科生和研究生的近似算法课程的教材，亦可作为相关研究领域科研人员的参考书。
目录
章 引言 1.1 “芝麻，开门!” 1.2 近似算法的设计技巧 1.3 启发式算法与近似算法 1.4 计算复杂性的术语 1.5 np-完全问题 1.6 性能比 习题 历史注记第二章 贪婪策略 2.1 独立系统 2.2 拟阵 2.3 权函数的四边形条件 2.4 次模势函数 2.5 应用 2.6 非次模势函数 习题 历史注记第三章 限制 3.1 斯坦纳树和生成树 3.2 k-限制斯坦纳树 3.3 贪婪k-限制斯坦纳树 3.4 生成树的应用 3.5 种系进化树同步 习题 历史注记第四章 划分 4.1 划分与移位 4.2 边界区域 4.3 多层划分 4.4 双重划分 4.5 树划分 习题 历史注记第五章 断切 5.1 矩形划分 5.2 l-断切 5.3 m-断切 5.4 接口 5.5 四叉树划分与补缀 5.6 两阶段接口 习题 历史注记第六章 松弛 6.1 有向哈密顿圈和超串 6.2 两阶段贪婪近似算法 6.3 单位圆盘图上连通控制集 6.4 有向图中的强连通控制集 6.5 光纤网络中的多播路由 6.6 关于松弛与限制的附记 习题 历史注记第七章 线性规划 7.1 基本性质 7.2 单纯形法 7.3 组合舍人 7.4 管输舍人 7.5 迭代舍人 7.6 随机舍人 习题 历史注记第八章 原始对偶方案与局部比值法 8.1 对偶理论和原始对偶方案 8.2 广义覆盖 8.3 网络设计 8.4 局部比值法 8.5 再论等价性 习题 历史注记第九章 半定规划 9.1 谱面体 9.2 半定规划 9.3 超平面舍人 9.4 旋转向量 9.5 多元正交舍人 习题 历史注记第十章 不可近似性 10.1 具有间隙的多一归约 10.2 间隙放大与保持 10.3 apx-完全性 10.4 概率可验证明定理 10.5 (ρin n)-不可近似性 10.6 nc-不可近似性 习题历史注记参考文献名词索引(汉英对照)
作者介绍
序言
-
【封面】
相关推荐
— 没有更多了 —
以下为对购买帮助不大的评价