科技
类型
8.0
豆瓣评分
可以朗读
语音朗读
166千字
字数
2013-09-01
发行日期
展开全部
主编推荐语
一部讨论最短路径数学问题的作品。
内容简介
本书概述了旅行商问题的起源和历史，并阐述了其许多重要的应用范围，如基因组测序、计算机处理器设计、音乐整理、行星寻找，等等。此外还探讨了人类如何在不借助计算机的情况下解决这个令人着迷的数学问题。
目录
- 版权信息
- 内容提要
- 版权声明
- 序
- 第1章 难题大挑战
- 1.1 环游美国之旅
- 1.2 不可能的任务吗
- 1.2.1 好算法，坏算法
- 1.2.2 复杂度类P与NP
- 1.2.3 终极问题
- 1.3 循序渐进，各个击破
- 1.3.1 从49到85 900
- 1.3.2 世界旅行商问题
- 1.3.3 《蒙娜丽莎》一笔画
- 1.4 本书路线一览
- 第2章 历史渊源
- 2.1 数学家出场之前
- 2.1.1 商人
- 2.1.2 律师
- 2.1.3 牧师
- 2.2 欧拉和哈密顿
- 2.2.1 图论与哥尼斯堡七桥问题
- 2.2.2 骑士周游问题
- 2.2.3 Icosian图
- 2.2.4 哈密顿回路
- 2.2.5 数学谱系
- 2.3 维也纳—哈佛—普林斯顿
- 2.4 兰德公司
- 2.5 统计学观点
- 2.5.1 孟加拉黄麻农田
- 2.5.2 证实路线估计值
- 2.5.3 TSP常数
- 第3章 旅行商的用武之地
- 3.1 公路旅行
- 3.1.1 数字化时代的推销员
- 3.1.2 取货与送货
- 3.1.3 送餐到家
- 3.1.4 农场、油田、蓝蟹
- 3.1.5 巡回售书
- 3.1.6 “多走一里路”
- 3.1.7 摩托车拉力赛
- 3.1.8 飞行时间
- 3.2 绘制基因组图谱
- 3.3 望远镜、X射线、激光方向瞄准
- 3.3.1 搜寻行星
- 3.3.2 X射线晶体学
- 3.3.3 激光雕刻水晶工艺品
- 3.4 操控工业机械
- 3.4.1 印制电路板钻孔
- 3.4.2 印制电路板焊锡
- 3.4.3 黄铜雕刻
- 3.4.4 定制计算机芯片
- 3.4.5 清理硅晶片缺陷
- 3.5 组织数据
- 3.5.1 音乐之旅
- 3.5.2 电子游戏速度优化
- 3.6 微处理器测试
- 3.7 安排生产作业任务
- 3.8 其他应用
- 第4章 探寻路线
- 4.1 周游48州问题
- 4.2 扩充构造树与路线
- 4.2.1 最近邻算法
- 4.2.2 贪心算法
- 4.2.3 插入算法
- 4.2.4 数学概念：树
- 4.2.5 Christofides算法
- 4.2.6 新思路
- 4.3 改进路线？立等可取！
- 4.3.1 边交换算法
- 4.3.2 Lin-Kernighan算法
- 4.3.3 Lin-Kernighan-Helsgaun算法
- 4.3.4 翻煎饼、比尔·盖茨和大步搜索的LKH算法
- 4.4 借鉴物理和生物思想
- 4.4.1 局部搜索与爬山算法
- 4.4.2 模拟退火算法
- 4.4.3 链式局部最优化
- 4.4.4 遗传算法
- 4.4.5 蚁群算法
- 4.4.6 其他
- 4.5 DIMACS挑战赛
- 4.6 路线之王
- 第5章 线性规划
- 5.1 通用模型
- 5.1.1 线性规划
- 5.1.2 引入产品
- 5.1.3 线性的世界
- 5.1.4 应用
- 5.2 单纯形算法
- 5.2.1 主元法求解
- 5.2.2 多项式时间的选主元规则
- 5.2.3 百万倍大提速
- 5.2.4 名字背后的故事
- 5.3 买一赠一：线性规划的对偶性
- 5.4 TSP对应的度约束线性规划的松弛
- 5.4.1 度约束条件
- 5.4.2 控制区
- 5.5 消去子回路
- 5.5.1 子回路不等式
- 5.5.2 “4/3猜想”
- 5.5.3 变量取值的上界
- 5.6 完美松弛
- 5.6.1 线性规划的几何本质
- 5.6.2 闵可夫斯基定理
- 5.6.3 TSP多面体
- 5.7 整数规划
- 5.7.1 TSP的整数规划模型
- 5.7.2 整数规划的求解程序
- 5.8 运筹学
- 第6章 割平面法
- 6.1 割平面法
- 6.2 TSP不等式一览
- 6.2.1 梳子不等式
- 6.2.2 TSP多面体的小平面定义不等式
- 6.3 TSP不等式的分离问题
- 6.3.1 最大流与最小割
- 6.3.2 梳子分离问题
- 6.3.3 不自交的线性规划解
- 6.4 Edmonds的“天堂之光”
- 6.5 整数规划的割平面
- 第7章 分支
- 7.1 拆分
- 7.2 搜索队
- 7.2.1 分支切割法
- 7.2.2 强分支
- 7.3 整数规划的分支定界法
- 第8章 大计算
- 8.1 世界纪录
- 8.1.1 随机选取的64个地点
- 8.1.2 随机选取的80个地点
- 8.1.3 德国的120座城市
- 8.1.4 电路板上的318个孔洞
- 8.1.5 全世界的666个地点
- 8.1.6 电路板上的2392个孔洞
- 8.1.7 电路板上的3038个孔洞
- 8.1.8 美国的13 509座城市
- 8.1.9 计算机芯片上的85 900个门电路
- 8.2 规模宏大的TSP
- 8.2.1 Bosch的艺术收藏品
- 8.2.2 世界
- 8.2.3 恒星
- 第9章 复杂性
- 9.1 计算模型
- 9.2 Jack Edmonds的奋战
- 9.3 Cook定理和Karp问题列表
- 9.3.1 复杂性类
- 9.3.2 问题归约
- 9.3.3 21个NP完全问题
- 9.3.4 百万美金
- 9.4 TSP研究现状
- 9.4.1 哈密顿回路
- 9.4.2 几何问题
- 9.4.3 Held-Karp纪录
- 9.4.4 割平面
- 9.4.5 近优路线
- 9.4.6 Arora定理
- 9.5 非计算机不可吗
- 9.5.1 DNA计算TSP
- 9.5.2 细菌
- 9.5.3 变形虫计算
- 9.5.4 光学
- 9.5.5 量子计算机
- 9.5.6 闭合类时曲线
- 9.5.7 绳子和钉子
- 第10章 谋事在人
- 10.1 人机对战
- 10.2 寻找路线的策略
- 10.2.1 路线之格式塔
- 10.2.2 儿童找到的路线
- 10.2.3 凸包假说
- 10.2.4 实地TSP题目
- 10.3 神经科学中的TSP
- 10.4 动物解题高手
- 第11章 错综之美
- 11.1 Julian Lethbridge
- 11.2 若尔当曲线
- 11.3 连续曲线一笔画
- 11.4 艺术与数学
- 第12章 超越极限
- 参考文献
展开全部
评分及书评
尚无评分
目前还没人评分
出版方
人民邮电出版社·图灵出品
图灵社区成立于2005年6月，由人民邮电出版社投资控股，以策划出版高质量的科技书籍为核心业务，主要出版领域包括计算机、电子电气、数学统计、科普等，通过引进国际高水平的教材、专著，以及发掘国内优秀原创作品等途径，为目标读者提供一流的内容。
