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



假设我们的起源（s）是红色的虚线十六进制(2, 3)，而目标（f）是蓝色虚线一个(5, 2)。我们想分5步到达蓝色虚线的十六进制（n = 5）。还应考虑到，如果步行到达特定的十六进制，则在下一步中也可能会停留在该十六进制中。换句话说，可能的路径之一可以是(3, 2) - (4, 2) - (5, 2) - (5, 2) - (5, 2)。它也算作5长度路径。

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

评论

您是要枚举所有路径，还是以某种方式汇总它们（例如找到最便宜的路径）？如果是前者，那么在效率方面就没什么可做的了。
我想列举一下。我知道无法通过定义以特别有效的方式解决问题，但我仍在寻找最佳解决方案。

#1 楼

假设您定义以下递归函数，返回一个成对列表列表，其中每个成对列表都是从from到to的路径，长度为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


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

评论

通过修剪无法导致目的地的部分路径，可以做得比做得更好。例如，从（2,3）到（5,2），我们知道它至少需要3个步骤。如果少于3个步骤可用，则可以放弃此路径。

–亨利
16年2月2日在10:42
谢谢。是否可以通过在网格上添加一些约束来增强此算法。例如。如果我们想从（3，2）到（5，1）分两步走，则无需为（2，2），（2，3）和（3，3）之类的某些邻居继续算法，因为使用剩下的1步不可能达到（5，1）。换句话说，我们可以为每个递归调用指定可能会访问的网格单元限制吗？ @Henry我为Ami添加了此评论。你比我快。另外，您以更好的方式解释了我想说的话。也谢谢你

–多鲁汉·阿尔斯兰（Dorukhan Arslan）
16-2-2在10:48


@Henry是的，很高兴，谢谢！我在计算机上时会添加它。

– Ami Tavory
16年2月2日，11：07
@DorukhanArslan是的，绝对正确！我会在可能的时候进行编辑。

– Ami Tavory
16年2月2日在11:08
我在下面稍微修改了您的答案。我在前面的评论中提到了此实现，但我仍然可能会错过其他一些修剪可能性。

–多鲁汉·阿尔斯兰（Dorukhan Arslan）
16年2月2日在20:53

#2 楼

对于这样的十六进制网格，可以使用以下方法计算两个节点之间的曼哈顿距离：

function dist = manhattan_dist( p, q )

    y1 = p(1);
    y2 = q(1);
    x1 = p(2);
    x2 = q(2);

    du = x2 - x1;
    dv = (y2 - floor(x2 / 2)) - (y1 - floor(x1 / 2));

    if ((du >= 0 && dv >= 0) || (du < 0 && dv < 0))
        dist = abs(du) + abs(dv);

    else
        dist = max(abs(du), abs(dv));
    end

end


以前曾在以下问题中讨论过此问题：


六边形网格上2个六边形之间的距离
曼哈顿六边形网格中砖之间的距离/>我相信，我们可以通过将它与manhattan_dist结合使用来增强Ami的答案：

function all_paths = find_paths( from, to, i )

    if i == 1
        all_paths = to;
        return;
    end

    all_paths = [];
    neighbors = neighbor_nodes(from, 8);
    for j = 1:length(neighbors)
        if manhattan_dist(neighbors(j,:), to) <= i - 1
            paths = find_paths(neighbors(j,:), to, i - 1);
            for k = 1:size(paths, 1)
                all_paths = [all_paths; {neighbors(j,:)} paths(k,:)];
            end
        end
    end

end


最后，如您所见，有一个辅助函数可以获取邻居的索引节点：

function neighbors = neighbor_nodes( node, n )

    y = node(1);
    x = node(2);

    neighbors = [];
    neighbors = [neighbors; [y, x]];

    if mod(x,2) == 1
        neighbors = [neighbors; [y, x-1]];

        if y > 0
            neighbors = [neighbors; [y-1, x]];
        end

        if x < n - 1
            neighbors = [neighbors; [y, x+1]];
            neighbors = [neighbors; [y+1, x+1]];
        end

        neighbors = [neighbors; [y+1, x-1]];

        if y < n - 1
            neighbors = [neighbors; [y+1, x]];
        end

    else
        if y > 0
            neighbors = [neighbors; [y-1, x]];
            neighbors = [neighbors; [y-1, x+1]];
            if x > 0
                neighbors = [neighbors; [y-1, x-1]];
            end
        end

        if y < n
            neighbors = [neighbors; [y+1, x]];
            neighbors = [neighbors; [y, x+1]];    

            if x > 0
                neighbors = [neighbors; [y, x-1]];
            end
        end
    end

end


主要思想是，如果其到目标节点的曼哈顿距离大于当前递归调用的长度n，则简单地修剪该节点。例如，如果可以分两步从(1, 1)转到(0, 3)（n = 2），则应修剪除(1, 2)之外的所有邻居节点。