广度优先搜索不返回最短路径
Breadth first search is not returning the shortest path
我正在尝试使用 Java 的广度优先搜索算法。考虑到 10x10 网格，我试图找到最后一个单元格 9x9（网格从 0,0 开始）。当它到达 9x9 时，它已经遍历了网格中的所有单元格。我听说 BFS 会给我最短的路径。但实际上它给了我最长的路。
- 你能告诉我这是否是预期的行为吗？
- 如果这就是 BFS 的工作方式，那么获得到 9x9 单元格的最短路线的最佳方法是什么？
请指教
Edit-- 我已经使用了这个逻辑并完成了我的游戏。如果您想参考，请检查 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]
访问单元格的模式。
通过日志回溯，从头到尾。您会看到它实际上找到了最短路径 - 沿着网格的边缘。不幸的是，在网格中，如果你不允许通过对角线（在这种情况下 BFS 超出 window 因为对角线应该有不同的权重），所有只有操作 "to the right" 和"down" 是最短的。
你可以通过简单的逻辑看出它——从 0 到 9 你必须走 9 步。你有2个坐标，你从(0, 0)到(9, 9)，1次操作只能改变一个坐标1次，所以最短路径有9+9=18步。追溯，这条路有18步。类似地 any 从头到尾只有操作 to the right 和 down 的路径将有 18 步，因此任何这样的路径都是最短的。决定路径本身的只是将相邻坐标放入队列的顺序。尝试以随机顺序进行。
编辑：下面是如何计算最短路径的数量。
我们之前注意到有 18 个操作；其中 9 个 to the right，9 个 down。这些操作的顺序无关紧要，因为最后你已经将 (9, 9) 添加到初始 (0, 0)，所以你实际上到达了最后。我们如何计算它们？让我们为每个操作分配一个标识符：a_1, a_2, ... a_18。我们现在将选择其中的 9 个操作作为 down。所以我们选择第一个点进行 down 操作，我们可以用 18 种方式进行（因为有 18 种操作可供选择），然后是第二个（17 种方式）等等，直到我们在 down 个操作中。我们本可以用 18*17*...*10 种方式做到这一点。现在我们为 right 操作选择点。我们可以（通过生物学）以 9*8*...*1 方式做到这一点。但是现在我们并没有真正区分每个 down 指令，对吗？我们可以用 9 方式选择第一个 down 操作，用 8 方式选择第二个操作，依此类推。同样，我们可以选择 right 操作。最后我们推导出有 (18*17*...*1)/((9*8*...*1)*(9*8*...*1)) = 48 620 种方法（除以对我们来说没有意义的操作区分）。这也是您可以从 18 个点中选择 9 的方法数。
如果我的解释对你来说太乱了，我建议你看看 Richard A. Brualdi 的 Introductory combinatorics。这是一本关于离散数学某些领域有趣事物的非常酷的书。非常容易阅读。
根据我对其他答案（lared 的这个）的理解，您的代码可能如下所示：
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;
private Cell previousCell;
public Cell(int x, int y, String value,boolean visitStatus) {
this.x = x;
this.y = y;
this.value = value;
this.visitStatus=visitStatus;
}
public String toString()
{
return "[" + x + "," + y + "]";
}
}
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 diagonal moves :
// int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 }, {1,1} };
for (int n = 0; n < 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>();
Cell unVisitedadjCell = start;
Cell c = null;
q.add(start);
visited.add(start);
board[start.x][start.y].visitStatus = true;
//printNode(start);
while( !q.isEmpty() )
{
c = q.peek();
unVisitedadjCell = getAdjacentUnvisitedCell(c);
if(!testDone){
testDone=true;
}
if ( unVisitedadjCell != null )
{ visited.add(unVisitedadjCell);
board[unVisitedadjCell.x][unVisitedadjCell.y].visitStatus = true;
printNode(unVisitedadjCell,c);
unVisitedadjCell.previousCell=c;
q.add(unVisitedadjCell);
}
else
{
q.remove();
}
}
System.out.println("Shortest path");
while ( ( c != null ) && ( c!=start))
{
printNode(c.previousCell,c);
c = c.previousCell;
}
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 + " previous was " + node.previousCell);
}
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);
}
}
cells[0][1].value = "B";
cells[0][2].value = "B";
cells[1][1].value = "B";
cells[1][3].value = "B";
cells[2][1].value = "B";
cells[2][2].value = "B";
cells[2][3].value = "B";
cells[2][7].value = "B";
cells[2][8].value = "B";
BFS board = new BFS();
board.setBoard(cells);
board.BFSearch(cells[0][0], cells[1][4]);
}
}
java -cp。 com.example.game.bfs.alogrithm.BFS
For Node 0,0, Just Visited : [1,0] previous was null
For Node 0,0, Just Visited : [0,1] previous was null
For Node 1,0, Just Visited : [2,0] previous was [0,0]
For Node 1,0, Just Visited : [1,1] previous was [0,0]
For Node 0,1, Just Visited : [0,2] previous was [0,0]
For Node 2,0, Just Visited : [3,0] previous was [1,0]
For Node 2,0, Just Visited : [2,1] previous was [1,0]
For Node 1,1, Just Visited : [1,2] previous was [1,0]
For Node 0,2, Just Visited : [0,3] previous was [0,1]
For Node 3,0, Just Visited : [4,0] previous was [2,0]
For Node 3,0, Just Visited : [3,1] previous was [2,0]
For Node 2,1, Just Visited : [2,2] previous was [2,0]
For Node 1,2, Just Visited : [1,3] previous was [1,1]
For Node 0,3, Just Visited : [0,4] previous was [0,2]
For Node 4,0, Just Visited : [5,0] previous was [3,0]
For Node 4,0, Just Visited : [4,1] previous was [3,0]
For Node 3,1, Just Visited : [3,2] previous was [3,0]
For Node 2,2, Just Visited : [2,3] previous was [2,1]
For Node 1,3, Just Visited : [1,4] previous was [1,2]
For Node 0,4, Just Visited : [0,5] previous was [0,3]
For Node 5,0, Just Visited : [6,0] previous was [4,0]
For Node 5,0, Just Visited : [5,1] previous was [4,0]
For Node 4,1, Just Visited : [4,2] previous was [4,0]
For Node 3,2, Just Visited : [3,3] previous was [3,1]
For Node 2,3, Just Visited : [2,4] previous was [2,2]
For Node 1,4, Just Visited : [1,5] previous was [1,3]
For Node 0,5, Just Visited : [0,6] previous was [0,4]
For Node 6,0, Just Visited : [7,0] previous was [5,0]
For Node 6,0, Just Visited : [6,1] previous was [5,0]
For Node 5,1, Just Visited : [5,2] previous was [5,0]
For Node 4,2, Just Visited : [4,3] previous was [4,1]
For Node 3,3, Just Visited : [3,4] previous was [3,2]
For Node 2,4, Just Visited : [2,5] previous was [2,3]
For Node 1,5, Just Visited : [1,6] previous was [1,4]
For Node 0,6, Just Visited : [0,7] previous was [0,5]
For Node 7,0, Just Visited : [8,0] previous was [6,0]
For Node 7,0, Just Visited : [7,1] previous was [6,0]
For Node 6,1, Just Visited : [6,2] previous was [6,0]
For Node 5,2, Just Visited : [5,3] previous was [5,1]
For Node 4,3, Just Visited : [4,4] previous was [4,2]
For Node 3,4, Just Visited : [3,5] previous was [3,3]
For Node 2,5, Just Visited : [2,6] previous was [2,4]
For Node 1,6, Just Visited : [1,7] previous was [1,5]
For Node 0,7, Just Visited : [0,8] previous was [0,6]
For Node 8,0, Just Visited : [9,0] previous was [7,0]
For Node 8,0, Just Visited : [8,1] previous was [7,0]
For Node 7,1, Just Visited : [7,2] previous was [7,0]
For Node 6,2, Just Visited : [6,3] previous was [6,1]
For Node 5,3, Just Visited : [5,4] previous was [5,2]
For Node 4,4, Just Visited : [4,5] previous was [4,3]
For Node 3,5, Just Visited : [3,6] previous was [3,4]
For Node 2,6, Just Visited : [2,7] previous was [2,5]
For Node 1,7, Just Visited : [1,8] previous was [1,6]
For Node 0,8, Just Visited : [0,9] previous was [0,7]
For Node 9,0, Just Visited : [9,1] previous was [8,0]
For Node 8,1, Just Visited : [8,2] previous was [8,0]
For Node 7,2, Just Visited : [7,3] previous was [7,1]
For Node 6,3, Just Visited : [6,4] previous was [6,2]
For Node 5,4, Just Visited : [5,5] previous was [5,3]
For Node 4,5, Just Visited : [4,6] previous was [4,4]
For Node 3,6, Just Visited : [3,7] previous was [3,5]
For Node 2,7, Just Visited : [2,8] previous was [2,6]
For Node 1,8, Just Visited : [1,9] previous was [1,7]
For Node 9,1, Just Visited : [9,2] previous was [9,0]
For Node 8,2, Just Visited : [8,3] previous was [8,1]
For Node 7,3, Just Visited : [7,4] previous was [7,2]
For Node 6,4, Just Visited : [6,5] previous was [6,3]
For Node 5,5, Just Visited : [5,6] previous was [5,4]
For Node 4,6, Just Visited : [4,7] previous was [4,5]
For Node 3,7, Just Visited : [3,8] previous was [3,6]
For Node 2,8, Just Visited : [2,9] previous was [2,7]
For Node 9,2, Just Visited : [9,3] previous was [9,1]
For Node 8,3, Just Visited : [8,4] previous was [8,2]
For Node 7,4, Just Visited : [7,5] previous was [7,3]
For Node 6,5, Just Visited : [6,6] previous was [6,4]
For Node 5,6, Just Visited : [5,7] previous was [5,5]
For Node 4,7, Just Visited : [4,8] previous was [4,6]
For Node 3,8, Just Visited : [3,9] previous was [3,7]
For Node 9,3, Just Visited : [9,4] previous was [9,2]
For Node 8,4, Just Visited : [8,5] previous was [8,3]
For Node 7,5, Just Visited : [7,6] previous was [7,4]
For Node 6,6, Just Visited : [6,7] previous was [6,5]
For Node 5,7, Just Visited : [5,8] previous was [5,6]
For Node 4,8, Just Visited : [4,9] previous was [4,7]
For Node 9,4, Just Visited : [9,5] previous was [9,3]
For Node 8,5, Just Visited : [8,6] previous was [8,4]
For Node 7,6, Just Visited : [7,7] previous was [7,5]
For Node 6,7, Just Visited : [6,8] previous was [6,6]
For Node 5,8, Just Visited : [5,9] previous was [5,7]
For Node 9,5, Just Visited : [9,6] previous was [9,4]
For Node 8,6, Just Visited : [8,7] previous was [8,5]
For Node 7,7, Just Visited : [7,8] previous was [7,6]
For Node 6,8, Just Visited : [6,9] previous was [6,7]
For Node 9,6, Just Visited : [9,7] previous was [9,5]
For Node 8,7, Just Visited : [8,8] previous was [8,6]
For Node 7,8, Just Visited : [7,9] previous was [7,7]
For Node 9,7, Just Visited : [9,8] previous was [9,6]
For Node 8,8, Just Visited : [8,9] previous was [8,7]
For Node 9,8, Just Visited : [9,9] previous was [9,7]
Shortest path
For Node 9,9, Just Visited : [9,8] previous was [9,8]
For Node 9,8, Just Visited : [9,7] previous was [9,7]
For Node 9,7, Just Visited : [9,6] previous was [9,6]
For Node 9,6, Just Visited : [9,5] previous was [9,5]
For Node 9,5, Just Visited : [9,4] previous was [9,4]
For Node 9,4, Just Visited : [9,3] previous was [9,3]
For Node 9,3, Just Visited : [9,2] previous was [9,2]
For Node 9,2, Just Visited : [9,1] previous was [9,1]
For Node 9,1, Just Visited : [9,0] previous was [9,0]
For Node 9,0, Just Visited : [8,0] previous was [8,0]
For Node 8,0, Just Visited : [7,0] previous was [7,0]
For Node 7,0, Just Visited : [6,0] previous was [6,0]
For Node 6,0, Just Visited : [5,0] previous was [5,0]
For Node 5,0, Just Visited : [4,0] previous was [4,0]
For Node 4,0, Just Visited : [3,0] previous was [3,0]
For Node 3,0, Just Visited : [2,0] previous was [2,0]
For Node 2,0, Just Visited : [1,0] previous was [1,0]
For Node 1,0, Just Visited : [0,0] previous was [0,0]
然后尝试使用带对角线的注释代码...
我正在尝试使用 Java 的广度优先搜索算法。考虑到 10x10 网格，我试图找到最后一个单元格 9x9（网格从 0,0 开始）。当它到达 9x9 时，它已经遍历了网格中的所有单元格。我听说 BFS 会给我最短的路径。但实际上它给了我最长的路。
- 你能告诉我这是否是预期的行为吗？
- 如果这就是 BFS 的工作方式，那么获得到 9x9 单元格的最短路线的最佳方法是什么？
请指教
Edit-- 我已经使用了这个逻辑并完成了我的游戏。如果您想参考，请检查 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]
访问单元格的模式。
通过日志回溯，从头到尾。您会看到它实际上找到了最短路径 - 沿着网格的边缘。不幸的是，在网格中，如果你不允许通过对角线（在这种情况下 BFS 超出 window 因为对角线应该有不同的权重），所有只有操作 "to the right" 和"down" 是最短的。
你可以通过简单的逻辑看出它——从 0 到 9 你必须走 9 步。你有2个坐标，你从(0, 0)到(9, 9)，1次操作只能改变一个坐标1次，所以最短路径有9+9=18步。追溯，这条路有18步。类似地 any 从头到尾只有操作 to the right 和 down 的路径将有 18 步，因此任何这样的路径都是最短的。决定路径本身的只是将相邻坐标放入队列的顺序。尝试以随机顺序进行。
编辑：下面是如何计算最短路径的数量。
我们之前注意到有 18 个操作；其中 9 个 to the right，9 个 down。这些操作的顺序无关紧要，因为最后你已经将 (9, 9) 添加到初始 (0, 0)，所以你实际上到达了最后。我们如何计算它们？让我们为每个操作分配一个标识符：a_1, a_2, ... a_18。我们现在将选择其中的 9 个操作作为 down。所以我们选择第一个点进行 down 操作，我们可以用 18 种方式进行（因为有 18 种操作可供选择），然后是第二个（17 种方式）等等，直到我们在 down 个操作中。我们本可以用 18*17*...*10 种方式做到这一点。现在我们为 right 操作选择点。我们可以（通过生物学）以 9*8*...*1 方式做到这一点。但是现在我们并没有真正区分每个 down 指令，对吗？我们可以用 9 方式选择第一个 down 操作，用 8 方式选择第二个操作，依此类推。同样，我们可以选择 right 操作。最后我们推导出有 (18*17*...*1)/((9*8*...*1)*(9*8*...*1)) = 48 620 种方法（除以对我们来说没有意义的操作区分）。这也是您可以从 18 个点中选择 9 的方法数。
如果我的解释对你来说太乱了，我建议你看看 Richard A. Brualdi 的 Introductory combinatorics。这是一本关于离散数学某些领域有趣事物的非常酷的书。非常容易阅读。
根据我对其他答案（lared 的这个）的理解，您的代码可能如下所示：
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;
private Cell previousCell;
public Cell(int x, int y, String value,boolean visitStatus) {
this.x = x;
this.y = y;
this.value = value;
this.visitStatus=visitStatus;
}
public String toString()
{
return "[" + x + "," + y + "]";
}
}
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 diagonal moves :
// int moves[][] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 }, {1,1} };
for (int n = 0; n < 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>();
Cell unVisitedadjCell = start;
Cell c = null;
q.add(start);
visited.add(start);
board[start.x][start.y].visitStatus = true;
//printNode(start);
while( !q.isEmpty() )
{
c = q.peek();
unVisitedadjCell = getAdjacentUnvisitedCell(c);
if(!testDone){
testDone=true;
}
if ( unVisitedadjCell != null )
{ visited.add(unVisitedadjCell);
board[unVisitedadjCell.x][unVisitedadjCell.y].visitStatus = true;
printNode(unVisitedadjCell,c);
unVisitedadjCell.previousCell=c;
q.add(unVisitedadjCell);
}
else
{
q.remove();
}
}
System.out.println("Shortest path");
while ( ( c != null ) && ( c!=start))
{
printNode(c.previousCell,c);
c = c.previousCell;
}
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 + " previous was " + node.previousCell);
}
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);
}
}
cells[0][1].value = "B";
cells[0][2].value = "B";
cells[1][1].value = "B";
cells[1][3].value = "B";
cells[2][1].value = "B";
cells[2][2].value = "B";
cells[2][3].value = "B";
cells[2][7].value = "B";
cells[2][8].value = "B";
BFS board = new BFS();
board.setBoard(cells);
board.BFSearch(cells[0][0], cells[1][4]);
}
}
java -cp。 com.example.game.bfs.alogrithm.BFS
For Node 0,0, Just Visited : [1,0] previous was null
For Node 0,0, Just Visited : [0,1] previous was null
For Node 1,0, Just Visited : [2,0] previous was [0,0]
For Node 1,0, Just Visited : [1,1] previous was [0,0]
For Node 0,1, Just Visited : [0,2] previous was [0,0]
For Node 2,0, Just Visited : [3,0] previous was [1,0]
For Node 2,0, Just Visited : [2,1] previous was [1,0]
For Node 1,1, Just Visited : [1,2] previous was [1,0]
For Node 0,2, Just Visited : [0,3] previous was [0,1]
For Node 3,0, Just Visited : [4,0] previous was [2,0]
For Node 3,0, Just Visited : [3,1] previous was [2,0]
For Node 2,1, Just Visited : [2,2] previous was [2,0]
For Node 1,2, Just Visited : [1,3] previous was [1,1]
For Node 0,3, Just Visited : [0,4] previous was [0,2]
For Node 4,0, Just Visited : [5,0] previous was [3,0]
For Node 4,0, Just Visited : [4,1] previous was [3,0]
For Node 3,1, Just Visited : [3,2] previous was [3,0]
For Node 2,2, Just Visited : [2,3] previous was [2,1]
For Node 1,3, Just Visited : [1,4] previous was [1,2]
For Node 0,4, Just Visited : [0,5] previous was [0,3]
For Node 5,0, Just Visited : [6,0] previous was [4,0]
For Node 5,0, Just Visited : [5,1] previous was [4,0]
For Node 4,1, Just Visited : [4,2] previous was [4,0]
For Node 3,2, Just Visited : [3,3] previous was [3,1]
For Node 2,3, Just Visited : [2,4] previous was [2,2]
For Node 1,4, Just Visited : [1,5] previous was [1,3]
For Node 0,5, Just Visited : [0,6] previous was [0,4]
For Node 6,0, Just Visited : [7,0] previous was [5,0]
For Node 6,0, Just Visited : [6,1] previous was [5,0]
For Node 5,1, Just Visited : [5,2] previous was [5,0]
For Node 4,2, Just Visited : [4,3] previous was [4,1]
For Node 3,3, Just Visited : [3,4] previous was [3,2]
For Node 2,4, Just Visited : [2,5] previous was [2,3]
For Node 1,5, Just Visited : [1,6] previous was [1,4]
For Node 0,6, Just Visited : [0,7] previous was [0,5]
For Node 7,0, Just Visited : [8,0] previous was [6,0]
For Node 7,0, Just Visited : [7,1] previous was [6,0]
For Node 6,1, Just Visited : [6,2] previous was [6,0]
For Node 5,2, Just Visited : [5,3] previous was [5,1]
For Node 4,3, Just Visited : [4,4] previous was [4,2]
For Node 3,4, Just Visited : [3,5] previous was [3,3]
For Node 2,5, Just Visited : [2,6] previous was [2,4]
For Node 1,6, Just Visited : [1,7] previous was [1,5]
For Node 0,7, Just Visited : [0,8] previous was [0,6]
For Node 8,0, Just Visited : [9,0] previous was [7,0]
For Node 8,0, Just Visited : [8,1] previous was [7,0]
For Node 7,1, Just Visited : [7,2] previous was [7,0]
For Node 6,2, Just Visited : [6,3] previous was [6,1]
For Node 5,3, Just Visited : [5,4] previous was [5,2]
For Node 4,4, Just Visited : [4,5] previous was [4,3]
For Node 3,5, Just Visited : [3,6] previous was [3,4]
For Node 2,6, Just Visited : [2,7] previous was [2,5]
For Node 1,7, Just Visited : [1,8] previous was [1,6]
For Node 0,8, Just Visited : [0,9] previous was [0,7]
For Node 9,0, Just Visited : [9,1] previous was [8,0]
For Node 8,1, Just Visited : [8,2] previous was [8,0]
For Node 7,2, Just Visited : [7,3] previous was [7,1]
For Node 6,3, Just Visited : [6,4] previous was [6,2]
For Node 5,4, Just Visited : [5,5] previous was [5,3]
For Node 4,5, Just Visited : [4,6] previous was [4,4]
For Node 3,6, Just Visited : [3,7] previous was [3,5]
For Node 2,7, Just Visited : [2,8] previous was [2,6]
For Node 1,8, Just Visited : [1,9] previous was [1,7]
For Node 9,1, Just Visited : [9,2] previous was [9,0]
For Node 8,2, Just Visited : [8,3] previous was [8,1]
For Node 7,3, Just Visited : [7,4] previous was [7,2]
For Node 6,4, Just Visited : [6,5] previous was [6,3]
For Node 5,5, Just Visited : [5,6] previous was [5,4]
For Node 4,6, Just Visited : [4,7] previous was [4,5]
For Node 3,7, Just Visited : [3,8] previous was [3,6]
For Node 2,8, Just Visited : [2,9] previous was [2,7]
For Node 9,2, Just Visited : [9,3] previous was [9,1]
For Node 8,3, Just Visited : [8,4] previous was [8,2]
For Node 7,4, Just Visited : [7,5] previous was [7,3]
For Node 6,5, Just Visited : [6,6] previous was [6,4]
For Node 5,6, Just Visited : [5,7] previous was [5,5]
For Node 4,7, Just Visited : [4,8] previous was [4,6]
For Node 3,8, Just Visited : [3,9] previous was [3,7]
For Node 9,3, Just Visited : [9,4] previous was [9,2]
For Node 8,4, Just Visited : [8,5] previous was [8,3]
For Node 7,5, Just Visited : [7,6] previous was [7,4]
For Node 6,6, Just Visited : [6,7] previous was [6,5]
For Node 5,7, Just Visited : [5,8] previous was [5,6]
For Node 4,8, Just Visited : [4,9] previous was [4,7]
For Node 9,4, Just Visited : [9,5] previous was [9,3]
For Node 8,5, Just Visited : [8,6] previous was [8,4]
For Node 7,6, Just Visited : [7,7] previous was [7,5]
For Node 6,7, Just Visited : [6,8] previous was [6,6]
For Node 5,8, Just Visited : [5,9] previous was [5,7]
For Node 9,5, Just Visited : [9,6] previous was [9,4]
For Node 8,6, Just Visited : [8,7] previous was [8,5]
For Node 7,7, Just Visited : [7,8] previous was [7,6]
For Node 6,8, Just Visited : [6,9] previous was [6,7]
For Node 9,6, Just Visited : [9,7] previous was [9,5]
For Node 8,7, Just Visited : [8,8] previous was [8,6]
For Node 7,8, Just Visited : [7,9] previous was [7,7]
For Node 9,7, Just Visited : [9,8] previous was [9,6]
For Node 8,8, Just Visited : [8,9] previous was [8,7]
For Node 9,8, Just Visited : [9,9] previous was [9,7]
Shortest path
For Node 9,9, Just Visited : [9,8] previous was [9,8]
For Node 9,8, Just Visited : [9,7] previous was [9,7]
For Node 9,7, Just Visited : [9,6] previous was [9,6]
For Node 9,6, Just Visited : [9,5] previous was [9,5]
For Node 9,5, Just Visited : [9,4] previous was [9,4]
For Node 9,4, Just Visited : [9,3] previous was [9,3]
For Node 9,3, Just Visited : [9,2] previous was [9,2]
For Node 9,2, Just Visited : [9,1] previous was [9,1]
For Node 9,1, Just Visited : [9,0] previous was [9,0]
For Node 9,0, Just Visited : [8,0] previous was [8,0]
For Node 8,0, Just Visited : [7,0] previous was [7,0]
For Node 7,0, Just Visited : [6,0] previous was [6,0]
For Node 6,0, Just Visited : [5,0] previous was [5,0]
For Node 5,0, Just Visited : [4,0] previous was [4,0]
For Node 4,0, Just Visited : [3,0] previous was [3,0]
For Node 3,0, Just Visited : [2,0] previous was [2,0]
For Node 2,0, Just Visited : [1,0] previous was [1,0]
For Node 1,0, Just Visited : [0,0] previous was [0,0]
然后尝试使用带对角线的注释代码...