用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(

1. A1 -> 看看猴子是否在盒子上
2. A2 -> 看看猴子是否在盒子附近
3. A3 -> 查看盒子是否在香蕉下方

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

0 0
• 0
  0 1 0
  0 1 1
  1 0 1

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

Answer 1

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

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

Answer 2

我认为您的问题可能是，由于您在 GetChildrenOf(...( 方法中创建新的子节点实例，因此您的 closedSet 永远不会注册为包含后续节点(因为 HashSet 使用默认的 equals(( 方法，如果没有定义一个，并且两个实例不同，因为您创建新的子节点实例。 因此，该方法只是一遍又一遍地添加继任者，并且无限期地进行。

您应该尝试在 Node 类中实现 equals(( 方法，看看是否可以修复它。

祝你好运！