java - 广度优先搜索不返回最短路径

Question

我正在尝试通过 Java 使用广度优先搜索算法。考虑到 10x10 网格，我试图找到最后一个单元格 9x9(网格从 0,0 开始)。当它到达 9x9 时，它已经遍历了网格中的所有单元格。我听说 BFS 会给我最短的路径。但实际上它给了我最长的路。

1. 你能告诉我这是否是预期的行为吗？
2. 如果这就是 BFS 的工作方式，那么获得到 9x9 单元格的最短路线的最佳方法是什么？

请指教。

编辑——我已经使用了这个逻辑并完成了我的游戏。如果您想引用，请查看https://play.google.com/store/apps/details?id=com.game.puzzle.game.ballmania.android

代码

package com.example.game.bfs.alogrithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BFS {

static class Cell {
    private int x;
    private int y;
    private String value;
    private boolean visitStatus;

    public Cell(int x, int y, String value,boolean visitStatus) {
        this.x = x;
        this.y = y;
        this.value = value; 
        this.visitStatus=visitStatus;
    }
}

private Cell[][] board;

private List<Cell> visited = new ArrayList<Cell>();

private boolean testDone;

public void setBoard(Cell[][] board) {
    this.board = board;
} 

public Cell getAdjacentUnvisitedCell(Cell cell)
{  
   int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };
   for (int n = 0; n < 4 /* moves.length */; ++n) {
       int ti = cell.x + moves[n][0];
       int tj = cell.y + moves[n][1];
      // System.out.println("ti,tj" + ti +"," + tj );  

       if (ti >= 0 && ti < board.length && tj >= 0 && tj < board[0].length) { 

          // System.out.println("getAdjacentUnvisitedCell : " + "[" + board[ti][tj].x + "," + board[ti][tj].y + "]" ); 
          // System.out.println("getAdjacentUnvisitedCell : board[ti][tj].visitStatus " + board[ti][tj].visitStatus ); 

           if(!board[ti][tj].visitStatus) {  
              return board[ti][tj];
           }
       }
   }  
   return null;  
} 

public void BFSearch(Cell start, Cell end) {  
   // BFS uses Queue data structure 
   Queue<Cell> q = new LinkedList<Cell>(); 
   q.add(start);
   visited.add(start);
   board[start.x][start.y].visitStatus = true;

   //printNode(start);

   while( !q.isEmpty() )
   { 
      Cell c; 
      c = q.peek(); 
      Cell unVisitedadjCell = getAdjacentUnvisitedCell(c); 

      if(!testDone){
          testDone=true;  
      } 

      if ( unVisitedadjCell != null )
      {  visited.add(unVisitedadjCell); 
         board[unVisitedadjCell.x][unVisitedadjCell.y].visitStatus = true;

         printNode(unVisitedadjCell,c); 
         q.add(unVisitedadjCell);
      }
      else
      {
         q.remove();
      }
   }

   visited.clear();     //Clear visited property of nodes
}


private void printNode(Cell c,Cell node) {
    System.out.println("For Node " + node.x +"," + node.y + ",   " + "Just Visited : " + "[" + c.x + "," + c.y + "]" );  
} 

public static void main(String[] args) {
    Cell[][] cells = new Cell[10][10];
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cells[i][j] = new Cell(i, j, "defaultvalue",false);
        }
    } 

    BFS board = new BFS();
    board.setBoard(cells);

    board.BFSearch(cells[0][0], cells[1][4]);
}


}

}

日志:

For Node 0,0,   Just Visited : [1,0]
For Node 0,0,   Just Visited : [0,1]
For Node 1,0,   Just Visited : [2,0]
For Node 1,0,   Just Visited : [1,1]
For Node 0,1,   Just Visited : [0,2]
For Node 2,0,   Just Visited : [3,0]
For Node 2,0,   Just Visited : [2,1]
For Node 1,1,   Just Visited : [1,2]
For Node 0,2,   Just Visited : [0,3]
For Node 3,0,   Just Visited : [4,0]
For Node 3,0,   Just Visited : [3,1]
For Node 2,1,   Just Visited : [2,2]
For Node 1,2,   Just Visited : [1,3]
For Node 0,3,   Just Visited : [0,4]
For Node 4,0,   Just Visited : [5,0]
For Node 4,0,   Just Visited : [4,1]
For Node 3,1,   Just Visited : [3,2]
For Node 2,2,   Just Visited : [2,3]
For Node 1,3,   Just Visited : [1,4]
For Node 0,4,   Just Visited : [0,5]
For Node 5,0,   Just Visited : [6,0]
For Node 5,0,   Just Visited : [5,1]
For Node 4,1,   Just Visited : [4,2]
For Node 3,2,   Just Visited : [3,3]
For Node 2,3,   Just Visited : [2,4]
For Node 1,4,   Just Visited : [1,5]
For Node 0,5,   Just Visited : [0,6]
For Node 6,0,   Just Visited : [7,0]
For Node 6,0,   Just Visited : [6,1]
For Node 5,1,   Just Visited : [5,2]
For Node 4,2,   Just Visited : [4,3]
For Node 3,3,   Just Visited : [3,4]
For Node 2,4,   Just Visited : [2,5]
For Node 1,5,   Just Visited : [1,6]
For Node 0,6,   Just Visited : [0,7]
For Node 7,0,   Just Visited : [8,0]
For Node 7,0,   Just Visited : [7,1]
For Node 6,1,   Just Visited : [6,2]
For Node 5,2,   Just Visited : [5,3]
For Node 4,3,   Just Visited : [4,4]
For Node 3,4,   Just Visited : [3,5]
For Node 2,5,   Just Visited : [2,6]
For Node 1,6,   Just Visited : [1,7]
For Node 0,7,   Just Visited : [0,8]
For Node 8,0,   Just Visited : [9,0]
For Node 8,0,   Just Visited : [8,1]
For Node 7,1,   Just Visited : [7,2]
For Node 6,2,   Just Visited : [6,3]
For Node 5,3,   Just Visited : [5,4]
For Node 4,4,   Just Visited : [4,5]
For Node 3,5,   Just Visited : [3,6]
For Node 2,6,   Just Visited : [2,7]
For Node 1,7,   Just Visited : [1,8]
For Node 0,8,   Just Visited : [0,9]
For Node 9,0,   Just Visited : [9,1]
For Node 8,1,   Just Visited : [8,2]
For Node 7,2,   Just Visited : [7,3]
For Node 6,3,   Just Visited : [6,4]
For Node 5,4,   Just Visited : [5,5]
For Node 4,5,   Just Visited : [4,6]
For Node 3,6,   Just Visited : [3,7]
For Node 2,7,   Just Visited : [2,8]
For Node 1,8,   Just Visited : [1,9]
For Node 9,1,   Just Visited : [9,2]
For Node 8,2,   Just Visited : [8,3]
For Node 7,3,   Just Visited : [7,4]
For Node 6,4,   Just Visited : [6,5]
For Node 5,5,   Just Visited : [5,6]
For Node 4,6,   Just Visited : [4,7]
For Node 3,7,   Just Visited : [3,8]
For Node 2,8,   Just Visited : [2,9]
For Node 9,2,   Just Visited : [9,3]
For Node 8,3,   Just Visited : [8,4]
For Node 7,4,   Just Visited : [7,5]
For Node 6,5,   Just Visited : [6,6]
For Node 5,6,   Just Visited : [5,7]
For Node 4,7,   Just Visited : [4,8]
For Node 3,8,   Just Visited : [3,9]
For Node 9,3,   Just Visited : [9,4]
For Node 8,4,   Just Visited : [8,5]
For Node 7,5,   Just Visited : [7,6]
For Node 6,6,   Just Visited : [6,7]
For Node 5,7,   Just Visited : [5,8]
For Node 4,8,   Just Visited : [4,9]
For Node 9,4,   Just Visited : [9,5]
For Node 8,5,   Just Visited : [8,6]
For Node 7,6,   Just Visited : [7,7]
For Node 6,7,   Just Visited : [6,8]
For Node 5,8,   Just Visited : [5,9]
For Node 9,5,   Just Visited : [9,6]
For Node 8,6,   Just Visited : [8,7]
For Node 7,7,   Just Visited : [7,8]
For Node 6,8,   Just Visited : [6,9]
For Node 9,6,   Just Visited : [9,7]
For Node 8,7,   Just Visited : [8,8]
For Node 7,8,   Just Visited : [7,9]
For Node 9,7,   Just Visited : [9,8]
For Node 8,8,   Just Visited : [8,9]
For Node 9,8,   Just Visited : [9,9]

访问单元格的模式。

Answer 1

通过日志回溯，从头到尾。您会看到它实际上找到了最短路径 - 沿着网格的边缘。不幸的是，在网格中，如果您不允许通过对角线(在这种情况下 BFS 超出窗口，因为对角线应该具有不同的权重)，所有仅具有“向右”和“向下”操作的路径是最短的。

您可以通过简单的逻辑看到它 - 从 0 到 9 必须走 9 步。你有 2 个坐标，你从 (0, 0) 到 (9, 9)，你只能通过 1 in 1 操作更改一个坐标，所以最短路径有 9+9=18 个步骤。追溯，这条路有18步。类似地，任何从头到尾只有向右和向下操作的路径将有18步，所以任何这样的路径都是最短的。决定路径本身的只是将相邻坐标放入队列的顺序。尝试以随机顺序进行。

编辑:下面是如何计算最短路径的数量。我们之前注意到有 18 个操作；其中 9 个在右侧，9 个在下方。这些操作的顺序无关紧要，因为最后您已将 (9, 9) 添加到初始 (0, 0)，因此您实际上到达了结尾。我们如何计算它们？让我们为每个操作分配一个标识符，如下所示:a_1, a_2, ... a_18。我们现在要选择其中的 9 个操作down。所以我们选择第一个位置进行 down 操作，我们可以用 18 种方式进行(因为有 18 种操作可供选择)，然后是第二个(17 方式)和依此类推，直到我们完成 down 操作。我们本可以用 18*17*...*10 的方式做到这一点。现在我们为正确的操作选择点。我们可以(通过逻辑)以 9*8*...*1 方式做到这一点。但是现在我们并没有真正区分每个 down 指令，对吗？我们可以在 9 方式中选择第一个 down 操作，在 8 方式中选择第二个操作，依此类推。同样，我们可以选择正确的 操作。最后我们推导出有 (18*17*...*1)/((9*8*...*1)*(9*8*...*1)) = 48 620 这样做的方式(我们通过对我们无意义的操作区分来划分)。这也是您可以从 18 点中选择 9 的方法数。

如果我的解释对您来说太乱，我可以推荐您看一下Richard A. Brualdi 的Introductory combinatorics。这是一本关于离散数学某些领域有趣事物的非常酷的书。非常容易阅读。