Dijkstra或A *上的10x10網格帶有隨機障礙物，起始點0,0,0,9,9端？

我有有Dijkstra或A *上的10x10網格帶有隨機障礙物，起始點0,0,0,9,9端？

1 0 1 1 1 1 1 1 1 1 
1 1 0 0 1 1 1 1 1 1 
1 1 1 0 1 1 1 1 1 0 
1 1 1 1 1 1 1 1 1 0 
1 0 1 1 1 0 1 0 1 1 
1 1 0 1 0 1 0 0 1 1 
1 1 0 1 1 0 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 0 1 1 1 1 
1 1 1 1 1 1 0 1 1 1

1代表開放 0代表密切

的0的可能是隨機的，並獲得用戶選擇開始點和結束點二維數組。

我明白如何通過2個嵌套for循環獲取所有開放單元格，並將它們存儲到點的Arraylist中。

現在我需要找到最短路徑，但A *或Djakstra混淆了

比方說我的出發點是0,0和我的終點是9,9，我怎麼得到最短的路徑？

我想出這個至今拿開電池：

//Check empty cells in the grid and color them in YELLOW 
for (int i = 0; i < MyMatrix.length; i++) { 
    for (int j = 0; j < MyMatrix.length; j++) { 
     if (MyMatrix[j][i]) { 
      StdDraw.setPenColor(StdDraw.YELLOW); 
      StdDraw.filledSquare(i, N - j - 1, .1); 

     } 
    } 

} 

//add all empty coordinates to array list of points 
for (int i = 0; i < MyMatrix.length; i++) { 
    for (int j = 0; j < MyMatrix.length; j++) { 
     if (MyMatrix[i][j]) { 
      coordinates.add(new Point(i, j)); 

     } 
    } 
}

但後來我如何檢查的最短路徑？

來源

2017-03-22 Mub Elme

Dijkstra算法在這裏工作。 – vish4071

[廣度優先搜索]（https://en.wikipedia.org/wiki/Breadth-first_search）適合您的情況。 – Gassa

您可以使用A *，Dijkstra或BFS查找最短路徑。這包括將矩陣轉換爲圖形，以便矩陣中的任何相鄰單元在圖形中相鄰。這並不難，但我可以理解你爲什麼會覺得有點混亂。

但是，如果您正在尋找更簡單的解決方案，我會建議Lee's algorithm。李的算法是基於BFS的，但是我覺得它比較容易理解。這很像flood fill。

該算法看起來是這樣的：

Consider matrix A of size n by m, and another matrix D of the same size. 
Pick starting point S. 
Set D[S.y][S.x] to 1. 
Add S into a queue Q. 
while Q isn't empty: 
     get point from top of the queue, call it T, pop the queue 
     for all adjacent cells P of T: 
       if cell P is visitable: 
        D[P.y][P.x]=D[T.y][T.x]+1 
        push P into queue 
The minimum distance from the starting point to any other point P will be found in D[P.y][P.x]. 
If P can't be reached, then D[p.y][p.x]=0. 
To find the actual path, you need to backtrack from the end point to the starting point, by going through the cells of D in a descending order.

來源

2017-03-22 20:35:00 k4andrei

謝謝，這真的幫助:) –

Dijkstra或A *上的10x10網格帶有隨機障礙物，起始點0,0,0,9,9端？

回答

相關問題