热搜关键词: 信号与系统无刷电机ADSTCP/IP

pdf

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

  • 1星
  • 日期: 2022-01-06
  • 大小: 61.95MB
  • 所需积分:0分
  • 下载次数:2
  • favicon收藏
  • rep举报
  • free评论
标签: 编程

编程

算法

算法

作者简介    ·  ·  ·  ·  ·  ·

William  J.  Cook

加拿大滑铁卢大学教授,美国国家工程院院士,美国数学学会、美国工业与应用数学学会以及美国运筹学和管理学研究协会会员。主要研究领域为整数规划与组合优化,曾出版多部研究旅行商问题的专著,其中与人合著的The  Taveling  Salesman  Problem:A  Computational  Study获2007年Lanchester奖。

目录    ·  ·  ·  ·  ·  ·

第  1  章 难题大挑战  1

1.1   环游美国之旅  2

1.2   不可能的任务吗  7

1.2.1   好算法,坏算法  8

1.2.2   复杂度类P与NP  10

1.2.3   终极问题  11

1.3   循序渐进,各个击破  12

1.3.1   从49到85  900  12

1.3.2   世界旅行商问题  15

1.3.3  《蒙娜丽莎》一笔画  17

1.4   本书路线一览  18

第  2  章 历史渊源  21

2.1   数学家出场之前  21

2.1.1   商人  21

2.1.2   律师  27

2.1.3   牧师  28

2.2   欧拉和哈密顿  30

2.2.1   图论与哥尼斯堡七桥问题  30

2.2.2   骑士周游问题  33

2.2.3   Icosian图  34

2.2.4   哈密顿回路  37

2.2.5   数学谱系  39

2.3   维也纳—哈佛—普林斯顿  40

2.4   兰德公司  43

2.5   统计学观点  45

2.5.1   孟加拉黄麻农田  45

2.5.2   证实路线估计值  47

2.5.3   TSP常数  47

第  3  章 旅行商的用武之地  50

3.1   公路旅行  50

3.1.1   数字化时代的推销员  50

3.1.2   取货与送货  51

3.1.3   送餐到家  52

3.1.4   农场、油田、蓝蟹  53

3.1.5   巡回售书  53

3.1.6  “多走一里路”  54

3.1.7   摩托车拉力赛  54

3.1.8   飞行时间  55

3.2   绘制基因组图谱  56

3.3   望远镜、X射线、激光方向瞄准  57

3.3.1   搜寻行星  58

3.3.2   X射线晶体学  59

3.3.3   激光雕刻水晶工艺品  60

3.4   操控工业机械  61

3.4.1   印制电路板钻孔  61

3.4.2   印制电路板焊锡  62

3.4.3   黄铜雕刻  62

3.4.4   定制计算机芯片  62

3.4.5   清理硅晶片缺陷  63

3.5   组织数据  63

3.5.1   音乐之旅  64

3.5.2   电子游戏速度优化  66

3.6   微处理器测试  67

3.7   安排生产作业任务  68

3.8   其他应用  68

第  4  章 探寻路线  70

4.1   周游48州问题  70

4.2   扩充构造树与路线  73

4.2.1   最近邻算法  73

4.2.2   贪心算法  75

4.2.3   插入算法  77

4.2.4   数学概念:树  79

4.2.5   Christofides算法  82

4.2.6   新思路  84

4.3   改进路线?立等可取!  85

4.3.1   边交换算法  86

4.3.2   Lin-Kernighan算法  89

4.3.3   Lin-Kernighan-Helsgaun算法  92

4.3.4   翻煎饼、比尔·盖茨和大步搜索的LKH算法  93

4.4   借鉴物理和生物思想  95

4.4.1   局部搜索与爬山算法  95

4.4.2   模拟退火算法  97

4.4.3   链式局部最优化  97

4.4.4   遗传算法  99

4.4.5   蚁群算法  101

4.4.6   其他  102

4.5   DIMACS挑战赛  103

4.6   路线之王  104

第  5  章 线性规划  106

5.1   通用模型  106

5.1.1   线性规划  107

5.1.2   引入产品  109

5.1.3   线性的世界  110

5.1.4   应用  111

5.2   单纯形算法  112

5.2.1   主元法求解  113

5.2.2   多项式时间的选主元规则  116

5.2.3   百万倍大提速  117

5.2.4   名字背后的故事  118

5.3   买一赠一:线性规划的对偶性  119

5.4   TSP对应的度约束线性规划的松弛  122

5.4.1   度约束条件  124

5.4.2   控制区  125

5.5   消去子回路  127

5.5.1   子回路不等式  129

5.5.2   “4/3猜想”  131

5.5.3   变量取值的上界  132

5.6   完美松弛  133

5.6.1   线性规划的几何本质  133

5.6.2   闵可夫斯基定理  135

5.6.3   TSP多面体  137

5.7   整数规划  137

5.7.1   TSP的整数规划模型  139

5.7.2   整数规划的求解程序  140

5.8   运筹学  140

第  6  章 割平面法  143

6.1   割平面法  143

6.2   TSP不等式一览  148

6.2.1   梳子不等式  149

6.2.2   TSP多面体的小平面定义不等式  152

6.3   TSP不等式的分离问题  155

6.3.1   最大流与最小割  155

6.3.2   梳子分离问题  157

6.3.3   不自交的线性规划解  159

6.4   Edmonds的“天堂之光”  161

6.5   整数规划的割平面  163

第  7  章 分支  165

7.1   拆分  165

7.2   搜索队  168

7.2.1   分支切割法  168

7.2.2   强分支  170

7.3   整数规划的分支定界法  171

第  8  章 大计算  173

8.1   世界纪录  173

8.1.1   随机选取的64个地点  174

8.1.2   随机选取的80个地点  175

8.1.3   德国的120座城市  177

8.1.4   电路板上的318个孔洞  178

8.1.5   全世界的666个地点  179

8.1.6   电路板上的2392个孔洞  180

8.1.7   电路板上的3038个孔洞  181

8.1.8   美国的13  509座城市  183

8.1.9   计算机芯片上的85  900个门电路  183

8.2   规模宏大的TSP  185

8.2.1   Bosch的艺术收藏品  186

8.2.2   世界  187

8.2.3   恒星  188

第  9  章 复杂性  190

9.1   计算模型  191

9.2   Jack  Edmonds的奋战  193

9.3   Cook定理和Karp问题列表  196

9.3.1   复杂性类  196

9.3.2   问题归约  198

9.3.3   21个NP完全问题  199

9.3.4   百万美金  200

9.4   TSP研究现状  200

9.4.1   哈密顿回路  201

9.4.2   几何问题  202

9.4.3   Held-Karp纪录  203

9.4.4   割平面  205

9.4.5   近优路线  206

9.4.6   Arora定理  207

9.5   非计算机不可吗  208

9.5.1   DNA计算TSP  208

9.5.2   细菌  210

9.5.3   变形虫计算  211

9.5.4   光学  212

9.5.5   量子计算机  213

9.5.6   闭合类时曲线  214

9.5.7   绳子和钉子  215

第  10  章 谋事在人  216

10.1   人机对战  216

10.2   寻找路线的策略  217

10.2.1   路线之格式塔  218

10.2.2   儿童找到的路线  218

10.2.3   凸包假说  219

10.2.4   实地TSP题目  220

10.3   神经科学中的TSP  221

10.4   动物解题高手  223

第  11  章 错综之美  225

11.1   Julian  Lethbridge  225

11.2   若尔当曲线  228

11.3   连续曲线一笔画  231

11.4   艺术与数学  234

第  12  章   超越极限  238

参考文献  240

推荐帖子 最新更新时间:2022-01-17 21:57

多普勒流量计传感器安装高度怎么选择?
在安装多普勒流量计时,传感器应尽量安装于靠近渠底,如果渠底有很多沉淀物、淤泥、水草或者有石头会滚动,可以抬高安装位置,避免被沉积物与水草覆盖探头,或者被石头冲击探头;探头距渠底的理想高度为100mm―250mm,具体要根据渠道的最低水位确定。 当渠道水位比较高,同时最低水位也比较高,为了安装方便可以将探头安装于最低水位以下0.5倍处即可。 科学在发展,时代在进步,我们一直在为客户的产品升级
ywj5188 工控电子
CH554评测 灯的闪烁
本帖最后由 chenlijuan 于 2017-10-22 12:02 编辑 CH554开发板收到有几天了, 今天早上根据例程写了个LED灯闪烁的程序。   还是用熟悉的KEILL 烧录用的是 WCHISPTool,选择USB烧录方式, 烧录速度确实是快1秒都不到。 但是有些奇怪,板上的灯P16(D2), P17(D3)没有变化,不知是怎么回事了? 资料在沁恒科技  官网上有htt
chenlijuan 单片机
虚拟架子鼓------Android程序开发
Android程序使用Android Studio开发的界面显示2根鼓棒,移动SensorTile相应的鼓棒会上下左右摆检测到鼓棒快速落下鼓棒时,判断落下的角度播放相应鼓声之前没接触过Android的3D开发在网上找了一个“OpenGL ES2.03D茶壶”的例程例程里通过导入3D茶壶的.obj文件,并对其进行操作我用3DMAX自己画了一根鼓棒,第一次用3DMax,用着还挺顺手http://bbs
littleshrimp MEMS传感器
【LPC54100】+ LED走起
本帖最后由 强仔00001 于 2015-2-17 01:12 编辑 今天点了个灯,看了原理图知道这个板子引出3个IO口开控制套件上的3色贴片的led。如下图:从原理可以看出这个3色led是共阳的,也就是说,我把相应的IO置低就可以控制某个led亮或者组合成其他颜色。我现在就用就用Keil 5来点亮板子上的LED,keil 5相比其他的版本变了不少,关于keil的这方面我就不多说了。现在直入主
强仔00001 NXP MCU
线性充电器的基本功能
作者:德州仪器 Pearl Cao      随着内置功能越来越多,越来越智能的电子设备在更具吸引力的同时也更加耗电,可充电电池因此成为了一个经济的选择。近年来,随着创新应用、新兴技术和新电池化学成分的出现,充电器的需求不断发展。例如,可穿戴设备领域的新应用(如智能银行卡、智能服装和医疗贴片)引领着解决方案变得更小巧便宜,同时也推动着电池朝更小更高功率密度的方向发展。     
qwqwqw2088 模拟与混合信号
【SINA31评测】No.1.果照哪里有?速度戳进来。
最近在玩Ubuntu和Linux 手上也有一套平台 正好论坛有A31平台的评测的活动 正好撸来简单比较一下 如果触及厂家的敏感处,请管管帮忙直接修改 在@okhxyyo 的帮助下,昨天拿到这套SINLINX芯灵思A31s的开发平台 开箱爆果照 天蓝色的包装盒子 炎炎夏日啊 终于有一丝清凉的感觉 包装简洁大方,起码给楼主第一印象还不错 开箱全家桶,欢乐无极限 5v2A
ljj3166 嵌入式系统

评论

登录/注册

意见反馈

求资源

回顶部

About Us 关于我们 客户服务 联系方式 器件索引 网站地图 最新更新 手机版 版权声明

北京市海淀区知春路23号集成电路设计园量子银座1305 电话:(010)82350740 邮编:100191

电子工程世界版权所有 京B2-20211791 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号 Copyright © 2005-2022 EEWORLD.com.cn, Inc. All rights reserved
×