布置笛卡尔点的算法

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.

因此,您可以尝试使用任何已知的汉密尔顿路径/欧几里德旅行商问题的近似/启发式/等算法.

如果您正在寻找可以重复的安排,但希望安排中的最小点数:

这又是NP-Complete.上述问题可以减少到它.这是因为当且仅当图形具有哈密顿路径时,最小可能步行具有n个顶点.

如果你只是寻找一些点的安排,

然后,您需要做的就是检查图表是否已连接.如果没有连接,就没有这样的安排.

您可以进行深度优先搜索来计算出来.深度优先搜索还将为您提供连接图表时的安排.

如果你想要更接近最优的东西(但是在合理的快速时间内),你可以使用近似算法来解决欧几里德旅行商问题.