在六角形网格中找到所有长度为n的可能路径 [英] Finding all possible paths of n length in hexagonal grid

问题描述

假定一个函数采用 s （原边六边形）， f （目标六边形）和 n （路径的长度）值作为参数，并输出所有长度为n的可能路径的列表。要显示问题，请检查下图：

Assume that a function takes s (origin hexagon), f (target hexagon) and n (length of the path) values as parameters and outputs list of all possible paths that has n length. To visualize the problem please check the figure below:

让我们说我们的起源（ s ）是红色的虚线十六进制（2，3）和目标（ f ）是蓝色的虚线的（5，2）。我们希望分5步到达蓝色虚线的十六进制（ n = 5 ）。还应考虑到，如果步行到达特定的十六进制，则在下一步中也可能会停留在该十六进制中。换句话说，可能的路径之一可以是（3，2）-（4，2）-（5，2）-（5，2）-（5，2）。

Let's say our origin (s) is the red dotted hex (2, 3) and the target (f) is the blue dotted one (5, 2). We want to reach blue dotted hex in 5 steps (n = 5). Also consider that if a walk reaches a specific hex, it may stay in that hex as well in the next step. In other words, one of the possible paths can be (3, 2) - (4, 2) - (5, 2) - (5, 2) - (5, 2). It is also counted as 5-length path.

这些是从（2，3）到（5，2）：

(1, 3) - (2, 3) - (3, 2) - (4, 3) - (5, 2)
(3, 3) - (4, 4) - (5, 4) - (5, 3) - (5, 2)
(2, 3) - (2, 3) - (3, 3) - (4, 3) - (5, 2)

我想以某种方式找到所有这些路径。但是，我无法确定哪种算法为解决此问题提供了最有效的解决方案。首先想到的是使用深度优先搜索，但我想知道在这种情况下还有没有更好的选择。

I want to find all of these paths in a way. However, I could not determine which algorithm gives the most efficient solution to handle this problem. The first thing comes to mind is to use depth-first-search but I wonder is there any better alternative to use in this case.

推荐答案

假设您定义以下递归函数，返回成对列表的列表，其中每个成对列表都是从从到到的路径的长度为 i ：

Say you define the following recursive function, returning a list of lists of pairs, where each list of pairs is a path from from to to with length i:

find_paths_from_to_with_length(from, to, i):
    if i == 1:
        if to in neighbors(from) or from == to:
            return [[(from, to)]]
        return []

    all_paths = []
    for node in neighbors(from) + [from]:
        neighbor_all_paths = find_paths_from_to_with_length(node, to, i - 1)
        for path in neigbor_all_paths:
            all_paths.append([(from, node)] + neighbor_path

    return all_paths

然后，您只需使用源，目标和所需长度来调用它即可。

Then you just need to call it with your source, target, and required length.

这篇关于在六角形网格中找到所有长度为n的可能路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！