• 
  计算机数学-计算...
  ￥22.12元
• 
  最优化方法与程序...
  ￥27.65元

本书全面、系统地介绍了计算复杂性理论的基本内容与各种NPC问题、NP难问题等复杂问题的计算机求解方法。前四章分别简要介绍了线性规划、多面体理论、网络规划与动态规划等预备知识。第五至九章具体介绍了计算复杂性理论。包括复杂性的定义与分类，证明一个问题为P类或NPC类的基本方法，NPC记理论在分析、求解问题中的应用与近似算法的性能度量等。第十至十六章则主要以整数规划为框架，详细论述求解NPC及NP难问题各种不同形式的精确算法与近似算法。
本书可作为信息与计算科学、应用数学、计算机、管理科学等专业的研究生教材或本科生的选修课教材，也可供有关的科研人员参考。

样章试读

• 暂时还没有任何用户评论

总计 0 个记录，共 1 页。 第一页 上一页 下一页 最末页

全部咨询(共0条问答)

• 暂时还没有任何用户咨询内容

总计 0 个记录，共 1 页。 第一页 上一页 下一页 最末页

用户名：	匿名用户
E-mail：
咨询内容：

• 第一章线性规划
  II线性规划的基本概念
  I2单纯形算法
  I3字典序单纯形算法
  I4对偶理论
  I5内点算法
  第二章多面体理论
  2I多面体的定义及其维数
  22用有效不等式与边界面来描述多面体
  23用极点和极射向表示多面体
  第三章图与网络规划
  3I图的基本知识
  3II图
  3I2有向图
  3I3图的表示
  32几类重要的图
  33最短路间题
  34最小权支撑树问题
  35最大流问题
  第四章动态规划方法
  4I多阶段决策问题与动态规划的基本概念
  42动态规划方法的基本思想与最优性定理
  43最小权问题
  44背包问题
  44IO-1背包问题
  442整数背包问题
  45旅行商问题
  第五章算法复杂性概论
  5口引言
  52基本概念
  53多项式时间算法与指数时间算法
  第六章问题复奈性的分类
  6I判定问题与语言
  62算法的严格定义与P类问题。
  63NP类问题
  64多项式变换与MD完全问题
  65强MD完全问题
  66CO-NP类问题
  67NP困难问题
  68空间复杂性简介
  第七章证明问题为NP完全的或P的方法
  7I证明问题为NPC的一般步骤
  72限制法(Restriction)
  73局部置换法(Local Rep1acement)
  74分量设计法(Component Design)
  75证明问题属于P类的方法
  第八章NP完全理论在分析、求解新问题中的应用
  8I分析新问题复杂性的双向研究方法
  82子问题分析法
  83求解NPC问题的算法类型
  第九章近似算法的性能度量与NP完全理论的应用
  91近似算法的性能度量
  92NP完全理论在限定问题可近似程度中的应用
  第十章一般整数规划的基本性质
  t0t一般整数规划问题
  I02整数规划与线性规划之间的关系
  I03整数规划问题解的有界性
  t04整数规划问题的计算复杂性
  第十一章割平面算法
  HI分数割平面算法
  H2整数割平面算法
  H3导出有效不等式的方法
  H3I取整方法
  H32同余方法
  H33合并方法
  U34超加函数法
  U4混合整数规划问题的求解
  H5覆盖问题的割平面算法
  U51覆盖问题的描述
  n52覆盖问题的割平面算法
  第十二章分解算法
  12口拉格朗日松弛法
  122Benders分解
  123一般分解方法
  124选址问题的分解算法
  第十三章分枝定界法
  131口一般分枝定界法
  132使用线性规划松弛的分枝定界算法
  1321厂剪枝准则
  1322分枝方法
  1323结节选取方法
  1324分枝变量选择方法
  1330-1背包问题的分枝定界算法。
  第十四章匹配问题
  141匹配问题简介
  142最大匹配问题
  1421二部图的匹配算法
  ]422非二部图的匹配算法
  143加权匹配问题
  1431指派问题的求解
  1432一般加权匹配问题
  144ｂ匹配问题与其他相关论题
  1441b匹配问题
  1442匹配理论与算法的应用
  第十五章近似算法的设计与分类
  151近似算法概述
  152贪婪算法(Greedy Algorithms)
  153局部搜索法(Local Search Heuristics)
  154原始-对偶法
  155近似算法的其他设计方法
  156近似算法的分类
  ]56入定常近似比算法
  1562近似策略
  1563最好可能近似比算法
  ]564比最好还要好的近似算法
  1565与真正最优值仅一步之遥的近似
  第十六章对称旅行商问题
  16几有效不等式的构造
  162松弛问题的构造
  163近似算法
  163厂最近邻法
  1632最近插人法
  1633贪婪可行法
  1634A边交换法
  1635三角不等式与贪婪型算法的性能
  1636支撑树加倍法
  1637支撑树加完美匹配法
  164精确算法
  164口指派问题加分枝定界算法
  1642拉格朗日松弛加分枝定界算法
  1643分数割平面加分枝定界算法
  参考文献