19

我有几个笛卡尔点的形式： (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)
，不可能有这样的安排。

我不知道该怎么称呼它，
但我会称之为曼哈顿订购。

任何人都可以帮忙吗？

4

6 回答 6

12

如果您正在寻找不重复顶点的排列：

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

这对于一般网格图来说是 NP-Complete 的，请参阅网格图中的Hamilton Paths。

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

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

这又是 NP 完全的。上面的问题可以归结为它。这是因为当且仅当图具有汉密尔顿路径时，最小可能游走具有 n 个顶点。

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

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

您可以进行深度优先搜索以找出答案。如果图是连接的，深度优先搜索也会给你这样的安排。

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

于 2010-07-16T18:22:15.223 回答
4

您可以构建一个图，其中顶点是您的点，边是有效步骤。

然后，您要寻找的是该图的哈密顿路径。在其一般形式中，这是一个 NP 完全问题，这意味着没有已知的有效解决方案（即与点数很好地缩放的解决方案）。维基百科描述了一种随机算法，它“在大多数图表上都很快”并且可能有用：

从一个随机顶点开始，如果有没有访问过的邻居则继续。如果没有更多未访问的邻居，并且形成的路径不是哈密顿路径，则随机均匀地选择一个邻居，并使用该邻居作为枢轴进行旋转。（即，向该邻居添加一条边，并从该邻居中删除一条现有边，以免形成循环。）然后，在路径的新端继续算法。

不过，对于这种特殊情况，可能存在更有效的解决方案。

于 2010-07-16T18:07:06.587 回答
2

把它想象成一个图，其中每个节点最多有四个边。然后进行深度/广度优先搜索。

于 2010-07-16T18:07:59.327 回答
1

这可以简化为最小化每个连续点之间的距离。从 (0,0) 到 (0,1) 只是 1 个单位，但从 (0,0) 到 (1,1) 实际上是 sqrt(2)。因此，如果您将点排列成图形，然后执行简单的最小总距离遍历（旅行推销员），它应该正确排列它们。

编辑：如果您从不想要大于 1 的步长，只需不要添加任何大于 1 的边。遍历仍将正常工作，并忽略任何需要移动 > 1 的路径。

编辑 2：为了进一步澄清，您可以使用任何您希望的边缘选择算法。如果您可以移动 2 个空格，只要空格不是对角线，那么您可以选择在 (0,2) 和 (0,4) 之间放置一条边。最小距离算法仍然有效。只需以巧妙的方式放置边缘，您就可以使用任意数量的选择标准来确定结果。

于 2010-07-16T18:05:23.260 回答
0

一种方法是创建两个排序的坐标列表。一个按 x 排序，一个按 y 排序。然后，递归地找到解决方案。

代码来了（还不确定是什么语言；也许是伪代码？）... 编辑 - 没关系，因为我的回答不如其他人好。

于 2010-07-16T18:05:28.760 回答
0

一个蛮力递归 REXX 例程怎么样...尝试所有可能的路径并打印那些可行的路径。

/* rexx */
point. = 0  /* Boolean for each existing point */
say 'Enter origin x and y coordinate:'
pull xo yo
point.xo.yo = 1  /* Point exists... */
say 'Enter destination x and y coordinate:'
pull xd yd
point.xd.yd = 1  /*  Point exists... */
say 'Enter remaining x and y coordinates, one pair per line:'
do forever
  pull x y
  if x = '' then leave
  point.x.y = 1
end

path = ''
call findpath xo yo path
say 'All possible paths have been displayed'
return

findpath: procedure expose point. xd yd
arg x y path
if \point.x.y then return               /* no such point */
newpoint = '(' || x y || ')'
if pos(newpoint, path) > 0 then return  /* abandon on cycle */
if x = xd & y = yd then                 /* found a path */
  say path newpoint
else do                                 /* keep searching */
  call findpath x+1 y path newpoint
  call findpath x-1 y path newpoint
  call findpath x y+1 path newpoint
  call findpath x y-1 path newpoint
  end
return

示例会话：

Path.rex
Enter origin x and y coordinate:
0 0
Enter destination x and y coordinate:
2 2
Enter remaining x and y coordinates, one pair per line:
0 1
1 1
2 1
1 2

 (0 0) (0 1) (1 1) (2 1) (2 2)
 (0 0) (0 1) (1 1) (1 2) (2 2)
All possible paths have been displayed

不要在任何大的东西上尝试这个 - 可能需要很长时间！但是这个问题从来没有提到任何关于成为最佳解决方案的事情。

于 2010-07-16T20:52:36.093 回答