用 BFS 算法解决猴子和香蕉

Question

我尝试用 java 的 BFS 算法解决猴子和香蕉问题。到目前为止，这是我的代码

public class Program {
    static final int[][] states={
            { 1, 1, 0, 0, 0, 0 }, //0  | 0 0 0 |
            { 1, 4, 3, 4, 0, 0 }, //1  | 0 1 0 |
            { 0, 3, 0, 0, 0, 0 }, //2  | 1 0 0 |
            { 0, 4, 0, 0, 3, 1 }, //3  | 0 1 1 |
            { 0, 0, 0, 3, 0, 0 }, //4  | 1 0 1 |
            { 0, 0, 0, 1, 0, 1 }, //5  | 0 0 1 |
    };
    static final String[] lblStates={
            "0 0 0",
            "0 1 0",
            "1 0 0",
            "0 1 1",
            "1 0 1",
            "0 0 1"
    };

    static class Node{
        public Node parent;
        public int node;

        Node(int node, Node parent) {
            this.node = node;
            this.parent = parent;
        }


    @Override
    public boolean equals(Object obj) {
        return this.node.equals(((Node)obj).node);
    }
    }



    static void BFS(Node start, Node goal) throws InterruptedException {
        if (start.equals(goal)){
            PrintPath(start);
            return;
        }

        Queue<Node> open = new Queue<Node>();
        open.enqueue(start);
        HashSet<Node> closed = new HashSet<Node>();

        while (!open.isEmpty()){
            Node x = open.dequeue();
            List<Node> successorsOfX = GetChildrenOf(x);
            closed.add(x);


            for (Node successor: successorsOfX) {
                if (successor.equals(goal)){
                    PrintPath(successor);
                    System.out.println();
                    return;
                }else if(!closed.contains(successor) && !open.equals(successor)){
                    open.enqueue(successor);
                }
            }
        }
    }


    static void PrintPath(Node node){
        if (node.parent != null){
            PrintPath(node.parent);
            System.out.println(lblStates[node.node]);
        }else {
            System.out.println(lblStates[node.node]);
        }
    }

    static List<Node> GetChildrenOf(Node parent){
        List<Node> result = new ArrayList<Node>();
        for (int i = 0; i <states.length ; i++) {
            int[] cost=states[parent.node];
            if (!cost.equals(0)){
                Node newNode = new Node(i, parent);
                result.add(newNode);
                System.out.print(cost[i]);
            }
        }
        System.out.println();
        return result;
    }


    public static void main(String[] args) throws InterruptedException {
        int start = 0;
        int goal = 4;

        BFS(new Node(start, null), new Node(goal, null));
    }
}

条件为(A1,A2,A3)

A1 -> 看猴子是否在箱子上
A2 -> 看看猴子是否在箱子附近
A3 -> 看箱子是不是在香蕉下面

开始条件 (0,0,0)，结束条件 (1,0,1) 最后结果它必须是猴子的路径

0 0 0
0 1 0
0 1 1
1 0 1

但是每次我运行程序都会陷入无限循环并且不打印路径。

Answer 1

我认为你的问题可能是因为你在 GetChildrenOf(...) 方法中创建新的子节点实例，你的 closedSet 从不注册为包含后继（因为如果没有定义，HashSet 使用默认的 equals() 方法，并且两个实例不相同，因为您创建了新的子节点实例。所以该方法只是继续添加继任者周而复始。

您应该尝试在节点 class 中实现 equals() 方法，看看是否可以解决问题。

祝你好运！

Answer 2

在 class Node 中，而不是 public int node;，尝试使用 public Integer node;。

或者，将 return this.node.equals(((Node)obj).node); 更改为 return this.node == ((Node)obj).node;

用 BFS 算法解决猴子和香蕉

Solving monkey and banana with BFS algorithm

java

breadth-first-search