Dijkstra 或 A* 在 10x10 网格上，障碍物是随机的，起点在 0,0，终点在 9,9？

Question

我有一个二维数组

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));

        }
    }
}

但是我该如何检查最短路径呢？

Answer 1

您可以使用 A*、Dijkstra 或 BFS 来寻找最短路径。这涉及将矩阵转换为图形，使得矩阵中的任何相邻单元格在图形中都是相邻的。这并不难，但我能理解为什么你会觉得它有点混乱。

但是，如果您正在寻找更简单的解决方案，我建议 Lee's algorithm. Lee's algorithm is based on BFS, but I find it somewhat simpler to understand. It's a lot like 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.

Dijkstra 或 A* 在 10x10 网格上，障碍物是随机的，起点在 0,0，终点在 9,9？

Dijkstra or A* on 10x10 Grid with obstacles which are random, starting point on 0,0 end on 9,9?

java

algorithm

a-star