水壶问题Java.lang.OutofMemoryError：Java堆空间

Question

为我的人工智能类编写一段代码，它旨在列出所有可能的状态，给出三个水壶的水壶问题（你可以装满任何一个水壶，或者把一个水壶倒入另一个水壶，或者清空任何一个水壶，你想要多少次就多少次，以任何顺序），从空水壶开始。

出于某种原因，在记录了88个看似不同的状态后，第89个状态与第一个状态相同，我最终用完了空间，因为它在循环。

我想这与我如何检查状态是不同的有关，但我不能弄清楚。任何帮助都将不胜感激。

import java.util.ArrayList;
    import java.util.List;

public class AI {
    private static final int[] start=new int[]{0,0,0};
    private static int[] jugs;
    public static void main(String[] args){
        jugs=new int[]{Integer.parseInt(args[0]), Integer.parseInt(args[1]),Integer.parseInt(args[2])};

    String out="";
    out=out.concat("{");
    for (int[] state:addStates(start,new ArrayList<>())) {
        out=out.concat("{"+state[0]+","+state[1]+","+state[2]+"}");
    }
    out=out.substring(0,out.length()-2).concat("}");
    System.out.println(out);

}

private static List<int[]> addStates(int[] start, List<int[]> states) {


    states.add(start);

    int[][] newStates={
            fillA(start),
            fillB(start),
            fillC(start),
            emptyA(start),
            emptyB(start),
            emptyC(start),
            pour(start,0,1),
            pour(start,0,2),
            pour(start,1,0),
            pour(start,1,2),
            pour(start,2,0),
            pour(start,2,1)
    };

    for (int[] child:newStates) {
        if (!has(states,child)) {
            states.addAll(addStates(child,states));
        }
    }
    System.out.println("close");
    return states;
}
private static boolean has(List<int[]> list, int[] e) { //finds out if list contains something with the same values as e
    for (int[] el:list) {
        boolean is=true;
        for(int i=0;i<e.length;i++){
            if (el[i]!=e[i]){
                is=false;
            }
        }
        if(is){
            return true;
        }
    }
    return false;
}

private static int[] fillA(int[] state) {
    return new int[]{jugs[0],state[1],state[2]};
} //fills A
private static int[] fillB(int[] state) {
    return new int[]{state[0],jugs[1],state[2]};
} //fills B
private static int[] fillC(int[] state) {
    return new int[]{state[0],state[1],jugs[2]};
} //fills C
private static int[] emptyA(int[] state) {
    return new int[]{0,state[1],state[2]};
} //empties A
private static int[] emptyB(int[] state) {
    return new int[]{state[0],0,state[2]};
} //empties B
private static int[] emptyC(int[] state) {
    return new int[]{state[0],state[1],0};
} //empties C
private static int[] pour(int[] state, int from, int into) {
    int currentInto=state[into];
    int currentfrom=state[from];
    if (currentInto+currentfrom>jugs[into]){
        currentfrom-=(jugs[into]-currentInto);
        currentInto=jugs[into];
    } else {
        currentInto+=currentfrom;
        currentfrom=0;
    }

    int[] newState= new int[3];
    newState[from]=currentfrom;
    newState[into]=currentInto;
    newState[3-from-into]=state[3-from-into];

    return newState;
} //moves as much water from "from" into "into"

}

Answer 1

问题是我同时使用了states.add(start)和states.addall(addStates(child,states))，这意味着我添加每个元素的次数非常多。修复了这个问题后，代码运行得非常好。