旅行推销员问题

✍ dations ◷ 2025-04-03 10:51:00 #旅行推销员问题
行商问题(最短路径问题)(英语: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} ,我们有:满足约束。

相关

  • ICD-9编码列表 (001–139)医学导航:病菌细菌(分类)gr+f/gr+a(t)/gr-p(c/gr-o药物(J1p、w、n、m、疫苗)医学导航:病菌细菌(分类)gr+f/gr+a(t)/gr-p(c/gr-o药物(J1p、w、n、m、疫苗)医学导航:病菌细菌(分类)gr+f/gr+a(t)/gr-p(c/gr-o药
  • 锂离子聚合物电池锂聚合物电池(英语:lithium polymer,缩写:Li-Po),又称聚合物锂电池、聚锂电池,是一种锂离子电池。锂聚电池通常是由数个相同的平行子电池芯(secondary cells)来增加放电电流,或由数个
  • 数字图书馆数字图书馆(Digital Library)是一种馆藏以数字化格式存储,可以利用电脑访问的图书馆,而传统图书馆的馆藏则以印刷、微缩胶片或其他媒体等相对格式为馆藏主体。数字化的内容可以
  • 新闻节目新闻节目是指以报导即时消息、探讨时事,通常定时播出的电台或电视节目。新闻节目通常是由多则新闻报导内容所组成,会由一个或多个主播播报。新闻节目可包括现场或预先录制的访
  • 拟卤素拟卤素或类卤素(pseudohalogen)是一种性质类似卤素的无机化合物,其通式为 XY,其中 X 可以是氰基 CN、氰氧基 OCN、硫氰基 SCN 等官能基,而 Y 可以是上述的物质或是卤素原子。如氰
  • 香辛料香料,或名辛香料或香辛料,是一些干 的植物的种子、果实、根、树皮做成的调味料的总称,例如胡椒、丁香、肉桂等。它们主要是被用于为食物增加香味,而不是提供营养。用于香料的植
  • 梅酒梅酒是日本酒类的一种,主要成分包括梅、糖和烧酒。梅酒一般酒精含量约为10-15%,味带酸甜,故亦为一些不嗜酒的人士所爱。日本餐馆提供不同口味的梅酒,也使用梅酒制作鸡尾酒。梅酒
  • span style=color:#ffffff;地理/span希腊位于欧洲东南角,巴尔干半岛南端。其北面与阿尔巴尼亚、北马其顿共和国和保加利亚毗邻,西临爱奥尼亚海,南靠地中海,东靠爱琴海与小亚细亚。希腊国土面积为131940平方千米,由希
  • 萨伏依萨伏依公国(法语:Duché de Savoie、意大利语:Ducato di Savoia)是1416年至1713年间曾经存在于西欧的独立公国,由萨伏依家族统治,领土包括今日意大利西北部和法国的东南部的部分地
  • 1968年格勒诺布尔冬奥会第十届冬季奥林匹克运动会(英语:the X Olympic Winter Games,法语:les Xes Jeux olympiques d'hiver),于1968年2月6日至2月18日在法国格勒诺布尔举行。这是法国第二次主办冬季奥林