旅行商问题的多项式时间精确解的解释（P≠NP 仍然成立吗？）

很多朋友对于旅行商问题的多项式时间精确解的解释（P≠NP 仍然成立吗？）和不太懂，今天就由小编来为大家分享，希望可以帮助到大家，下面一起来看看吧！

1. 旅行推销员问题（TSP）的背景、重要性和现状介绍

2. 基于数学证明的算法描述

3. 我国31个省会城市TSP问题的最优路径

4. LJ数字算法软件应用的一些思考

5. 英雄帖

6. 结局

7.附录1：提供解决TSP问题的概率算法：遗传算法（python代码）

8.附件2：提供利用遗传算法对china31进行无限PK的python程序

9.附件3：提供使用遗传算法对bays29进行无限PK的python程序（不含起始点）

1. 旅行推销员问题（TSP）的背景、重要性和现状介绍

起源：

旅行推销员问题（TSP）是美国克莱研究所花费100万美元解决的千禧年十大数学问题之一。 TSP 的早期形式可以追溯到19 世纪的数学家和经济学家，例如Leonhard Euler 和W.R. Hamilton。他们提出了一些与TSP相关的问题，但没有明确提出TSP。第一个提出类似TSP问题的人是欧拉，他于1736年解决了柯尼斯堡七桥问题，也可以看作是TSP的简单版本。

定义和发展：

TSP问题的定义：即旅行商必须访问一组城市一次，并返回一条到达出发城市的最小路径。

在20 世纪50 年代，George Dantzig、Ray Fulkerson 和Selmer Johnson 开发了用于求解小规模TSP 实例的线性规划方法。 - 在20 世纪60 年代，David Applegate、William Cook 等人设计了启发式算法和分支定界算法来处理中型TSP 实例。

20世纪80年代，Lin和Kernighan开发了著名的LKH算法，提高了求解大规模TSP实例的效率。 - TSP的难度已被证明，它是一个NP难问题，这意味着一般情况下不存在多项式时间算法可以解决所有TSP实例。

前沿：

近似算法的改进：研究人员一直在努力改进TSP的近似算法，以在实际问题中找到更好的解决方案。这包括改进的启发式、元启发式和混合算法。

量子计算：量子计算的发展也引起了人们对TSP 的兴趣，因为它可能提供比传统计算更快的解决方法。研究人员正在探索如何利用量子计算来解决TSP 等组合优化问题。

大规模问题： TSP 通常针对中小型问题，但研究人员正在寻求扩展其适用性来解决大规模问题。这可能包括更高效的并行算法和分布式计算方法。

多目标TSP: 在多目标TSP中，不仅要找到最短路径，还可以考虑时间、成本等多个目标。研究人员正在寻找该领域更复杂问题的解决方案。

TSP 解决问题的重要性

实际应用：TSP在物流、交通规划、电子电路设计、生物信息学等领域有着广泛的应用。通过解决TSP，可以优化路径规划、降低成本、提高效率、节省时间和资源。

优化问题示例：TSP是组合优化问题的典型代表之一。解决TSP 问题有助于开发可用于解决其他复杂问题的新算法和优化技术。

理论研究：TSP具有重要的理论意义，是NP难问题的代表之一。解决TSP问题有助于理解计算复杂性理论并促进算法设计和分析的进步。

决策支持：在业务决策和规划中，TSP解决方案可以为管理者提供决策支持，帮助他们制定最优路线、资源分配和调度计划。

科学研究：对TSP 问题的研究不断推动计算机科学、数学和运筹学的前沿发展。解决TSP 有助于加深您对组合优化、图论和算法的理解。

经济效益：通过优化旅行商的路线，可以降低油耗、运输成本和效率，从而为企业和政府节省大量资金。

对现有算法的回顾

现有算法

现有算法的局限性

现有算法总结

• 线性规划算法

• 启发法

• 遗传算法

• 分支定界算法

• 详尽的方法

• ETC

除了穷举法外，其他寻找旅行商解的算法都是低概率事件。

目前的算法基本上都是采用优中选优的概率算法，而不是证明算法。

2.基于数学证明的算法描述——算法简称：LJ数学证明算法

1.先讲故事

在一个封闭的圆形轨道的直径的两端，你在一端，一扇编码门（编码极其复杂）在另一端。一个人鲍勃很快从你的左边沿着圆形轨道来到你的右边。如果门没有被破坏，你能确定鲍勃就是知道密码的人吗？答案是肯定的。

现在我们把这个密码改成随机N个TSP问题的最优路径值，最优路径就是密码。如果Bob也能从你的左边沿着圆形轨道快速来到你的右边，是否意味着Bob也是懂得TSP问题的多项式时间算法的人呢？答案是肯定的。

2、我们来设计这样一个密码锁（密码锁=密码A+密码B+密码C）：

在TSPLIB 上随机选择100 道TSP 问题中的8 道

1.bayg29 (1610)

2.bays29（2020）

3.柏林52 (7542)

4.巴西58 (25395)

5. 周五26 (937)

6.gr24 (1272)

7.gr48 (5046)

8.hk48 (11461)

密码A=1610*2020*7542*253959

*937*1272*5046*11461

密码B=hk48的TSP最优解路径（其中之一）

密码C=bays29各点到所有点的最优路径解（不返回起点）

3、使用穷举法暴力破解TSPLIB上的8道TSP问题，获取密码A、B、C的时间：时间：

1.bayg29 (1610) 28!3.0510^29

2.bays29 (2020) 28!3.0510^29

3.berlin52 (7542) 51!1.5510^66

4.巴西58 (25395) 57!4.0510^76

5. fri26 (937) 25!1.5510^25

6. gr24 (1272) 23!2.5610^22

7.gr48(5046)47!2.5910^59

8.hk48(11461)47!2.5910^59

世界上最快的计算机计算速度计算速度=410^17FLOPS/秒

时间=28!/410^17606024365+28!/410^17606024365……+47!/410^176060 243653.2110^51年

注：使用暴力穷举法求解TSPLIB 上8 个问题的最优路径解所需的时间估计直到宇宙消失为止都是不可能的！

4. 鲍勃能在很短的时间内（比如三天）通过这扇门吗？

如果Bob知道这8个问题是TSPLIB上的问题并且不拥有LJ算法：

密码A：直接在TSPLIB上查找8题答案；

密码B：寻找从TSPLIB官网到hk48的最佳路径（因为尚未向公众公布）是困难的，但也是可能的。

密码C:通过各种概率算法解出密码C，准确概率1/28！^28

注意：因为密码C的存在，概率无限接近0，Bob通过这扇门的概率也无限接近0。

（鲍勃使用各种概率算法。即使他很幸运，第一次就得到了最优解，他也不能停止搜索，因为他不知道这是最优解！就时间而言，因为他不知道每个问题需要分配多少时间才能得到最优解，所以最后Bob通过的概率几乎为0！）

如果Bob不知道这8个问题是TSPLIB上的问题，他有LJ数字证明算法：

密码A、密码B、密码C通过LJ数字证明算法解出；

注意：因为Bob拥有LJ证明算法，所以Bob一定能够穿过这扇门！

5. Bob提供的密码A:

密码A=1610*2020*7542*253959*937

*1272*5046*11461

因为LJ数值证明算法在找到TSPLIB中8个问题的最优路径时，也找到了从每个问题的0点到所有点的最优路径，而不返回0点。为了表明不是通过TSPLIB 值直接得到的最优路径，Bob 发布结果如下：

1. bayg29(1610)=[1502, [0, 27, 7, 23, 12, 15, 26, 22, 6, 24, 18, 10, 21, 16, 13, 17, 14, 3, 9, 19 , 1, 20, 4, 5, 11, 8, 25, 28, 2]

2. bays29 (2020)=[1882, [0, 20, 1, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 15, 12, 23 , 7, 27, 5, 11, 8, 4, 25, 28, 2]]

3. 柏林52(7542)=[7302 [0, 21, 30, 17, 2, 16, 20, 41, 6, 1, 29, 22, 19, 49, 28, 15, 43, 45, 24, 3, 5, 14, 4, 23, 47, 37, 36, 39, 38, 33, 34, 35, 48, 31, 44, 18, 40, 7, 8, 9, 42, 32, 50, 11, 27, 26, 25, 46, 12, 13, 51, 10]

4. 巴西58(25395)=[21532, [0, 29, 12, 39, 24, 8, 31, 19, 52, 49, 3, 17, 43, 23, 57, 4, 22, 56, 11, 26 , 42, 48, 46, 50, 51, 9, 34, 40, 1, 53, 54, 7, 21, 47, 2, 28, 32, 44, 55, 45, 33, 14, 36, 13, 27 , 5, 18, 25, 16, 35, 20, 38, 10, 15, 41, 37, 30, 6]]

5. fri26 (937)=[799, [0, 1, 2, 3, 5, 4, 6, 7, 8, 9, 13, 14, 11, 12, 10, 15, 18, 19, 17, 16 , 20, 25, 21, 24, 22, 23]]

6. gr24(1272)=[1165, [0, 15, 5, 23, 11, 3, 22, 8, 12, 13, 19, 1, 14, 18, 17, 21, 16, 9, 4, 20 , 7, 6, 2, 10]]

7. gr48(5046)=[4723, [0, 43, 40, 33, 22, 24, 2, 18, 3, 29, 42, 44, 37, 19, 1, 34, 41, 38, 39, 36 , 46, 17, 45, 27, 6, 28, 12, 47, 15, 10, 35, 5, 25, 14, 23, 9, 11, 30, 4, 32, 7, 21, 13, 8, 20 , 31, 26, 16]]

8. hk48(11461)=[10861, [0, 1, 18, 36, 26, 43, 38, 44, 45, 3, 41, 15, 10, 19, 30, 16, 34, 23, 40, 28 , 25, 47, 14, 42, 20, 32, 4, 2, 24, 31, 27, 12, 21, 11, 17, 13, 37, 6, 46, 7, 5, 33, 35, 39, 9 , 8, 22, 29]]

注意：如上图，因为不会回到起点，所以这个值必须小于TSP最优路径值！（欢迎验证）

6. Bob提供的密码B:

hk48TSP最优路径值=11461

hk48TSP最优路径=[0, 1, 47, 14, 42, 20, 32, 29, 22, 8, 9, 39, 35, 33, 5, 7, 46, 6, 37, 13, 17, 11, 21 , 12, 27, 31, 24, 2, 4, 28, 25, 40, 23, 34, 16, 30, 19, 10, 15, 41, 3, 45, 44, 38, 43, 26, 36, 18 , 0]

7. Bob提供的密码C:

[0, 1882, [0, 20, 1, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 15, 12, 23, 7, 27, 5, 11, 8, 4, 25, 28, 2]]

[1, 1872, [1, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 7, 23, 15, 12, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[2, 1804, [2, 28, 25, 4, 8, 11, 5, 27, 0, 23, 7, 26, 22, 15, 12, 20, 1, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6]]

[3, 1837, [3, 14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 7, 23, 15, 12, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[4, 1891, [4, 20, 1, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 15, 12, 23, 7, 0, 27, 5, 11, 8, 25, 28, 2]]

[5, 1890, [5, 11, 8, 4, 25, 28, 2, 1, 20, 0, 27, 7, 22, 26, 23, 15, 12, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6]]

[6, 1804, [6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 12, 15, 22, 26, 7, 23, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[7, 1846, [7, 23, 12, 15, 26, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[8, 1876, [8, 11, 5, 27, 0, 7, 23, 12, 15, 26, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 4, 25, 28, 2]]

[9, 1879, [9, 12, 15, 23, 7, 26, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[10, 1810, [10, 21, 13, 16, 17, 14, 3, 18, 24, 6, 22, 26, 7, 23, 15, 12, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[11, 1848, [11, 5, 27, 0, 7, 23, 12, 15, 26, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 4, 8, 25, 28, 2]]

[12, 1822, [12, 15, 23, 7, 26, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[13, 1842, [13, 17, 16, 21, 10, 14, 3, 18, 24, 6, 22, 26, 7, 23, 15, 12, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[14, 1863, [14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 7, 23, 15, 12, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[15, 1834, [15, 12, 23, 7, 26, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[16, 1809, [16, 17, 13, 21, 10, 14, 3, 18, 24, 6, 22, 26, 7, 23, 15, 12, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[17, 1833, [17, 16, 13, 21, 10, 14, 3, 18, 24, 6, 22, 26, 7, 23, 15, 12, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[18, 1853, [18, 15, 12, 23, 7, 26, 22, 6, 24, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[19, 1856, [19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 7, 23, 15, 12, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[20, 1857, [20, 1, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6, 22, 26, 15, 12, 23, 7, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[21, 1839, [21, 13, 16, 17, 14, 10, 18, 24, 6, 22, 26, 7, 23, 15, 12, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[22, 1829, [22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 12, 15, 26, 7, 23, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[23, 1860, [23, 12, 15, 26, 7, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[24, 1831, [24, 6, 22, 26, 7, 23, 12, 15, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[25, 1886, [25, 28, 2, 1, 20, 4, 8, 11, 5, 27, 0, 23, 7, 26, 22, 15, 12, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6]]

[26, 1872, [26, 7, 23, 12, 15, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 0, 27, 5, 11, 8, 4, 25, 28, 2]]

[27, 1882, [27, 0, 7, 23, 12, 15, 26, 22, 6, 24, 18, 10, 21, 13, 16, 17, 14, 3, 9, 19, 1, 20, 5, 11, 8, 4, 25, 28, 2]]

[28, 1881, [28, 2, 25, 4, 8, 11, 5, 27, 0, 23, 7, 26, 22, 15, 12, 20, 1, 19, 9, 3, 14, 17, 16, 13, 21, 10, 18, 24, 6]]

注：1、通过现有的概率算法得到的密码C的概率为1/28!^28，成功的概率无限接近于0。

2、密码C的所有值必须小于TSP值2020。

八、结论：

因为Bob 有密码A、密码B 和密码C

这样鲍勃就可以快速开门

LJ数值证明算法可以解决N个随机TSP问题并得到最优路径。因为它的概率极低，而且确实存在，所以它是一个在多项式时间内解决TSP问题的算法的概率无限接近100%！

（为什么无限接近而不等于100%？因为Bob有可能用概率算法找到它。虽然无限接近0，但不等于0）

9.关于LJ数字证明算法的时间复杂度

随机生成任意TSP问题，理论上可以通过LJ数值证明算法在多项式时间O(n^3)内得到其解：

普通笔记本电脑（MateBook 14s）

超级计算机（如果串行计算速度比普通计算快一万倍）

解决29！大约需要0.3小时

解决58！大约需要4小时

解决100个！大约需要50小时

解决1000个！大约需要500小时

解决10000个！大约需要5000小时

解决29！大约需要0.00003小时

解决58！大约需要0.0004小时

解决100个！大约需要0.005小时

解决1000个！大约需要0.05小时

解决10000个！大约需要0.5小时

3. 我国31个省会城市TSP问题的最优路径

1、中国31个省会城市的地理坐标及对应城市：

0.北京：北纬39.9042，东经116.4074

1. 天津：北纬39.3434，东经117.3616

2.石家庄市：北纬38.0428，东经114.5149

3.太原市：北纬37.8706，东经112.5509

4.呼和浩特市：北纬40.8426，东经111.7492

5.沉阳市：北纬41.8057，东经123.4315

6.长春市：北纬43.8171，东经125.3235

7. 哈尔滨： 45.8038N, 126.5349E

8.上海：北纬31.2304，东经121.4737

9. 南京：北纬32.0603，东经118.7969

10.杭州：北纬30.2741，东经120.1551

11.合肥市：北纬31.8206，东经117.2272

12.福州市：北纬26.0745，东经119.2965

13、南昌市：北纬28.7041，东经115.8236

14.郑州市：北纬34.7466，东经113.6253

15. 武汉市：北纬30.5928，东经114.3055

16.长沙市：北纬28.2278，东经112.9388

17. 广州：北纬23.1291，东经113.2644

18、南宁市：北纬22.817，东经108.366

19.海口市：北纬20.02，东经110.35

20. 重庆：北纬29.57，东经106.55

21. 成都：北纬30.5728，东经104.0668

22、贵阳市：北纬26.6474，东经106.6302

23.昆明：25.0389N，102.7183E

24.西安：北纬34.3416，东经108.9398

25.兰州市：北纬36.0611，东经103.8343

26.西宁市：北纬36.6232，东经101.7622

27.济南市：北纬36.6512，东经117.1201

28.银川市：北纬38.4872，东经106.2309

29.乌鲁木齐：北纬43.8256，东经87.6168

30.拉萨市：北纬29.65，东经91.1

2.哈弗

sine函数和四舍五入方法（Haversine函数为通用的球面求距函数）注：因为使用的haversine函数和四舍五入的方法不同，就会产生不同的距离矩阵，不同的距离矩阵会产生不同的TSP的最优路径，所以欢迎研究者对标后再验证 #定义球面两个坐标点直接的距离函数haversine def haversine(lat1, lon1, lat2, lon2): # 将经纬度从度数转换为弧度 lat1 = math.radians(lat1) lon1 = math.radians(lon1) lat2 = math.radians(lat2) lon2 = math.radians(lon2) # 差值 dlat = lat2 - lat1 dlon = lon2 - lon1 # 使用Haversine公式计算球面距离 a = math.sin(dlat/2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon/2)**2 c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a)) # 地球的半径（平均半径，单位：千米） R = 6371.0 # 计算距离 distance = R * c return distance #具体四舍五入方法：不保留小数 distance =round(haversine(float(x1),float(y1),float(x2),float(y2))) 3、中国31个省会城市的TSP最优路径（通过LJ数证算法求得） 31ChinaTSP最优路径值=15167 31ChinaTSP最优路径=[0, 4, 3, 2, 14, 24, 28, 25, 26, 29, 30, 21, 20, 22, 23, 18, 19, 17, 16, 15, 13, 12, 10, 8, 9, 11, 27, 5, 6, 7, 1, 0] 四、对于LJ数证算法软件应用的想法 LJ数证算法软件有偿授予国内1家研究机构或者企业使用希望软件能够被研究机构或者企业按照TSP的数学证明不断优化希望研究机构或者企业能结合自己的算力，使用其服务世界特别说明LJ数证算法也可以解决非对称的TSP问题，因为它们的数学证明是相同的五、英雄帖如果你能找到此文中的TSP问题的最优路径值小于本算法在此文中提供的任意一个最优路径值并得到确认注：首次找到者有效，信息请发到yjia1001@sohu.com，核实后将及时公开六、结尾仅以此文向毕达哥拉斯、欧拉致敬！有合作意向者可以在评论区发一个48个节点对称的TSP问题二维数组（建议随机生成），前五个问题作者会在第一时间（工作时间9:00-20:00，问题发出后24个小时以内）给出最优路径值和最优路径（希望在这之前你做大量的运算有自己的最优路径值好pk）注：软件授权后会及时公布