排列笛卡尔点的算法

Question

我有一些笛卡尔坐标的点，形式如：(x,y)
其中x和y都是非负整数。

例如：
(0,0) ，(1,1)，(0,1)

我需要一个算法来排列上述点
使得从一个点到另一个点时
要么x加一，要么y加一。

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

因此，上述提到的点将被排列为：
(0,0), (0,1), (1,1)。

对于(0,0),(1,1),(0,2)
没有这样的排列可能。

我不确定该怎么称呼它
但我会称之为曼哈顿排序。

有人能帮忙吗？

- simplfuzz

---

你是否总是从0,0（或最左下角的点）开始？还是可以从任何点开始？ - cape1232

我喜欢这个问题，但你需要具体说明，例如你是先水平移动（尝试找到一个x值+1但y值与当前点相同的点）还是垂直移动？如果两个点相同会发生什么？你能倒退吗？例如从（2,2）到（2,1）？ - Jesse Naugher

等一下，你是在寻找从特定的起点/终点到达的路径，还是要经过每个点的路径？我理解为前者，但其他人似乎认为是后者...如果是后者，那么你可以重复经过同一个点吗？ - BlueRaja - Danny Pflughoeft

笛卡尔积最近很受欢迎。看到这个：http://blogs.msdn.com/b/ericlippert/archive/2010/06/28/computing-a-cartesian-product-with-linq.aspx或者这个： https://dev59.com/JXA75IYBdhLWcg3w0cjx今天我的大脑太紧张了，无法阅读上述任何一个链接，也许它们可以帮助你。 - FiveTools

@BlueRaja 我正在寻找一条从每个点出发的路径。我可以经过同一个点多次。 - simplfuzz

Answer 1

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

您似乎在寻找网格图中的哈密顿路径。对于一般的网格图，这已知是NP完全问题，请参见Hamilton Paths in Grid Graphs。

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

---

如果您想要一个可以重复的排列，但是希望排列中的点数量尽可能少：

这同样是NP完全问题。上述问题可以归约为此问题。这是因为最小可能路径有n个顶点，当且仅当图形具有哈密顿路径。

---

如果你只是想找到一些点的排列方式，

那么你需要检查图是否连通。如果不连通，则不存在这样的排列。

你可以进行深度优先搜索来确定这一点。如果图是连通的，深度优先搜索也会给你这样的排列。

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

- Aryabhatta

Answer 2

你可以用点作为顶点，有效步骤作为边来构建图形。然后你要找的是这个图形的哈密顿路径。一般情况下，这是一个NP完全问题，这意味着没有已知的高效解决方案（即随着点数增加而扩展得好）。维基百科描述了一个随机算法，它在大多数图形上都很快，并可能有用：

从一个随机顶点开始，如果有未访问的邻居，则继续。如果没有更多未访问的邻居，并且形成的路径不是哈密顿路径，则随机选择一个邻居，并使用该邻居作为枢轴旋转。（也就是说，添加一条到该邻居的边，并删除该邻居的一个现有边，以便不形成环。）然后，在路径的新末端继续算法。

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

- Thomas

---

你只是证明了哈密顿路径问题比解决这个问题更难，但你并没有证明当前的问题是NP完全问题。 - Aryabhatta

我看了一下那个算法，不是很清楚...你能再解释一下吗？可以用伪代码来说明吗？ - simplfuzz

嗯，你说得对，那个描述相当不精确。也许这可以帮助：https://dev59.com/5nI-5IYBdhLWcg3wKVA9 - Thomas

Answer 3

可以将其看作一个图，其中每个节点最多有四条边。然后进行深度/广度优先搜索。

- BlueRaja - Danny Pflughoeft

---

这很可能是正确答案，因为问题没有涉及最优性或类似的内容。 - Nick Larsen

Answer 4

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

编辑：如果您永远不希望步骤大于1，请不要添加任何大于1的边缘。遍历仍将正常工作，并忽略需要移动> 1的任何路径。

编辑2：为了进一步澄清，您可以使用任何边缘选择算法。如果您可以接受它移动2个空格，只要空格不是对角线，那么您可以选择在（0,2）和（0,4）之间放置边缘。最小距离算法仍将起作用。只需以聪明的方式放置边缘，您就可以使用任何数量的选择标准来确定结果。

- drharris

---

有人删掉了一条相当好的评论；在你的标准中，顺序（0,0）->（1,1）->（5,0）是有效的，但不符合他的标准。 - nlucaroni

不，我认为没有人建议您一次性跨越一个以上的步长。问题不在于对角线步进。虽然我提到的这三个点在作者的标准下没有指定顺序，但像这样的列表更适合讨论，(3,2) -> (0,2) -> (0,3) -> (1,3)。在这里，尽管步骤(3,2) -> (1,3)是最小的，但应该避免使用它。 - nlucaroni

这是在假设有解的情况下，并且您可以多次通过点的前提下。对于 { (0,0), (1,0), (0,1) }，您该怎么办？需要更多信息。 - Nick Larsen

@drharris：使用 { (1,0), (1,1), (0,1), (2,1) }，您的旅行商人有一条合法路径，但必须至少经过 (1,1) 两次。您的算法将如何响应此集合？ - Nick Larsen

@drharris：我认为最好在解决方案旁边陈述您的假设，而不是让读者自己去猜测。 - Nick Larsen

Answer 5

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

代码即将到来（还不确定使用什么语言，也许是伪代码？）...编辑-算了，因为我的答案并不像其他一些答案那样好。

- Cam

Answer 6

如何使用暴力递归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

不过，不要在任何大型项目上尝试这样做 - 这可能需要很长时间！但是问题从来没有提到过要求最优解。

- NealB