054,798号。令人惊喜的是，Behzad与Modarres证明了广义旅行商问题可以转化为相同城市数量的标准旅行商问题 ，只是要改变距离矩阵。 优先顺序旅行推销员问题处理城市之间存在访问次序的问题。 旅行购买者问题涉及购买一系列产品的购买者。他可以在若干城市购买这些产品，但价格会有不同，也不...

模拟退火常用于搜索空间离散的情形（如旅行推销员问题、布尔可满足性问题、蛋白质结构预测、作业车间调度问题等）。对于在固定时间内找到近似全局最优优先于找到精确局部最优的问题，模拟退火算法可能优于梯度下降法或分支定界等精确方法。 模拟退火算法解决的问题包含多元目标函数与若干约束。实践中，约束可作为目标函数的一部分进行惩罚。...

算机科学的领域中，组合优化是在一个有限的对象集中找出最优对象的一类问题。在很多组合优化的问题中，穷举搜索／枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。常见的例子有旅行推销员问题和最小生成树。 组合优化涉及运筹学、算法理论和计算复杂性理论，在人...

旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的不同在于它对每个子问题...

车辆路径问题（VRP）是一个组合优化和整数规划问题（英语：Integer_programming）（回答了“为了交付给定的一组客户，车辆车队的最佳路线集是什么？”）。它概括了众所周知的旅行推销员问题（TSP）。它最初出现在1959年George Dantzig和John...

而退火温度按一定速度降低。从模拟退火算法看，最优化问题的解是通过寻找最小能量点找到的，而不是寻找最佳适应点找到的。模拟退火也可以用于标准遗传算法里，只要把突变率随时间逐渐降低就可以了。 演化策略 遗传编程 演化规划 模拟退火 禁忌搜索 旅行推销员问题 最优化 交叉 (遗传算法) 突變 (遺傳演算法)...

是P也不是NPC問題，雖然它明顯是一個NP問題。這是一個典型被認為很難卻還不是NPC問題的例子。 下表列出了一些以決定性命題表示的著名NPC問題： 布尔可满足性问题 N-puzzle問題（華容道問題） 背包問題 漢彌爾頓迴圈問題 旅行推销员问题 子圖同構問題：（Subgraph isomorphism...

问题是NP类中“最难”的问题，也就是说它们是最可能不属于P类的。这是因为任何NP中的问题可以在多项式时间内变换成为任何特定NP完全问题的一个特例。例如，旅行推销员问题的判定问题版本为NP完全。所以NP中的任何问题的任何特例可以在多项式时间内转换成旅行商问题的一个特例。所以若旅行商问题...

在计算复杂性理论内，函数问题（英語：Function problem）或者功能性问题是一种计算问题（英语：computational problem），对任何一种输入都预期会有单一个输出，但是输出不像是决定性问题一样这么单纯。换句话说，输出不只是或否，比决策问题复杂得多。重要的范例像是旅行推销员问题...

图的遍历问题分为四类： 遍历完所有的边而不能有重复，即所謂“欧拉路径问题”（又名一笔画问题）； 遍历完所有的顶点而没有重复，即所谓“哈密頓路径问题”。 遍历完所有的边而可以有重复，即所谓“中国邮递员问题”； 遍历完所有的顶点而可以重复，即所谓“旅行推销员问题”。 对于第一和第三类问题...

中国邮递员问题（也称路线检查问题，Route Inspection Problem）是一个图论问题。此問題為在一個連通的無向圖中找到一最短的封閉路徑，且此路徑需通過所有邊至少一次。现实意义中，中国邮递员问题就是在一個已知的地區，郵差要設法找到一條最短路徑，走過此地區所有的街道，且最後要回到出發點。 此問題...

P：包含可以使用确定型图灵机在多项式时间内解决的决定性问题。 NP：包含可以使用非确定型图灵机在多项式时间内解决的决定性问题。 ZPP：包含可以使用概率图灵机在多项式时间内零错误解决的决定性问题。 RP：包含可以使用概率图灵机在多项式时间内解决的决定性问题，但它给出的两种答案中（是或否）只有一种答案是一定正确的，另一种则有几率不正确。...

蚁群优化算法已应用于许多组合优化问题，包括蛋白质折叠或路由车辆的二次分配问题，很多派生的方法已经应用于实变量动力学问题，随机问题，多目标并行的实现。它也被用旅行推銷員問題的拟最优解。在图表动态变化的情况下解决相似问题时，他们相比模拟退火算法和遗传算法方法有优势；蚁群算法可以...

a m ( G ) ⩽ 2 r a d ( G ) {\displaystyle diam(G)\leqslant 2rad(G)} 图论中著名的问题。 称 G {\displaystyle G} 是连通的，如果非空图 G {\displaystyle G} 的任意两个顶点之间均有一条路相连。 称...

该方法最初是由阿尔萨·兰德和艾莉森·哈考特在1960年由英国石油公司赞助的伦敦经济学院进行离散规划研究时提出的，目前已成为解决NP困难优化问题最常用的工具。“分支定界”一词最早出现在解决旅行推销员问题的时候。 分支定界法的目的是从可行解集合 S {\displaystyle S} 中选出一个解 x {\displaystyle...

根据定义，所有P问题都属于NP——直接将非确定性图灵机当作普通图灵机使用即可。另外，许多常见的难解问题都属于NP，例如旅行推销员问题的决定性问题版本、图论中的分团问题等，但尚不清楚这些问题是否其实亦属于P。即，尚未证明图灵机的非确定性在解决这些问题时确实必要。这便是著名的P/NP问题。 PSPACE类问题...

一个加权图在图中的每条边上给出一个值（权重）。加权图中一条道路的权是经过的边的权之和。有时使用成本（cost）或长度一词代替权。 图论术语 最短路问题 旅行推销员问题 加权道路问题 圈空间（英语：Cycle space） Bondy, J. A.; Murty, U. S. R. Graph Theory with...

最长路径，然后将其长度与数k进行比较来将其用于解决该决定问题。因此，最长的路径问题是NP难的。问题“在给定图中是否存在具有至少k条边的简单路径”是NP完全的。 在具有非负边权的加权完全图中，加权最长路径问题与旅行推销员问题相同，因为最长路径总是包括所有顶点。 在加权图G中两个给定顶点s和t之间的最长...

1994年，他的論文《分子計算應用於解決組合問題》中，描述實驗使用 DNA 作為一個計算系統。利用此系統，他解決了一個七節點的哈密頓圖問題，一個類似旅行推銷員問題的NP完全問題。 雖然解決了七個節點的實例是微不足道的，但該論文是第一個已知「利用DNA來作計算」...

中一個染色體代表的答案是155這個整數，那染色體本身可能就是10011011這個字串。 更實際一點的問題是我們可能想要解決一個旅行推銷員問題。對這個問題，我們的目的是要找出一個距離最短，讓我們的推銷員可以拜訪完所有城市的順序。假設我們現在有六座城市，分別是 A、B、C、D、E、和F。那麼一個照順序列...

问题的整数解，也可以用来解决常规的、未必可微的凸优化问题。利用切割平面法求解 MILP 由 Ralph E. Gomory 引入。 MILP 的切割平面法通过将整数问题线性松弛为非整数线性问题，并对其进行求解，来求解 MILP 问题...

。解决该问题是NP困难的。但是伊萨·威廉姆斯和夏尔马以及提出了可以在接近多项式时间内解决该问题的启发式。 度受限最小生成树（英语：degree-constrained spanning tree）是一棵树，其每一个顶点连接的顶点数都不超过d。对一些特定的d值，该问题类似于旅行推销员问题。该问题也是NP困难的。...

parameters），一組定義揚聲器單體低頻表現的機電參數 拖車穩定計畫（Trailer stability program） 旅行推銷員問題（Travelling salesman problem） 3-三甲基矽基丙酸（Trimethylsilylpropanoic acid） 磷酸鈉（Trisodium...

份真值表，每个条款同时在真值表的每一行进行评估。 通过对所有m个子句的重叠透明片进行一次拷贝操作，就可以得到解。 Shaked等人（2007）已经解决了旅行推销员问题 by using an optical approach. 所有可能的TSP路径都已生成并存储在一个二进制矩阵中，该矩阵与另一个包含城市间距...

问题，例如缓冲区、成本距离分析、插值和网络路径。其他应用距离摩擦的问题要复杂得多（即NP困难），例如旅行推销员问题和聚类分析，解决它们的自动化工具（通常使用启发式算法，如k-平均聚类）较少在GIS软件中提供，或比较晚才提供。 试举以下一例：一位徒步旅行...

2005-05-05 [2024-01-22].  总理“推销”高铁引关注. 文摘报. 2013-12-10 [2024-01-22]. 进入新世纪之后，相关部委官员注意到，“中国只有卖出八亿件衬衫才能进口一架空客380。”  超级推销员李克强今年5次出访签约1400亿美元. 广州日报. 2014-12-29...

第四季于2025年5月15日释出。 該部動畫為獨立單元劇，每集之間的劇情並無連貫，而每集片長不超過20分鐘。每一集由不同的配音員和工作人​​員創作，不過某些劇集可能源自同一製作團隊。該劇的標題是指每集的劇情與前者三個主題相互聯繫，但並非每集都包含這三大要素。...

algorithm），這是一種針對旅行推銷員問題的精確指數時間算法。 1971年，他與傑克·埃德蒙茲（英语：Jack Edmonds）共同開發了埃德蒙茲-卡普演算法，用於解決網路上的最大流問題。1972年，他發表一篇在複雜性理論中具有里程碑意義的論文《組合問題中的可減少性》，其中他證明了21個NP-完全問題。...

算在能源消耗、空間需求以及效率上優於電子電腦，且脱氧核醣核酸運算為具有高度平行（見平行運算）的計算方式。許多其他問題，包括多種抽象機器的模擬、布爾可滿足性問題，以及有界形式的旅行推銷員問題，皆曾利用脱氧核醣核酸運算做过分析。由於小巧緊密的特性，脱氧核醣核酸也成為密碼學理論的一部分，尤其在於能夠利用脱...

錄。較早時，參與者可以使用私人交通（如汽車或自行車）接駁，因此可以以少於16小時完成。後來吉尼斯更改了規則，禁止了私人交通。 紐約地鐵挑戰賽 旅行推銷員問題 Alwakeel, Ramzy. Tube challenger reclaims world record for trip around...

問題的補集的一個複雜度類。像是，若一個語言屬於NP，則此語言的補集則屬於Co-NP。（注意這裡不代表NP的補集就等同於Co-NP - 有一些語言同時是NP也是Co-NP，也有語言兩者皆非。） 一個複雜度類裡面"最難的問題"代表這個複雜度類裡面所有的問題都可以歸約為這個問題...