如何找到最短路径在这种类型的迷宫

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可以将自身在同一时间只有一招，可以在绿色六分之一的移动连接到它的圈子。什么是最快的方法来计算这种类型的迷宫中的最短路径。

来源

2015-11-04 jpm

什么构成“路径？”你能举一些例子吗？ Upvote包括一个漂亮的图片的问题。 –

这是什么意思？目的地 - 矩阵的边界[意思是x = 0或y = 0或x = 9或y = 9] 9次成功移动？ –

请参阅编辑中的示例。红点必须达到迷宫的边界。 – jpm

首先，你不需要Dijkstra算法，因为边缘的所有值都相同。您可以使用简单的BFS或DFS算法。最坏情况的复杂性是相同的，但我会使用BFS，因为它具有更好的平均情况复杂性。但是，O（| V | + | E |）是您可以在此获得的最快速度，并且已被证明。

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

BFS算法具有其分配的每个节点的层，这意味着它是多远从起始节点的属性。你从你的起点开始，你的当前层将是0.然后，你只需要关注当前层的所有节点（通常保持在队列中），并尝试找到它的邻居（来自它们的邻居列表），它没有层分配给你并为其分配+1更高层。一旦你找到你的Node，（它仍然可以有x，y作为边界检查属性（或属性布尔边框）），在迷宫边界，你知道它和你的图层值一样。如果你想打印确切的方式，你只需要找回方式（通过你的邻居列表），它符合条件，每一步都在-1层以下。这将打印从头到尾的方式，但我相信你会从Stack数据结构得到你的结果:)

来源

2015-11-13 13:52:37

你有什么是一个“简单”的图形问题。图连通性是您拥有的合法举动。起始节点是你的红点。为了获得单个终端节点，在给定的迷宫之外再创造一个圆圈;以零成本的方式将所有的实际出口节点连接到新的圆。

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

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

做那些让你未卡住？

来源

2015-11-04 21:56:46 Prune

-1

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次函数调用，并取最小值）

至于节点的启发式值 - 只需设置黑色阻塞节点非常高的启发式值，这将使它们无法访问，所以算法会绕过它们。

来源

2015-11-07 13:16:54

这将是很好的给一个想法什么算法。 SO帮助中心说：为什么以及如何删除一些答案？不能从根本上回答问题的答案可能会被删除。这包括以下答案： ... \t•\t仅仅比链接到外部网站 –

如何找到最短路径在这种类型的迷宫

回答

相关问题