algorithm - 绘图仪绘制“n”个点的最小累积距离

Question

给出了一个绘图仪，它可以绘制以“x”和“y”坐标形式提供给它的点。绘图手只能水平或垂直移动。输入将以“n”坐标列表的形式提供：{(x1,y1), (x2,y2} ... (xn,yn)}。最初，绘图仪将位于原点。

需要提供一个算法来返回所有“n”点的列表，这些点表示绘图仪手按照输出列表中提供的确切顺序绘制所有“n”点的最小累积距离。

有了一些最初的回忆，我很想输出将是一个“n”点的列表，这些点按递增的“x”和“y”坐标排序。

例如，

输入- (3, 5), (1, 2), (4, 3)

输出- (1, 2), (3, 5), (4, 3)

但是，恐怕这将是正确的算法。

所以，问题是：推导出一个算法来解决这个问题，如果上面是正确的，那么证明它。

此外，如果绘图仪也被允许沿对角线移动，派生算法将观察到什么变化！

Answer 1

这个问题是旅行商问题的 NP-hard 变体，因此精确解仅适用于小问题。有关一般描述，请参阅旅行推销员问题。软件有一些可能有用的程序的链接。

Answer 2

正如 Patricia 在她的评论中所写的那样，这相当于带有曼哈顿距离的旅行推销员问题的度量。这是一个 NP 完全优化问题，最好用近似或启发式算法解决现实生活中的问题（比如要绘制超过 10 个点）。任何总是产生最佳解决方案的确定性算法都可能会非常糟糕地扩展到更大的问题规模。