java - 如何实现BFS搜索~java

Question

这是我的代码:

private void doBfs(HiRiQ node, ArrayList<HiRiQ> queue, ArrayList<HiRiQ> path, ArrayList<HiRiQ> visited) {
    while(!queue.isEmpty()){
        HiRiQ current = queue.remove(0);
        if(current.IsSolved()){
            current.print();
            System.out.println("Path found !");
            return;
        } else {    
            if(current.getAllNextStates().isEmpty()){
                return; 
            } else {
                queue.addAll(current.getAllNextStates());
            }
        }
        visited.add(current); 
    }
}

我很难弄清楚如何继续使用此方法。我知道如果无法访问其他方法，它应该会很复杂，但我只想知道这个 bfs-search 算法缺少什么。

此 bfs 搜索的目标应该是查找是否可以找到从“节点”开始的已解决配置。

注意:HiRiQ 表示拼图板的一种配置(在本例中，游戏是钉子接龙拼图)，并且方法 getAllNextStates() 生成距离当前棋盘一步之遥的所有不同棋盘配置。

当我运行它时，它只是找不到任何解决方案，它无休止地运行。

Answer 1

我会给你一个广度优先的概念(因为我觉得你对此不清楚)，比如说一个简单的二叉树，这应该会让你更清楚。

说这是我们的树。

           1
     /           \
    2             3
  /   \         /   \
4      5       6     7

现在，由于我们需要进行广度优先搜索，所以让我们看一下队列数据结构。

queue -> []

让我们将根引用放入队列

queue -> [1]

当队列不为空时...

- pop the first element, i.e. 1
- if it has a left child, add it to the queue [2]
- if it has a right child, add it to the queue [2,3]
- repeat

这将如何运作？

pop first element, i.e. 1; queue -> []
- if it has a left child, add it to the queue [2]
- if it has a right child, add it to the queue [2,3]

pop first element, i.e. 2; queue -> [3]
- if it has a left child, add it to the queue [3,4]
- if it has a right child, add it to the queue [3,4,5]

pop first element, i.e. 3; queue -> [4,5]
- if it has a left child, add it to the queue [4,5,6]
- if it has a right child, add it to the queue [4,5,6,7]

pop first element, i.e. 4; queue -> [5,6,7]
- if it has a left child, add it to the queue [5,6,7]
- if it has a right child, add it to the queue [5,6,7]

pop first element, i.e. 5; queue -> [6,7]
- if it has a left child, add it to the queue [6,7]
- if it has a right child, add it to the queue [6,7]

pop first element, i.e. 6; queue -> [7]
- if it has a left child, add it to the queue [7]
- if it has a right child, add it to the queue [7]

pop first element, i.e. 7; queue -> []
- if it has a left child, add it to the queue []
- if it has a right child, add it to the queue []

queue is empty

我希望这能澄清您的理解并帮助您解决问题。