如何找到最短路徑在這種類型的迷宮

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

首先，你不需要Dijkstra算法，因爲邊緣的所有值都相同。您可以使用簡單的BFS或DFS算法。最壞情況的複雜性是相同的，但我會使用BFS，因爲它具有更好的平均情況複雜性。但是，O（| V | + | E |）是您可以在此獲得的最快速度，並且已被證明。

如何讓你的圖表代表？最好的方法是保留每個Node的鄰居列表。您示例中的黑點不被視爲鄰居。因此，在你的例子中，每個節點將有0個（完全由黑點覆蓋）到6個鄰居。然後，通過這些列表，您可以從任何節點獲取任何地方。

BFS算法具有其分配的每個節點的層，這意味着它是多遠從起始節點的屬性。你從你的起點開始，你的當前層將是0.然後，你只需要關注當前層的所有節點（通常保持在隊列中），並嘗試找到它的鄰居（來自它們的鄰居列表），它沒有層分配給你併爲其分配+1更高層。一旦你找到你的Node，（它仍然可以有x，y作爲邊界檢查屬性（或屬性布爾邊框）），在迷宮邊界，你知道它和你的圖層值一樣。如果你想打印確切的方式，你只需要找回方式（通過你的鄰居列表），它符合條件，每一步都在-1層以下。這將打印從頭到尾的方式，但我相信你會從Stack數據結構得到你的結果:)

Answer 2

你有什麼是一個「簡單」的圖形問題。圖連通性是您擁有的合法舉動。起始節點是你的紅點。爲了獲得單個終端節點，在給定的迷宮之外再創造一個圓圈;以零成本的方式將所有的實際出口節點連接到新的圓。

現在，應用Dijkstra算法。完成。

---

查看問題的另一種方法是使用遞歸。移動紅點，將舊位置標記爲黑色。重新從新的位置。退出時返回（返回路徑長度1）或沒有合法移動（返回路徑長度無限）。保持最短的已知路徑。

做那些讓你未卡住？

Answer 3

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次函數調用，並取最小值）

至於節點的啓發式值 - 只需設置黑色阻塞節點非常高的啓發式值，這將使它們無法訪問，所以算法會繞過它們。