Water Jug问题java.lang.OutOfMemoryError:java堆空间

Question

为我的AI类编写一段代码，该代码旨在列出水壶问题的三个罐子的所有可能状态(你可以装满任何罐子，或者从一个罐子倒入另一个罐子，或者清空任何罐子，按照你想要的次数和任何顺序(。

出于某种原因，在记录了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))，这意味着我多次添加每个元素。修复此问题后，代码运行得非常好。