按顺序到达每个点的给定距离内的路径
我有一个二维平面中点的有序列表。我想找到最短的路线，以便它按照给定的顺序至少在距离每个点 X（或更近）的范围内。我如何找到这条路线？
我意识到将确定路线（方向在那里改变）的点将位于周长 X 的圆上，以输入点本身为中心，但我没有进一步了解。
我正在用 Python 实现这一点，但很乐意提供任何理论帮助。
示例：（哎呀我数不过来所以跳过了 7）
回答
也许有一种分析方法，但这个问题当然可以用凸编程来解决。这是一个带有 cvxpy 的 Python 实现，它输出 EPS。
import cvxpy as cp
import numpy as np
def objective(points):
return np.sum(np.linalg.norm(points[1:] - points[:-1]))
def shortest_path(x, centers):
points = cp.reshape(cp.Variable(centers.size), centers.shape)
cost = cp.sum(cp.norm(points[1:] - points[:-1], axis=1))
constraints = []
for i, center in enumerate(centers):
constraints.append(cp.SOC(x, points[i] - center))
prob = cp.Problem(cp.Minimize(cost), constraints)
prob.solve()
return points.value
def main():
x = 0.05
centers = np.random.random_sample((10, 2))
points = shortest_path(x, centers)
print("%!PS-Adobe-3.0 EPSF-3.0")
print("%%BoundingBox:0 0 504 504")
print("72 dup translate")
print("360 dup scale")
print("0 setlinewidth")
for center in centers:
print(*center, x, 0, 360, "arc")
print("stroke")
for i, point in enumerate(points):
print(*point, "lineto" if i else "moveto")
print("stroke")
if __name__ == "__main__":
main()