java - 线程中的异常 "main"java.lang.StackOverflowError 问题

Question

我需要你的帮助。我不知道为什么当维度为 10 且脏槽为 11 时我的代码会失败，请帮忙。

package Strategies;

import java.util.LinkedList;
import java.util.Queue;

import Cleaning.State;

public class BFS {

private int dirty;
private Queue<State> fifo = new LinkedList<State>();
private String path = "";
private int num_of_expanded_states;
private boolean failure = false;

public BFS(State state, int dirty) {
    // TODO Auto-generated constructor stub
    this.dirty = dirty;
    this.num_of_expanded_states = 0;
    this.fifo.add(state);
}

public void startCleaning() {
    // TODO Auto-generated method stub
    successorFunction(fifo.element());
    if(failure){
        System.out.println("There is no solution under the constraint of  maximum number of dirty slots");
        return;
    }

}


public void successorFunction(State state){
    int x,y,i;

    State temp = new State(state);

//      state.printRoom();
    if(goalTest(state)){
        printPath(state);
        return;
    }


    x = state.x;
    y = state.y;


    // checking valid moves

    if(x+3 <= state.room.length-1){
        if(y+1 <= state.room.length-1){
            if(state.room[x+1][y]==1 && state.room[x+2][y]==1 && state.room[x+3][y]==1 && state.room[x+3][y+1]==1){
                for(i=1;i<=3;i++){
                    temp.room[x+i][y]=0;
                }
                temp.room[x+i-1][y+1]=0;
                temp.x = x+i-1;
                temp.y = y+1;
                temp.father = new State(state);
                temp.action = "3";
                fifo.add(temp);
            }
        }

        temp = new State(state);

        if(y-1 >= 0){
            if(state.room[x+1][y]==1 && state.room[x+2][y]==1 && state.room[x+3][y]==1 && state.room[x+3][y-1]==1){
                for(i=1;i<=3;i++){
                    temp.room[x+i][y]=0;
                }
                temp.room[x+i-1][y-1]=0;
                temp.x = x+i-1;
                temp.y = y-1;
                temp.father = new State(state);
                temp.action = "1";
                fifo.add(temp);
            }
        }
    }

    temp = new State(state);

    if(x-3 >= 0){
        if(y+1 <= state.room.length-1){
            if(state.room[x-1][y]==1 && state.room[x-2][y]==1 && state.room[x-3][y]==1 && state.room[x-3][y+1]==1){
                for(i=1;i<=3;i++){
                    temp.room[x-i][y]=0;
                }

                temp.room[x-i+1][y+1]=0;
                temp.x = x-i+1;
                temp.y = y+1;
                temp.father = new State(state);
                temp.action = "5";
                fifo.add(temp);
            }
        }

        temp = new State(state);

        if(y-1 >= 0){
            if(state.room[x-1][y]==1 && state.room[x-2][y]==1 && state.room[x-3][y]==1 && state.room[x-3][y-1]==1){
                for(i=1;i<=3;i++){
                    temp.room[x-i][y]=0;
                }

                temp.room[x-i+1][y-1]=0;
                temp.x = x-i+1;
                temp.y = y-1;
                temp.father = new State(state);
                temp.action = "7";
                fifo.add(temp);
            }
        }
    }

    temp = new State(state);

    if(y+3 <= state.room.length-1){
        if(x+1 <= state.room.length-1){
            if(state.room[x][y+1]==1 && state.room[x][y+2]==1 && state.room[x][y+3]==1 && state.room[x+1][y+3]==1){
                for(i=1;i<=3;i++){
                    temp.room[x][y+i]=0;
                }

                temp.room[x+1][y+i-1]=0;
                temp.x = x+1;
                temp.y = y+i-1;
                temp.father = new State(state);
                temp.action = "2";
                fifo.add(temp);
            }
        }

        temp = new State(state);

        if(x-1 >= 0){
            if(state.room[x][y+1]==1 && state.room[x][y+2]==1 && state.room[x][y+3]==1 && state.room[x-1][y+3]==1){
                for(i=1;i<=3;i++){
                    temp.room[x][y+i-1]=0;
                }

                temp.room[x-1][y+i-1]=0;
                temp.x = x-1;
                temp.y = y+i-1;
                temp.father = new State(state);
                temp.action = "4";
                fifo.add(temp);
            }
        }
    }

    temp = new State(state);

    if(y-3 >= 0){
        if(x+1 <= state.room.length-1){
            if(state.room[x][y-1]==1 && state.room[x][y-2]==1 && state.room[x][y-3]==1 && state.room[x+1][y-3]==1){
                for(i=1;i<=3;i++){
                    temp.room[x][y-i]=0;
                }

                temp.room[x+1][y-i+1]=0;
                temp.x = x+1;
                temp.y = y-i+1;
                temp.father = new State(state);
                temp.action = "0";
                fifo.add(temp);
            }
        }

        temp = new State(state);

        if(x-1 >= 0){
            if(state.room[x][y-1]==1 && state.room[x][y-2]==1 && state.room[x][y-3]==1 && state.room[x-1][y-3]==1){
                for(i=1;i<=3;i++){
                    temp.room[x][y-i]=0;
                }

                temp.room[x-1][y-i+1]=0;
                temp.x = x-1;
                temp.y = y-i+1;
                temp.father = new State(state);
                temp.action = "6";
                fifo.add(temp);
            }
        }
    }

    num_of_expanded_states = num_of_expanded_states+1;

    // return
    fifo.remove();
    if(fifo.isEmpty()){
        failure = true;
        return;
    }
    else{
        successorFunction(fifo.element());
    }
}

public boolean goalTest(State state){
    int counter = 0;

    for (int i=0;i<state.room.length;i++){
        for (int j=0;j<state.room.length;j++){
            if(state.room[i][j] == 1){
                counter++;
            }
        }
    }

    if(counter <= dirty){
        return true;
    }
    else{       
        return false;
    }

}

public int pathCost(String path){

    if(path.equals(null)){
        return 0;
    }

    path.split("(?!^)");
    return path.length();
}

public void printPath(State goal_state){

    System.out.println(calculatePath(goal_state));
    System.out.println("The number of expanded nodes is: "+num_of_expanded_states);

}

public String calculatePath(State state){
    if(state.father==null){
        return path;
    }
    return calculatePath(state.father).concat(state.action);

}
}

这是状态代码:

package Cleaning;

public class State {

public  long[][] room;
public State father;
public String action;
public int x;
public int y;


public State(State another){
    this.room = new long[another.room.length][another.room.length];
    this.father = another.father;
    this.x = another.x;
    this.y = another.y;
    this.action = another.action;

    for(int i=0; i<this.room.length; i++)
        for(int j=0; j<this.room.length; j++)
            this.room[i][j] = another.room[i][j];
}

public State() {
    // TODO Auto-generated constructor stub
}

public void initializeState(int dimention){     
    int i,j;

    this.room = new long[dimention][dimention];
    this.action = "";
    this.father = new State();
    father = null;
    this.x = dimention - 1;
    this.y = 0;

    for(i=0;i<dimention;i++){
        for(j=0;j<dimention;j++){
            if(i == (dimention-1) && j==0){
                room[i][j] = 0;
            }
            else{
                room[i][j] = 1;
            }
        }
    }
}

public void printRoom(){
    for(int i=0;i<room.length;i++){
        for(int j=0;j<room.length;j++){
            System.out.print(room[i][j]+" ");
        }
        System.out.println();
    }
}
}

我尝试了一切，但无法解决此异常，请帮忙。并感谢您的帮助

日志:

Exception in thread "main" java.lang.StackOverflowError at 
java.util.LinkedList.removeFirst(Unknown Source)
at java.util.LinkedList.remove(Unknown Source) at Strategies.BFS.successorFunction(BFS.java:195)
at Strategies.BFS.successorFunction(BFS.java:201)
at Strategies.BFS.successorFunction(BFS.java:201)
at Strategies.BFS.successorFunction(BFS.java:201)
at Strategies.BFS.successorFunction(BFS.java:201)
at Strategies.BFS.successorFunction(BFS.java:201)
at Strategies.BFS.successorFunction(BFS.java:201) 


there is a lot lines like the above one so i can't include all of them

Answer 1

您可以解决 stackover-flow 问题，但将 successFunction 从递归更改为迭代，例如

private void successsFunction(声明另一个){

  ...
  else {
     successFunction(fifo.element());
  }

}

至

private void successFunction() {
  while(!fifo.isEmpty()) {
    another = fifo.element();
    ...
  }
}

这将使您的问题从堆栈溢出变成运行缓慢和/或内存不足。

我相信您真正的问题是，由于您标记房间已被访问的方式以及每次复制房间状态以创建新房间的方式，您经过相同房间的次数远远多于您需要的次数状态

来自您的代码

public State(State another){
    this.room = new long[another.room.length][another.room.length];
    ....

    for(int i=0; i<this.room.length; i++)
        for(int j=0; j<this.room.length; j++)
            this.room[i][j] = another.room[i][j];
}

...
private successFunction() {
  ...
  for(i=1;i<=3;i++){
     temp.room[x][y+i]=0;
  }

这意味着您仅标记该房间以及该房间的所有子级访问过的这些房间。如果我们有一个简单的房子，房间 1 连接到房间 10 和 11，房间 10 连接到房间 11、100 和 101。房间 11 连接到房间 10、110 和 111。

• 您将访问房间 1，将其标记为已访问，添加房间 10 和 11 [recuse] queue=[10,11]
• 访问房间 10 将其标记为已访问并添加房间 11、100 和 101 [recuse] queue=[11,11,100,101]
• 访问房间 11 将其标记为已访问，添加房间 110 和 111 [recuse] queue=[11,100,101,,110, 111]
• 访问房间 11 将其标记为已访问，添加房间 110 和 111 [recuse] queue=[11,100,101,110, 111,110,111 ]

如果你打印出每个 successFunction 开始时你所在的房间，以及 fifo 队列上的房间，你就会明白我的意思。

我建议对此问题的答案是仅拥有一组房间，并让每个州引用该集合。

所以

public State(State another){
    this.room = another.room;
    ....

    //for(int i=0; i<this.room.length; i++)
    //    for(int j=0; j<this.room.length; j++)
    //        this.room[i][j] = another.room[i][j];
}