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 变体，因此精确解仅适用于小问题。参见 Traveling Salesman Problem以获得一般描述。 Software包含一些可能有用的程序的链接。