相关疑难解决方法(0)

我有（比方说）100 分。我想在它们之间生成一条路径，越短越好。这就是旅行商问题。由于TSP 是 NP 难的，我对没有找到全局解决方案感到满意。我的方法可以快速给出解决方案并且扩展性良好。

生成示例点：

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

生成距离矩阵，其中i,j条目包含point[i]和之间的距离point[j]。使用这个答案：

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

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

一些相关问题：

此线程：scipy 中的旅行推销员提供了用于查找 TSP 解决方案的代码。但它以迭代方式工作，因此如果要访问的点数量很大，则脚本不会在合理的时间内生成解决方案。

此主题：如何使用 python 中的 or-tools 解决累积旅行商问题？没有代码答案，并且不专注于经典 TSP。

此线程：优化旅行商算法（时间旅行者算法）提供了问题的迭代解决方案（这意味着糟糕的扩展）

我正在尝试拟合 2D 点云（x 和 y 坐标）。到目前为止，我在 scipy 的插值包方面取得了有限的成功，最值得注意的是UnivariateSpline，它产生了以下（次优）拟合（请忽略颜色）：

然而，这显然是错误的包，因为我需要一条可以在抛物线点云边缘附近自行弯曲的最终曲线（因此不再是一维函数）。

例如，然后我阅读了interp2d，但不明白我的z数组是什么。是否有我可能忽略的更好的软件包类别？

更新 1：按照评论中的建议，我使用scipy.interpolate.splprep;重新完成了此操作 我的一般设置是：

from scipy.interpolate import splprep, splev
pts = np.vstack((X.ravel(), Y.ravel)) #X and Y contain my points
(tck, u), fp, ier, msg = splprep(pts, u=None, per=0, k=3, full_output=True) #s = optional parameter (default used here)
print('Spline score:',fp) #goodness of fit flatlines after a given s value (and higher), which captures the default s-value as well 
x_new, y_new = …

我在度量空间中有一组 n 个点。这些点都是蓝色的。我在空间中有另一组 n 点。这些点都是红色的。我想以这样的方式连接这些点，即每个蓝点都连接到一个红点，每个红点都连接到一个蓝点。（显然有 n! 种方法可以做到这一点。）我希望找到使连接总长度最小的连接集。这个问题叫什么？