本文通过零知识证明TSP问题其可以在多项式时间内得到求解目录：1、旅行商问题（Travel Salesman Problem：TSP）的背景、重

 

本文通过零知识证明TSP问题其可以在多项式时间内得到求解目录：1、旅行商问题（Travel Salesman Problem：TSP）的背景、重要性和现状介绍2、基于数学证明的算法说明3、中国31个省会城市的TSP问题的最优路径

4、对于LJ数证算法软件应用的一些想法5、英雄帖6、结尾7、附件1：提供一个解决TSP问题的概率算法：遗传算法（python代码）8、附件2：提供一个遗传算法对china31进行无限pk的python程序

9、附件3：提供一个遗传算法对bays29进行无限pk的python程序(不含出发点)10、附件4：中国31省会城市以及本文使用TSPLIB上的8个TSP问题的的二维数组一、旅行商问题（Travel Salesman Problem：TSP）的背景、重要性和现状介绍

起源：旅行商问题（Travel Salesman Problem：TSP）是千禧年美国克雷研究所花100万美金重金求解的千禧年10大数学难题之一TSP的早期形式可以追溯到19世纪的数学家和经济学家，如维尔内尔（Leonhard Euler）和柯尼斯（W.R.汉密尔顿）。

他们提出了一些与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-hard问题，这意味着在一般情况下没有多项式时间算法来解决所有TSP实例。

前沿：近似算法的改进: 研究者一直在努力改进TSP的近似算法，以在实际问题中找到更好的解决方案这包括改进启发式算法、元启发式方法和混合算法量子计算: 量子计算的发展也对TSP产生了兴趣，因为它可能提供比传统计算更快的求解方法。

研究人员在探索如何使用量子计算来解决TSP等组合优化问题大规模问题: TSP通常针对小到中等规模的问题，但研究者正在寻求扩展其适用性，以解决大规模问题这可能包括更高效的并行算法和分布式计算方法多目标TSP: 在多目标TSP中，不只是寻找最短路径，还可以考虑多个目标，如时间、成本等。

研究者在这个领域寻找更复杂问题的解决方案TSP问题解决的重要性实际应用：TSP在物流、交通规划、电子电路设计、生物信息学等领域具有广泛的应用通过解决TSP，可以优化路径规划，减少成本，提高效率，节省时间和资源。

优化问题范例：TSP是组合优化问题的典型代表之一解决TSP问题有助于开发新的算法和优化技术，这些技术可以用于解决其他复杂问题理论研究：TSP具有重要的理论意义，它是NP-hard问题的代表之一解决TSP问题有助于理解计算复杂性理论，并推动了算法设计和分析的进展。

决策支持：在商业决策和规划中，TSP的解决可以为管理者提供决策支持，帮助他们制定最佳路线、资源配置和排程计划科学研究：TSP问题的研究不断推动计算机科学、数学和运筹学领域的前沿解决TSP有助于深化对组合优化、图论和算法的理解。

经济效益：通过优化旅行商的路径，可以降低油料消耗、减少运输成本和提高效率，从而为企业和政府节省大量资金现有算法的综述现有算法现有算法的局限性现有算法总结• 线性规划算法• 启发式算法• 遗传算法• 分支限界算法。

• 穷举法• 等等除穷举法外，其他算法求出旅行商解是一种低概率事件目前算法基本使用的都是优中选优的概率算法，而非证明算法二、基于数学证明的算法说明——算法简称：LJ数证算法1、先讲一个故事在一个密闭的圆形轨道的一个直径的两端，一端是你，另一端是一扇密码门（密码极其复杂）。

一个人Bob从你的左边沿圆形轨道快速的来到了你的右边，在门没有坏的情况下，你是否可以肯定Bob是知道密码的人答案是一定的现在我们把这个密码改成是随机N个的TSP问题的最优路径值和最优路径为密码如果Bob也能从你的左边沿圆形轨道快速的来到了你的右边，是否说明Bob也是知道TSP问题在多项式时间算法的人呢？答案也是一定的。

2、我们来设计这样一把密码锁（密码锁=密码A+密码B+密码C）：随机选择TSPLIB上100以内的8个TSP问题1、bayg29（1610）2、 bays29 （2020）3、 berlin52（7542）

4、brazil58（25395）5、fri26 （937）6、 gr24（1272）7、 gr48（5046）8、 hk48 （11461）密码A=1610*2020*7542*253959*937*1272*5046*11461

密码B=hk48的TSP最优解路径（其中一个）密码C=bays29的每一个点到所有点的最优路径解 (不回到出发点)说明：为什么选择TSPLIB上的TSP问题作为密码锁的来源，是因为其是全球公认的TSP问题测试打靶数据提供方，其提供的最优路径值是全球目前已知的此问题的最小路径，任何优秀的算法只能小于或者等于它，更应该包括数学证明算法。

3、用穷举法暴力破解TSPLIB上的8个TSP问题得到密码A、B、C的时间Time：1、 bayg29（1610） 28!≈3.05×10^292、 bays29 （2020） 28!≈3.05×10^29

3、berlin52（7542） 51!≈1.55×10^664、 brazil58（25395） 57!≈4.05×10^765、 fri26 （937） 25!≈1.55×10^256、 gr24（1272）

23!≈2.56×10^227、 gr48（5046） 47!≈2.59×10^598、hk48 （11461） 47!≈2.59×10^59世界上最快的计算机计算速度computation speed

=4×10^17FLOPS/秒Time=28!/4×10^17×60×60×24×365+28!/4×10^17×60×60×24×365……+47!/4×10^17×60×60×24×365≈3.21×10^51 年

注：用暴力穷举法求解TSPLIB上的8个问题的最优路径解需要的时间直到宇宙消失估计都不可能完成！4、Bob能不能在一个极短的时间（比如三天）通过这扇门呢？假如Bob知道这8个问题是TSPLIB上的问题，不拥有LJ数证算法：

密码A：在TSPLIB上直接找到8个问题的解;密码B：找到TSPLIB官网要到hk48的最优路径（因为其没有对外公布），有难度但有实现的可能密码C: 通过各种概率算法求解密码C,准确的概率≈1/28!^28

注：因为密码C的存在，概率无限接近于0，Bob通过这扇门的概率也无限接近于0（ Bob使用各种概率算法即使运气非常好第一时间就得到了最优解，他也无法停止继续搜索，因为他不知道它就是最优解！从时间上来说，因为他不知道每个问题究竟需要分配多少时间才一定能够得到最优解，因此最后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数证算法求出TSPLIB8个问题的最优路径时，也求出了每一个问题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、 berlin52(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、 brazil58(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最优路径值=11461hk48TSP最优路径=[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，成功概率无限接近于02、密码C所有的值必小于TSP值20208、结论：因为Bob有密码A、密码B、密码C所以Bob能够快速的打开这扇门LJ数证算法求解N个随机TSP问题都能得到最优路径，因为其概率极低，而其又真实的存在，所以其是多项式时间解决TSP问题算法的概率无限接近100%！。

（为什么是无限接近，而不是等于100%呢？因为Bob有概率算法找到的可能性，虽然无限接近于0，但是不等于0）9、关于LJ数证算法的时间复杂度随机产生任意一个TSP问题，理论上来说通过LJ数证算法都能在多项式时间O(n^3)得到它的解：

普通笔记本电脑（MateBook 14s）超级计算机（如果比普通计算串行计算速度提高10000倍）解决 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小时

三、中国31个省会城市的TSP问题的最优路径1、中国31个省会城市的地理坐标及对应城市：0. 北京市：39.9042°N, 116.4074°E1. 天津市：39.3434°N, 117.3616°E2. 石家庄市：38.0428°N, 114.5149°E

3. 太原市：37.8706°N, 112.5509°E4. 呼和浩特市：40.8426°N, 111.7492°E5. 沈阳市：41.8057°N, 123.4315°E6. 长春市：43.8171°N, 125.3235°E

7. 哈尔滨市：45.8038°N, 126.5349°E8. 上海市：31.2304°N, 121.4737°E9. 南京市：32.0603°N, 118.7969°E10. 杭州市：30.2741°N, 120.1551°E

11. 合肥市：31.8206°N, 117.2272°E12. 福州市：26.0745°N, 119.2965°E13. 南昌市：28.7041°N, 115.8236°E14. 郑州市：34.7466°N, 113.6253°E

15. 武汉市：30.5928°N, 114.3055°E16. 长沙市：28.2278°N, 112.9388°E17. 广州市：23.1291°N, 113.2644°E18. 南宁市：22.817°N, 108.366°E

19. 海口市：20.02°N, 110.35°E20. 重庆市：29.57°N, 106.55°E21. 成都市：30.5728°N, 104.0668°E22. 贵阳市：26.6474°N, 106.6302°E

23. 昆明市：25.0389°N, 102.7183°E24. 西安市：34.3416°N, 108.9398°E25. 兰州市：36.0611°N, 103.8343°E26. 西宁市：36.6232°N, 101.7622°E

27. 济南市：36.6512°N，117.1201°E28. 银川市：38.4872°N, 106.2309°E29. 乌鲁木齐市：43.8256°N, 87.6168°E30. 拉萨市：29.65°N, 91.1°E

2、Haversine函数和四舍五入方法（Haversine函数为通用的球面求距函数）注：因为使用的haversine函数和四舍五入的方法不同，就会产生不同的距离矩阵，不同的距离矩阵会产生不同的TSP的最优路径，所以欢迎研究者对标后再验证

#定义球面两个坐标点直接的距离函数haversinedef haversine(lat1, lon1, lat2, lon2):# 将经纬度从度数转换为弧度lat1 = math.radians(lat1)

lon1 = math.radians(lon1)lat2 = math.radians(lat2)lon2 = math.radians(lon2)# 差值dlat = lat2 - lat1dlon = lon2 - lon1

# 使用Haversine公式计算球面距离a = math.sin(dlat/2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon/2)**2c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))

# 地球的半径（平均半径，单位：千米）R = 6371.0# 计算距离distance = R * creturn distance#具体四舍五入方法：不保留小数distance =round(haversine(float(x1),float(y1),float(x2),float(y2)))

3、中国31个省会城市的TSP最优路径（通过LJ数证算法求得）31ChinaTSP最优路径值=1516731ChinaTSP最优路径=[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]

注：目前网上能够查到的最优路径=15609.4771(数据来源于CSDN) 欢迎广大计算机算法研究者对标后验证以上数据的准确性四、对于LJ数证算法软件应用的想法LJ数证算法软件有偿授予国内1家研究机构或者企业使用

希望软件能够被研究机构或者企业按照TSP的数学证明不断优化希望研究机构或者企业能结合自己的算力，使用其服务世界特别说明LJ数证算法也可以解决非对称的TSP问题，因为它们的数学证明是相同的五、英雄帖如果你能找到此文中的TSP问题的最优路径值小于本算法在此文中提供的任意一个最优路径值并得到确认

作者郑重承诺：你可以共享此软件授权费用总和的30%作者提供了基于遗传算法的pk软件程序——附件2和附件3欢迎下载pk注：首次找到者有效，信息请发到yjia1001@sohu.com，核实后将及时公开六、结尾

仅以此文向毕达哥拉斯、欧拉致敬！具体LJ数证算法软件合作请联系：yjia1001@sohu.com有合作意向者可以在评论区发一个48个节点对称的TSP问题二维数组（建议随机生成），前五个问题作者会在第一时间（工作时间9:00-20:00，问题发出后24个小时以内）给出最优路径值和最优路径（希望在这之前你做大量的运算有自己的最优路径值好pk）

注：软件授权后会及时公布（本文于2023年10月28日公开发表于CSDN，头条，知乎等平台）

免责声明：本站所有信息均搜集自互联网，并不代表本站观点，本站不对其真实合法性负责。如有信息侵犯了您的权益，请告知，本站将立刻处理。联系QQ：1640731186