3

我目前正在做一个项目，在该项目中我必须使用包含随机数的二维数组执行任务。该数组形成一个网格，表示一座山的山峰（高度）。我解决了除最后一项之外的所有任务：

最后一项任务是查找是否存在从最小峰值到最高峰值的路径（不一定是最短的）。路径应该由不断增长的山峰组成，我不能踩到较低的山峰。

为简单起见，这里有一个示例，表示为 3x3 网格（原始的要大得多，并且不必像正方形，它是根据用户的需要生成的，并且数字是完全随机的）。

2  4  5    
1  3  8
9  7  10

可能的方式是 1-3-7-10、1-3-8-10、1-2-4-5-8-10。

我很确定，我应该使用某种递归。我读到了一个*探路者，但要使用它，我必须有一个带有“障碍”的“地图”（我无法跨过的节点=较小的峰），而这正是我无法制作的，因为您只能在旅途中找到它。

我的意思是我可以将数字 7 放在“例外列表”上——因为步骤 1-9-7 是被禁止的，但步骤 1-3-7-10 是完美的，所以将 7 放在例外列表上是错误的。

4

3 回答 3

3

关键是首先将您的数组转换为“有向图”，这是一个有向图，仅包含根据您的规则的有效单元格到单元格的移动。这个有向图将是一个数组或条目列表，包括： {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* 算法或其他任何算法。

（注意：我没有发布完整的答案，因为我假设您想自己这样做）

也就是说，您可以通过回溯进行强力递归搜索。这是最简单的解决方案，尽管可能不是最有效的。

于 2012-11-20T19:49:40.157 回答
0

您可以执行以下操作：

  1. 从您的矩阵创建一个加权图（每条边的权重将是 abs（两个节点的值之间的差异））

    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. 删除节点值不上升的解决方案

于 2012-11-20T19:49:53.613 回答
0

（我修复了帖子并将答案放在这里。）

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

因为我已经有了最小和最大的位置，所以我用零包围了原始数组。零是数组的全局最小值，因为默认情况下我从不生成零。有了这个，我不必每次都检查我是否在外面或在数组中（我只踩更大的数字）。

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

然后，我将每个较大数字的“坐标”排入相应的队列中。如果我在实际点 (t[x,y]) 周围找到了所有更大的数字，我将下一个 X,Y 坐标排入队列，这将是新的实际点（如开头所述）。并且检查重复。

整个事情都在一个while循环中，当其中一个队列清空时，它会保持不变。

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

我希望我的解释可以理解，英语不是我的母语。如果你愿意，我可以在这里发布代码。

于 2015-02-05T20:11:12.707 回答