如何在这种迷宫中找到最短路径

Question

Red Dot - Represents the initial location
Black Dot - Already occupied
Green - Free to occupy
Destination - Boundry of the matrix [which means either x = 0 or y = 0 or x = 8 or y = 8]

示例：

red dot 一次只能放置一个移动，并且可以移动到附加到它的六个绿色圆圈之一。在这种迷宫中计算最短路径的最快方法是什么。

Answer 1

您遇到的是一道 "simple" 图形问题。图形连通性是您拥有的合法移动。起始节点是您的红点。要获得单个终端节点，请在给定迷宫外再创建一个圆圈；以零成本移动将所有真实出口节点连接到新圆。

现在，应用 Dijkstra 算法。完成。

另一种看待问题的方法是递归。移动红点，将旧位置标记为黑色。从新位置重复。 Return 当您退出（return 路径长度 1）或没有合法移动（return 路径长度无限）。保持已知的最短路径。

这些能让你摆脱困境吗？

Answer 2

A*搜索算法

（来自： https://en.wikipedia.org/wiki/A*_search_algorithm )

以下伪代码描述算法[可疑-讨论]：

function A*(start,goal)
    ClosedSet := {}       // The set of nodes already evaluated.
    OpenSet := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
    Came_From := the empty map    // The map of navigated nodes.


    g_score := map with default value of Infinity
    g_score[start] := 0    // Cost from start along best known path.
    // Estimated total cost from start to goal through y.
    f_score := map with default value of Infinity
    f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

    while OpenSet is not empty
       current := the node in OpenSet having the lowest f_score[] value
        if current = goal
            return reconstruct_path(Came_From, goal)

       OpenSet.Remove(current)
       ClosedSet.Add(current)
       for each neighbor of current
           if neighbor in ClosedSet 
               continue     // Ignore the neighbor which is already evaluated.
        tentative_g_score := g_score[current] + dist_between(current,neighbor) // length of this path.
        if neighbor not in OpenSet  // Discover a new node
            OpenSet.Add(neighbor)
        else if tentative_g_score >= g_score[neighbor] 
            continue        // This is not a better path.

        // This path is the best until now. Record it!
        Came_From[neighbor] := current
        g_score[neighbor] := tentative_g_score
        f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)

return failure

function reconstruct_path(Came_From,current)
    total_path := [current]
    while current in Came_From.Keys:
        current := Came_From[current]
        total_path.append(current)
    return total_path

因此，据我了解-您可以将起始节点设置在红点位置\中心位置，并将目标节点设置为x = 0或y = 0或x = 8或y = 8（您可以进行4次函数调用，取最少的)

至于节点的启发值 - 只需将黑色阻塞节点的启发值设置得非常高，这将使它们无法到达，因此算法将绕过它们。

Answer 3

首先，你不需要Dijkstra，因为所有边的值都是一样的。您可以使用简单的 BFS or DFS 算法。最坏情况的复杂度是相同的，但我会使用 BFS，因为它具有更好的平均情况复杂度。然而，O(|V|+|E|) 是最快的，并且已被证明。

如何表示您的图表？最好的方法是为每个 Node 保留一个邻居列表。您示例中的黑点不算作邻居。因此，在您的示例中，每个节点将有 0（完全被黑点覆盖）到 6 个邻居。然后，您可以通过这些列表从任何节点到达任何您可以到达的地方。

BFS 算法有一个属性，它为每个节点分配一个层，这意味着它与起始节点的距离。你从你的起点开始，你的当前层将为 0。然后你只需跟随当前层的所有节点（通常保持在队列中）并尝试找到它的邻居（从他们的邻居列表中），它没有层分配，你分配给他们 +1 更高层。一旦您在迷宫的边界找到您的节点（它仍然可以将 x,y 作为边界检查的属性（或属性 bool border）），您就知道它与您的图层值一样远。如果你想打印确切的方式，你只需要找到满足每一步都在 -1 层以下的条件的返回方式（通过你的邻居列表）。这将打印从头到尾的方式，但我相信在 Stack 数据结构的帮助下你会得到你的结果 :)

如何在这种迷宫中找到最短路径

How to find shortest path in this type of maze

algorithm

path

breadth-first-search

shortest-path

shortest