排列笛卡尔点的算法

Question

我有几个形式的笛卡尔点:(x,y)
其中 x 和 y 都是非负整数。

例如
(0,0) , (1,1), (0,1)

我需要一个算法来安排上面的点
以这样一种方式，从一点到另一点
将 x 或 y 改变 1。

换句话说，我想避免
对角线运动。

所以，上面提到的要点将安排如下:
(0,0)、(0,1)、(1,1)。

同样适用于 (0,0),(1,1),(0,2)
不可能有这样的安排。

我不知道该怎么调用它
但我会称之为曼哈顿排序。

有人能帮忙吗？

Answer 1

如果您正在寻找不重复顶点的排列方式:

您似乎要寻找的是网格图中的哈密顿路径。

对于一般网格图，这已知是 NP-Complete，请参阅 Hamilton Paths in Grid Graphs .

因此，您可以使用任何已知的哈密顿路径/欧几里德旅行商问题的近似/启发式/等算法试试运气。

---

如果您正在寻找可以重复的排列，但希望排列中的点数尽可能少:

这又是 NP-Complete。上面的问题可以归结为它。这是因为当且仅当图具有哈密顿路径时，最小可能步数有 n 个顶点。

---

如果你只是在寻找一些点的排列方式，

然后您需要做的就是检查图形是否连通。如果没有连接，就没有这样的安排。

您可以进行深度优先搜索来解决这个问题。如果图是连通的，深度优先搜索也会给你这样的安排。

如果您想要更接近最优的东西(但在相当快的时间内)，您可以使用近似算法来解决欧几里得旅行商问题。