迷茫的旅行商:一个无处不在的计算机算法问题

迷茫的旅行商:一个无处不在的计算机算法问题
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者: [美] ,
2013-10
版次: 1
ISBN: 9787115327734
定价: 49.00
装帧: 平装
开本: 32开
纸张: 胶版纸
页数: 242页
字数: 254千字
正文语种: 简体中文
原版书名: In pursuit of the traveling salesman:Mathematics at the limits of computation
丛书: 图灵新知
126人买过
  •   《迷茫的旅行商:一个无处不在的计算机算法问题》概述了旅行商问题的起源和历史,并阐述了其许多重要的应用范围,如基因组测序、计算机处理器设计、音乐整理、行星寻找,等等。此外还探讨了人类如何在不借助计算机的情况下解决这个令人着迷的数学问题。
      《迷茫的旅行商:一个无处不在的计算机算法问题》图文并茂,生动有趣,适合所有对旅行商和数学感兴趣的读者。
      William J. Cook,加拿大滑铁卢大学教授,美国国家工程院院士,美国数学学会、美国工业与应用数学学会以及美国运筹学和管理学研究协会会员。主要研究领域为整数规划与组合优化,曾出版多部研究旅行商问题的专著,其中与人合著的The Taveling Salesman Problem:A Computational Study获2007年Lanchester奖。
    第1章难题大挑战
    1.1环游美国之旅
    1.2不可能的任务吗
    1.2.1好算法,坏算法
    1.2.2复杂度类P与NP
    1.2.3终极问题
    1.3循序渐进,各个击破
    1.3.1从49到85900
    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.3Icosian图
    2.2.4哈密顿回路
    2.2.5数学谱系
    2.3维也纳-哈佛-普林斯顿
    2.4兰德公司
    2.5统计学观点
    2.5.1孟加拉黄麻农田
    2.5.2证实路线估计值
    2.5.3TSP常数

    第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.2X射线晶体学
    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.5Christofides算法
    4.2.6新思路
    4.3改进路线?立等可取!
    4.3.1边交换算法
    4.3.2Lin-Kernighan算法
    4.3.3Lin-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.5DIMACS挑战赛
    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.4TSP对应的度约束线性规划的松弛
    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.3TSP多面体
    5.7整数规划
    5.7.1TSP的整数规划模型
    5.7.2整数规划的求解程序
    5.8运筹学

    第6章割平面法
    6.1割平面法
    6.2TSP不等式一览
    6.2.1梳子不等式
    6.2.2TSP多面体的小平面定义不等式
    6.3TSP不等式的分离问题
    6.3.1最大流与最小割
    6.3.2梳子分离问题
    6.3.3不自交的线性规划解
    6.4Edmonds的“天堂之光”
    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美国的13509座城市
    8.1.9计算机芯片上的85900个门电路
    8.2规模宏大的TSP
    8.2.1Bosch的艺术收藏品
    8.2.2世界
    8.2.3恒星

    第9章复杂性
    9.1计算模型
    9.2JackEdmonds的奋战
    9.3Cook定理和Karp问题列表
    9.3.1复杂性类
    9.3.2问题归约
    9.3.321个NP完全问题
    9.3.4百万美金
    9.4TSP研究现状
    9.4.1哈密顿回路
    9.4.2几何问题
    9.4.3Held-Karp纪录
    9.4.4割平面
    9.4.5近优路线
    9.4.6Arora定理
    9.5非计算机不可吗
    9.5.1DNA计算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.1JulianLethbridge
    11.2若尔当曲线
    11.3连续曲线一笔画
    11.4艺术与数学

    第12章超越极限
    参考文献
  • 内容简介:
      《迷茫的旅行商:一个无处不在的计算机算法问题》概述了旅行商问题的起源和历史,并阐述了其许多重要的应用范围,如基因组测序、计算机处理器设计、音乐整理、行星寻找,等等。此外还探讨了人类如何在不借助计算机的情况下解决这个令人着迷的数学问题。
      《迷茫的旅行商:一个无处不在的计算机算法问题》图文并茂,生动有趣,适合所有对旅行商和数学感兴趣的读者。
  • 作者简介:
      William J. Cook,加拿大滑铁卢大学教授,美国国家工程院院士,美国数学学会、美国工业与应用数学学会以及美国运筹学和管理学研究协会会员。主要研究领域为整数规划与组合优化,曾出版多部研究旅行商问题的专著,其中与人合著的The Taveling Salesman Problem:A Computational Study获2007年Lanchester奖。
  • 目录:
    第1章难题大挑战
    1.1环游美国之旅
    1.2不可能的任务吗
    1.2.1好算法,坏算法
    1.2.2复杂度类P与NP
    1.2.3终极问题
    1.3循序渐进,各个击破
    1.3.1从49到85900
    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.3Icosian图
    2.2.4哈密顿回路
    2.2.5数学谱系
    2.3维也纳-哈佛-普林斯顿
    2.4兰德公司
    2.5统计学观点
    2.5.1孟加拉黄麻农田
    2.5.2证实路线估计值
    2.5.3TSP常数

    第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.2X射线晶体学
    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.5Christofides算法
    4.2.6新思路
    4.3改进路线?立等可取!
    4.3.1边交换算法
    4.3.2Lin-Kernighan算法
    4.3.3Lin-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.5DIMACS挑战赛
    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.4TSP对应的度约束线性规划的松弛
    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.3TSP多面体
    5.7整数规划
    5.7.1TSP的整数规划模型
    5.7.2整数规划的求解程序
    5.8运筹学

    第6章割平面法
    6.1割平面法
    6.2TSP不等式一览
    6.2.1梳子不等式
    6.2.2TSP多面体的小平面定义不等式
    6.3TSP不等式的分离问题
    6.3.1最大流与最小割
    6.3.2梳子分离问题
    6.3.3不自交的线性规划解
    6.4Edmonds的“天堂之光”
    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美国的13509座城市
    8.1.9计算机芯片上的85900个门电路
    8.2规模宏大的TSP
    8.2.1Bosch的艺术收藏品
    8.2.2世界
    8.2.3恒星

    第9章复杂性
    9.1计算模型
    9.2JackEdmonds的奋战
    9.3Cook定理和Karp问题列表
    9.3.1复杂性类
    9.3.2问题归约
    9.3.321个NP完全问题
    9.3.4百万美金
    9.4TSP研究现状
    9.4.1哈密顿回路
    9.4.2几何问题
    9.4.3Held-Karp纪录
    9.4.4割平面
    9.4.5近优路线
    9.4.6Arora定理
    9.5非计算机不可吗
    9.5.1DNA计算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.1JulianLethbridge
    11.2若尔当曲线
    11.3连续曲线一笔画
    11.4艺术与数学

    第12章超越极限
    参考文献
查看详情
系列丛书 / 更多
迷茫的旅行商:一个无处不在的计算机算法问题
信息简史
[美]詹姆斯·格雷克 著;高博 译
迷茫的旅行商:一个无处不在的计算机算法问题
你不可不知的50个物理知识
[美]贝克(Joanne Baker) 著;马潇潇 译
迷茫的旅行商:一个无处不在的计算机算法问题
数学与生活(修订版)
[日]远山启 著;吕砚山、李诵雪、马杰、莫德举 译
迷茫的旅行商:一个无处不在的计算机算法问题
思考的乐趣:Matrix67数学笔记
顾森 著
迷茫的旅行商:一个无处不在的计算机算法问题
神奇的数学:牛津教授给青少年的讲座
[英]Marcus du Sautoy 著;程玺 译
迷茫的旅行商:一个无处不在的计算机算法问题
数学女孩
[日]结城浩 著;朱一飞 译
迷茫的旅行商:一个无处不在的计算机算法问题
你不可不知的50个数学知识
[英]Tony Crilly 著;王悦 译
迷茫的旅行商:一个无处不在的计算机算法问题
数学女孩2:费马大定理
[日]结城浩 著;丁灵 译
迷茫的旅行商:一个无处不在的计算机算法问题
数学万花筒3 夏尔摩斯探案集
何生 译
迷茫的旅行商:一个无处不在的计算机算法问题
微积分的历程:从牛顿到勒贝格
[美]邓纳姆 著;李伯民、汪军、张怀勇 译
迷茫的旅行商:一个无处不在的计算机算法问题
陶哲轩教你学数学
李馨 译
迷茫的旅行商:一个无处不在的计算机算法问题
数学女孩3 哥德尔不完备定理
丁灵 译
相关图书 / 更多
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫的大学
刘尧 著
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫的风云:探索云南古代文明
段鼎周 著
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫管家与懦弱的我. 5
[日]朝野始 著;雅岚 译
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫管家与懦弱的我 01
[日]朝野始 著;[日]菊池政治 绘
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫年少时:我的“文革”记忆
于斌 著
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫管家与懦弱的我 02
[日]朝野始 著;[日]菊池政治 绘
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫时,冒险指引你
晨天 著
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫与超越:学校社会工作案例研究
文军
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫管家与懦弱的我 03
[日]朝野始;[日]菊池政治
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫管家与懦弱的我. 6
[日]朝野始 著;雅岚 译
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫的女郎
松本清张
迷茫的旅行商:一个无处不在的计算机算法问题
迷茫管家与懦弱的我 04
[日]朝野始;[日]菊池政治
您可能感兴趣 / 更多
迷茫的旅行商:一个无处不在的计算机算法问题
宇宙视觉史:从宇宙大爆炸到时间的尽头
[美]查尔斯·刘 著;高爽 译者;[美]马克西姆· 马洛维奇科 绘;未读 出品
迷茫的旅行商:一个无处不在的计算机算法问题
写出我心 普通人如何通过写作表达自己(平装本)
[美]娜塔莉·戈德堡(Natalie Goldberg)
迷茫的旅行商:一个无处不在的计算机算法问题
写出我心3 写作疗愈的真正秘密
[美]娜塔莉·戈德堡(Natalie Goldberg)
迷茫的旅行商:一个无处不在的计算机算法问题
神套路:为什么我们总被带节奏(狂热与网红时代醍醐灌顶之作,教给普通人安身立命的不二法门!)
[美]阿里·阿莫萨维 著;[哥伦比亚]亚历杭德罗·希拉尔多 绘
迷茫的旅行商:一个无处不在的计算机算法问题
阿伦森自传
[美]埃利奥特·阿伦森(Elliot Aronson) 著;沈捷 译;湛庐文化 出品
迷茫的旅行商:一个无处不在的计算机算法问题
街头官僚:公共服务中的个人困境
[美]迈克尔·李普斯基(Michael Lipsky)
迷茫的旅行商:一个无处不在的计算机算法问题
史前至蒙古帝国时期的内欧亚大陆史
[美]大卫·克里斯蒂安 著;潘玲 译;杨建华 校
迷茫的旅行商:一个无处不在的计算机算法问题
意大利文艺复兴新艺术史
[美]迈克尔·韦恩·科尔 著;[美]斯蒂芬·J·坎贝尔;邵亦杨
迷茫的旅行商:一个无处不在的计算机算法问题
老人与海 彩图注音版 一二三四年级5-6-7-8-9岁小学生课外阅读经典 儿童文学无障碍有声伴读世界名著童话故事
[美]海明威
迷茫的旅行商:一个无处不在的计算机算法问题
养育的觉醒:全面激发孩子自驱力,教你如何心平气和做妈妈
[美]凯文·莱曼 著;唐晓璐 译;斯坦威 出品
迷茫的旅行商:一个无处不在的计算机算法问题
自律我也能做到(全9册)
[美]康妮·科维尔·米勒 著;[阿根廷]维多利亚·阿萨纳利 绘
迷茫的旅行商:一个无处不在的计算机算法问题
你在等什么?
[美]斯科特·明钦 著;[中]易万 译;[美]马特 ·斐兰 绘