python - Python 中 TSP 的可扩展实现

Question

我有(比方说)100 分。我想在它们之间生成一条路径，越短越好。这是Travelling salesperson problem .自 TSP is NP-hard ，我对没有找到全局解决方案感到满意。我的方法可以快速提供解决方案并且可以很好地扩展。

生成示例点:

import numpy as np
points = np.random.RandomState(42).rand(100,2)

生成距离矩阵，其中 i,j 条目包含 point[i] 和 point[j] 之间的距离。使用this回答:

z = np.array([[complex(*c) for c in points]]) # notice the [[ ... ]]
distance_matrix = abs(z.T-z)

我如何继续寻找至少具有局部最小路径长度的最短路径？

---

一些相关问题:

本主题:Travelling Salesman in scipy提供用于寻找 TSP 解决方案的代码。不过它以迭代方式工作，因此如果要访问的点数很大，脚本不会在合理的时间内生成解决方案。

本主题:How to solve the Cumulative Traveling Salesman Problem using or-tools in python?没有代码答案，也不关注经典 TSP。

本主题:Optimizing a Traveling Salesman Algorithm (Time Traveler Algorithm)为问题提供迭代解决方案(这意味着扩展性差)

Answer 1

这是一个基于 simulated annealing 的示例(pip install frigidum)。它很可能比其他解决方案慢。我希望发布的 Google OR 会更好，但由于它是一种不同的方法，因此可能会引起人们的兴趣(尽管是为了学习/教育)。

import numpy as np
import frigidum

from frigidum.examples import tsp

points = np.random.RandomState(42).rand(100,2)

tsp.nodes = points
tsp.nodes_count = points.shape[0]

z = np.array([[complex(*c) for c in points]]) # notice the [[ ... ]]
distance_matrix = abs(z.T-z)

tsp.dist_eu = distance_matrix

我们可以使用以下模拟退火方案(<30 秒)； (为了获得更好的解决方案，让 alpha 更接近 .999，和/或以更长的计算成本增加 repeats)

local_opt = frigidum.sa(random_start=tsp.random_start,
           objective_function=tsp.objective_function,
           neighbours=[tsp.euclidian_bomb_and_fix, tsp.euclidian_nuke_and_fix, tsp.route_bomb_and_fix, tsp.route_nuke_and_fix, tsp.random_disconnect_vertices_and_fix],
           copy_state=frigidum.annealing.naked,
           T_start=5,
           alpha=.8,
           T_stop=0.001,
           repeats=10**2,
           post_annealing = tsp.local_search_2opt)

local_opt 是一个元组，其第一个元素是解决方案，第二个元素是目标值(路线长度)。最后它将输出统计信息和找到的最小值； (这不是绘制的那个)。

(Local) Minimum Objective Value Found: 
   7.46016765

我使用 zabop 绘图代码来绘制解决方案；

import matplotlib.pyplot as plt

plt.scatter(points[:,0],points[:,1])

route = local_opt[0]
for a, b in zip(route[:-1],route[1:]):
    x = points[[a,b]].T[0]
    y = points[[a,b]].T[1]
    plt.plot(x, y,c='r',zorder=-1)
plt.gca().set_aspect('equal')

https://imgur.com/rg9Fgzk