在二维数组中进行路径规划

Question

我目前正在从事一个项目，在这个项目中，我需要使用一个包含随机数字的二维数组来执行任务。该数组形成一个网格，表示山峰的高度。我已经解决了除最后一个任务以外的所有任务：

最后一个任务是要查找是否存在一条路径，从最小的山峰到最高点（不一定是最短路径）。路径应由逐渐增高的山峰组成，我不能踏在低于当前位置的山峰上。

以下是一个示例，为简单起见，在 3x3 的网格上表示（原本更大，不一定是正方形的，它是根据用户需求生成的，数字完全是随机的）。

2  4  5    
1  3  8
9  7  10

可能的路径包括1-3-7-10、1-3-8-10、1-2-4-5-8-10。 我相信我应该使用某种递归。我读到过a* 寻路算法，但要使用它，我必须有一个带有“障碍物”的“地图”（我不能走的节点=更小的山峰），这正是我做不到的，因为你只能在进行中才会发现它。 我的意思是，我可以将数字7放在“例外列表”上-例如步骤1-9-7是禁止的，但步骤1-3-7-10很完美，因此将7放在例外列表中将是一个错误。

- P. Zoltan

---

你错过了 1-3-4-5-8-10 :) - Timwi

Answer 1

关键是首先将您的数组转换为“有向图”，该有向图仅由根据您的规则有效的单元格移动组成。此有向图将是一个条目的数组或列表，其中包含：{FromCell，ToCell}。

您的有向图将包含以下数据：

2,4
4,5
5,8
1,2
1,3
1,9
3,4
3,8
3,7
8,10
7,10

从这里开始，您应该能够应用A*算法或其他许多算法。

（注意：我不会发布完整的答案，因为我认为您想自己完成此任务）

---

话虽如此，您可以使用暴力递归搜索和回溯。这是最简单的解决方案，但可能不是最有效的。

- RBarryYoung

---

不错的解决方案 :), 但复杂度可能有点高。创建所有配对加上A*算法的复杂度不是O(n^2)吗？ - Mihai

不，创建这些配对的时间复杂度是O(n)。它们必须是相邻的吗？对于任何给定的FROM单元格，最多只有四个相邻的TO单元格。即使它们不是相邻的，你也可以先按值排序，这样时间复杂度最坏也只有O（N log N）。 - RBarryYoung

抱歉，我的错。这里已经很晚了 :) - Mihai

如果我理解正确的话，我可以通过执行简单搜索并将有效的移动放入另一个应该是动态的2D数组来收集有效的移动。然后，当我沿着峰行进时，我应该查看峰是否与有效移动匹配，对吗？此外，由于我在编程方面仍然是新手，我不知道如何递归地实现您的解决方案。 - P. Zoltan

Answer 2

你可以这样做：

从矩阵中创建加权图（每条边的权重将是两个节点值之间差的绝对值）：

2 - 4 - 5

|   |   |

1 - 3 - 8

|   |   |

9 - 7 - 9 

(2, 4) 的权重为 abs(4 - 2) = 2

(4, 5) 的权重为 abs(4 - 5) = 1

1. 应用一种最短路径算法，该算法考虑边的权重 http://www.informatics.susx.ac.uk/courses/dats/notes/html/node147.html

2. 删除节点值不按升序排列的解决方案

- Mihai

---

你是指用mod运算符进行模运算，还是只是取绝对值的差异？ - lfxgroove

我喜欢这个想法，但我认为你没有完全理解我的问题。我的问题是，我需要一个“地图”或“黑名单”，以避免在使用路径算法时出现非法步骤。 - P. Zoltan

你的想法可能对这个任务有好处，但我还不知道如何使用图表，这可能会使我的任务实现变得更加复杂（对于像我这样的初学者来说，一切都很困难）。 - P. Zoltan

如果使用公式b>a?1:无穷大代替abs(b-a),则你的算法可以解决OP所遇到的问题。但是，C#不支持表示无穷大，所以需要使用int.MaxValue代替，但这看起来有点不靠谱:) - Timwi

顺便问一下，有没有任何编程语言可以表示无穷大？ - P. Zoltan

Answer 3

（我修复了帖子并在此处放置了答案。）

这是我最终解决它的方法：

由于我已经有了最小和最大位置，所以我用零将原始数组包围起来。零是数组的全局最小值，因为我从不默认生成零。这样我就不必每次检查我是否在或在数组中（我只踩在更大的数字上）。

我创建了两个队列（QueueX，QueueY）。从最小的数字开始（我在开始时将其位置入队到队列中，将其赋给数组t[x，y]的x，y变量，然后出队）。

然后，我将每个更大数字的“坐标”入队到相应的队列中。如果我发现实际点（t[x，y]）周围的所有更大数字，我会将下一个X，Y坐标入队，这将是新的实际点（如开始时所述）。然后进行检查。

整个过程都在while循环中，该循环保持在其中一个队列为空的情况下。

如果在任何给定的检查中，X，Y与最大峰值的X，Y坐标相同，则返回并存在路径。在while循环结束时，如果X，Y与最大值的X，Y不同，则没有路径。

希望我的解释能够让您有所理解，英语不是我的母语。如果您愿意，我可以在这里发布代码。

- P. Zoltan