首页 >
旅行推销员问题
✍ dations ◷ 2025-04-02 09:29:57 #旅行推销员问题
行商问题(最短路径问题)(英语:travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。TSP是旅行购买者问题(英语:travelling purchaser problem)与车辆路径问题的一种特殊情况。作为计算复杂性理论中的一个典型的判定性问题,TSP的一个版本是给定一个图和长度 L,要求回答图中是否存在比 L 短的回路(英语:circuit或tour)。该问题被划分为NP完全问题。已知TSP算法最坏情况下的时间复杂度随着城市数量的增多而成超多项式(可能是指数(英语:Exponential time hypothesis))级别增长。问题在1930年首次被形式化,并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难,但已经有了大量的启发式和精确方法,因此可以完全求解城市数量上万的实例,并且甚至能在误差1%范围内估计上百万个城市的问题。甚至纯粹形式的TSP都有若干应用,如企划、物流、芯片制造。稍作修改,就是DNA测序等许多领域的一个子问题。在这些应用中,“城市”的概念用来表示客户、焊接点或DNA片段,而“距离”的概念表示旅行时间或成本或DNA片段之间的相似性度量。TSP还用在天文学中,观察很多源的天文学家希望减少在源之间转动望远镜的时间。许多应用(如资源或时间窗口有限)中,可能会加入额外的约束。可以用无向加权图来对TSP建模,则城市是图的顶点,道路是图的边,道路的距离就是该边的长度。它是起点和终点都在一个特定顶点,访问每个顶点恰好一次的最小化问题。通常,该模型是一个完全图(即每对顶点由一条边连接)。如果两个城市之间不存在路径,则增加一条非常长的边就可以完成图,而不影响计算最优回路。在对称TSP问题中,两座城市之间来回的距离是相等的,形成一个无向图。这种对称性将解的数量减少了一半。在非对称TSP问题中,可能不是双向的路径都存在,或是来回的距离不同,形成了有向图。交通事故、单行道和出发与到达某些城市机票价格不同等都是打破这种对称性的例子。单钻头的运动可以看成是典型的TSP问题。TSP可以用整数线性规划来形式化。 用数字 0, ..., n 标记这些城市(打孔位置),并定义:对于 i = 0, ..., n,令
u
i
{displaystyle u_{i}}
为一人工变量,最后把
c
i
j
{displaystyle c_{ij}}
作为从城市 i 到 j 的距离。那么TSP可以写成下面的整数线性规划问题:第一组等式要求每个城市都能另一个城市前来,而第二组等式要求每个城市都能出发。最后的约束迫使覆盖所有城市的路径只有一条,而不是两条或者多条分散的路径在一起覆盖的。要证明这一点,下面会去证 (1)每个可行解包含只有一条封闭城市序列,以及(2)对于每条覆盖所有城市的单独路径,虚拟变量
u
i
{displaystyle u_{i}}
有值可以满足约束。证明可行解中的每个子回路经过0号城市(注意到等式保证了只有一条这样的路径),就能证明所有可行解只包含一个封闭城市序列。对于若我们对所有
x
i
j
=
1
{displaystyle x_{ij}=1}
对应的不等式求和的话,对 k 步不经过0号城市的任何子回路,我们得到:这构成矛盾。必须证明对每个覆盖所有城市的单独回路,虚拟变量
u
i
{displaystyle u_{i}}
有值可以满足约束。为了不失一般性,定义起始点为0号城市。如果在第 t 步访问城市 i 后 (i, t = 1, 2, ..., n) 选取
u
i
=
t
{displaystyle u_{i}=t}
。则由于
u
i
{displaystyle u_{i}}
不大于 n 而
u
j
{displaystyle u_{j}}
不小于1;因此,每当
x
i
j
=
0
{displaystyle x_{ij}=0}
时满足约束。对于
x
i
j
=
1
{displaystyle x_{ij}=1}
,我们有:满足约束。
相关
- 气管气管(trachea)是连接喉部与肺部的通道,腹侧由软骨环组成,背侧由平滑肌所组成,向上以声带为出口,向下分支称之为支气管(bronchus)。组成气管的软骨为透明软骨。Template:Lower respir
- 冠状动脉搭桥手术冠状动脉旁路移植(英语:Coronary artery bypass graft,常缩写为CABG)或心脏绕道手术,俗称冠脉搭桥或搭桥,即冠状动脉旁路移植术,是一项缓解心绞痛和减少冠心病死亡风险的手术。搭桥
- 常任理事国联合国安全理事会常任理事国是联合国安全理事会中的常任成员(俗称五常),五个创始成员国是二战期间同盟国中的五大国。其中,中国和俄罗斯的代表政权曾有所改变。中国原由中华民国
- J01MA·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码J01(抗菌药)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO Collaboratin
- 新英格兰医学杂志《新英格兰医学杂志》(英语:The New England Journal of Medicine;简称 NEJM)是由美国麻省医学协会(英语:Massachusetts Medical Society)所出版的同行评审性质之医学期刊。它也是
- 硫酸铜硫酸铜,化学式CuSO4,无水为白色粉末,或因不纯而呈淡灰绿色,是可溶性铜盐。硫酸铜常见的形态为其结晶体,一水合硫酸四水合铜([Cu(H2O)4]SO4·H2O,五水合硫酸铜)为蓝色固体,故俗名为蓝矾
- 流量工程交通工程是土木工程学中的一个分支。运输工程包括:公路交通、铁路交通、航空交通、水上交通、管道交通五项内容。道路交通工程学仅研究道路上的交通,具体地说,就是把人、车、路
- 盐水池盐水池(英文:Brine pool)为位于海洋盆地中含有极高浓度盐水的水池,其盐水的盐度可达周遭海水的3~8倍,这么高浓度的盐来自于地底下盐体构造(英语:salt tectonics)中的盐沉积释出。另
- 美国白人英语 阿尔巴尼亚语 · 阿拉伯语 · 美国手语 · 新阿拉姆语(英语:Neo-Aramaic languages) · 亚美尼亚语 · 阿塞拜疆语 · 白俄罗斯语 · 捷克语 · 丹麦语
- 20号州际公路20号州际公路(Interstate 20,简称I-20)是美国州际公路系统的一部分。西起德克萨斯州肯特以东(与10号州际公路交汇),东在南卡罗莱纳州弗洛伦斯与95号州际公路交汇。全长1539.38英里