如何实现 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 搜索的目标应该是寻找是否有可能从 "node" 开始找到已解决的配置。

注意：HiRiQ 表示拼图板的配置（在本例中，游戏是 pegg-solitaire 拼图），方法 getAllNextStates() 生成所有不同的棋盘配置，这些配置与当前配置相差一步。

当我运行它找不到任何解决方案时，它运行没完没了。

Answer 1

我会给你一个广度优先的概念（因为我觉得你不清楚），让我们说一个简单的二叉树，这应该会让你更清楚。

说这是我们的树。

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

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

queue -> []

让我们在 queue

中引用我们的根

queue -> [1]

而 queue 不为空...

- 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

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

Answer 2

正如@DebosmitRay 指出的那样，问题可能是您没有检查节点是否已被访问过。所以您的搜索可能会陷入无限循环。

为了帮助您，这里有一个在 Java 中实现 BFS 的粗略框架。你必须自己实现 game/domain-specific 逻辑，例如棋子的配置，测试玩家是否获胜。这可以在 State 对象中实现：

interface State{
    public List<State> getNeighbors();
    public boolean isGoal();
}

BFS 搜索链接到其父状态的状态。此链接可由类似于以下内容的 Node class 处理：

class Node {

    private final State state;
    private final Node parent;

    Node(State state, Node parent){
        this.state = state;
        this.parent = parent;
    }

    public Node getParent(){return this.parent;}

    /** 
     * @return a List of neighbor Nodes that can be reached in a single move
     */
    public List<Node> getNeighbors(){
        List<Node> neighbors = new ArrayList<Node>();
        for(State state : state.getNeighbors()){
            neighbors.add(new Node(state,this));
        }
        return neighbors;
    }

    @Override
    public boolean equals(Object o){
        if(this == o) return true;
        if(!(o instanceof Node)) return false;
        Node other = (Node) o;
        return state.equals(other.state); 
    }

    @Override
    public int hashCode(){
        return state.hashCode();
    }

    @Override 
    public String toString(){
        return "Node containing: " + state.toString();
    }

}

BFS 逻辑很容易实现：

private void doBfs(State start) {

    List<Node> openList = new  ArrayList<>();
    Set<Node> closedSet = new HashSet<>();

    Node startNode = new Node(start,null);
    openList.add(startNode);

    while (!openList.isEmpty()) {

        Node current = openList.remove(0);

        //If this node has already been visited, skip it
        if(closedSet.contains(current)) continue;


        //check if the current node is a goal (solution) node
        if (current.isGoal()) {

            System.out.println("Path found !");

            //print the path by iterating over the parents
            for(Node parent = current; parent != null; parent = parent.getParent()){
                System.out.println(parent);
            }

            return;
        }

        //Add all neighbors to the openList
        openList.addAll(current.getNeighbors());

        //Add the current node to the closed set so that it is not revisted
        closedSet.add(current);
    }

    System.out.println("No solution could be found from the starting state "+ start);

}

如何实现 BFS 搜索 ~ java

How to implement a BFS search ~ java

java

breadth-first-search