二维数组上的EmptyStackException - Java深度优先搜索算法
二维数组上的EmptyStackException - Java深度优先搜索算法
提问于 2018-08-22 18:08:59
我已经看过这个问题了，here，我尝试了那里的大多数代码样本，但是当我在我的代码中使用它时，它只是跳过了算法。
我有一个使用堆栈的DFS算法，我正在获取一个EmptyStackException，我已经调试了算法，在第一次递归搜索之后，堆栈是空的，第一次搜索起作用了，但是随后堆栈的大小设置为0，我在这里遗漏了什么？github
如何确保第一次搜索后堆栈不为空？
我得到异常的那一行是while(true){AddBridges state = gameTree.peek(); ...
我使用二维数组来随机生成从0到4 0 = null 1-4 = island的节点。每次用户开始游戏时，数组都会生成随机整数，这可能会导致算法刹车，
经过一个周末的调试，我发现算法有时在4-6次搜索后刹车，有时在第一次搜索后中断。
public int[][] debug_board_state_easy = new int[4][4];
//This Generates random 2d array
private void InitializeEasy() {
Random rand = new Random();
setCurrentState(new State(WIDTH_EASY));
for (int row = 0; row < debug_board_state_easy.length; row++) {
for (int column = 0; column < debug_board_state_easy[row].length; column++) {
debug_board_state_easy[row][column] = Integer.valueOf(rand.nextInt(5));
}
}
for (int row = 0; row < debug_board_state_easy.length; row++) {
for (int column = 0; column < debug_board_state_easy[row].length; column++) {
System.out.print(debug_board_state_easy[row][column] + " ");
}
System.out.println(debug_board_state_easy);
}
//I am applying the search algorithm here...
this.search();
for (int row = 0; row < WIDTH_EASY; ++row) {
for (int column = 0; column < WIDTH_EASY; ++column) {
getCurrentState().board_elements[row][column] = new BoardElement();
getCurrentState().board_elements[row][column].max_connecting_bridges = Integer.valueOf(debug_board_state_easy[row][column]);
getCurrentState().board_elements[row][column].row = row;
getCurrentState().board_elements[row][column].col = column;
if (getCurrentState().board_elements[row][column].max_connecting_bridges > 0) {
getCurrentState().board_elements[row][column].is_island = true;
}
}
}
}
void search() {
Map<Point, List<Direction>> remainingOptions = new HashMap<>();
Stack<Land> gameTree = new Stack<>();
gameTree.push(new AddBridges(debug_board_state_easy));
while(true) {
AddBridges state = gameTree.peek();
int[] p = state.lowestTodo();
if (p == null)
System.out.println("solution found");
// move to next game state
int row = p[0];
int column = p[1];
System.out.println("expanding game state for node at (" + row + ", " + column + ")");
List<Direction> ds = null;
if(remainingOptions.containsKey(new Point(row,column)))
ds = remainingOptions.get(new Point(row,column));
else{
ds = new ArrayList<>();
for(Direction dir : Direction.values()) {
int[] tmp = state.nextIsland(row, column, dir);
if(tmp == null)
continue;
if(state.canBuildBridge(row,column,tmp[0], tmp[1]))
ds.add(dir);
}
remainingOptions.put(new Point(row,column), ds);
}
// if the node can no longer be expanded, and backtracking is not possible we quit
if(ds.isEmpty() && gameTree.isEmpty()){
System.out.println("no valid configuration found");
return;
}
// if the node can no longer be expanded, we need to backtrack
if(ds.isEmpty()){
gameTree.pop();
remainingOptions.remove(new Point(row,column));
System.out.println("going back to previous decision");
continue;
}
Direction dir = ds.remove(0);
System.out.println("connecting " + dir.name());
remainingOptions.put(new Point(row,column), ds);
AddBridgesnextState = new AddBridges(state);
int[] tmp = state.nextIsland(row,column,dir);
nextState.connect(row,column, tmp[0], tmp[1]);
gameTree.push(nextState);
}
}
}添加网桥类
public class AddBridges {
private int[][] BRIDGES_TO_BUILD;
private boolean[][] IS_ISLAND;
private Direction[][] BRIDGES_ALREADY_BUILT;
public Land(int[][] bridgesToDo){
BRIDGES_TO_BUILD = copy(bridgesToDo);
int numberRows = bridgesToDo.length;
int numberColumns = bridgesToDo[0].length;
BRIDGES_ALREADY_BUILT = new Direction[numberRows][numberColumns];
IS_ISLAND = new boolean[numberRows][numberColumns];
for(int i=0;i<numberRows;i++) {
for (int j = 0; j < numberColumns; j++) {
BRIDGES_ALREADY_BUILT[i][j] = null;
IS_ISLAND[i][j] = bridgesToDo[i][j] > 0;
}
}
}
public AddBridges (AddBridges other){
BRIDGES_TO_BUILD = copy(other.BRIDGES_TO_BUILD);
int numberRows = BRIDGES_TO_BUILD.length;
int numberColumns = BRIDGES_TO_BUILD[0].length;
BRIDGES_ALREADY_BUILT = new Direction[numberRows][numberColumns];
IS_ISLAND = new boolean[numberRows][numberColumns];
for(int i=0;i<numberRows;i++) {
for (int j = 0; j < numberColumns; j++) {
BRIDGES_ALREADY_BUILT[i][j] = other.BRIDGES_ALREADY_BUILT[i][j];
IS_ISLAND[i][j] = other.IS_ISLAND[i][j];
}
}
}
public int[] next(int r, int c, Direction dir){
int numberRows = BRIDGES_TO_BUILD.length;
int numberColumns = BRIDGES_TO_BUILD[0].length;
// out of bounds
if(r < 0 || r >=numberRows || c < 0 || c >= numberColumns)
return null;
// motion vectors
int[][] motionVector = {{-1, 0},{0,1},{1,0},{0,-1}};
int i = Arrays.asList(Direction.values()).indexOf(dir);
// calculate next
int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]};
r = out[0];
c = out[1];
// out of bounds
if(r < 0 || r >=numberRows || c < 0 || c >= numberColumns)
return null;
// return
return out;
}
public int[] nextIsland(int row, int column, Direction dir){
int[] tmp = next(row,column,dir);
if(tmp == null)
return null;
while(!IS_ISLAND[tmp[0]][tmp[1]]){
tmp = next(tmp[0], tmp[1], dir);
if(tmp == null)
return null;
}
return tmp;
}
public boolean canBuildBridge(int row0, int column0, int row1, int column1){
if(row0 == row1 && column0 > column1){
return canBuildBridge(row0, column1, row1, column0);
}
if(column0 == column1 && row0 > row1){
return canBuildBridge(row1, column0, row0, column1);
}
if(row0 == row1){
int[] tmp = nextIsland(row0, column0, Direction.EAST);
if(tmp == null)
return false;
if(tmp[0] != row1 || tmp[1] != column1)
return false;
if(BRIDGES_TO_BUILD[row0][column0] == 0)
return false;
if(BRIDGES_TO_BUILD[row1][column1] == 0)
return false;
for (int i = column0; i <= column1 ; i++) {
if(IS_ISLAND[row0][i])
continue;
if(BRIDGES_ALREADY_BUILT[row0][i] == Direction.NORTH)
return false;
}
}
if(column0 == column1){
int[] tmp = nextIsland(row0, column0, Direction.SOUTH);
if(tmp == null)
return false;
if(tmp[0] != row1 || tmp[1] != column1)
return false;
if(BRIDGES_TO_BUILD[row0][column0] == 0 || BRIDGES_TO_BUILD[row1][column1] == 0)
return false;
for (int i = row0; i <= row1 ; i++) {
if(IS_ISLAND[i][column0])
continue;
if(BRIDGES_ALREADY_BUILT[i][column0] == Direction.EAST)
return false;
}
}
// default
return true;
}
public int[] lowestTodo(){
int R = BRIDGES_TO_BUILD.length;
int C = BRIDGES_TO_BUILD[0].length;
int[] out = {0, 0};
for (int i=0;i<R;i++) {
for (int j = 0; j < C; j++) {
if(BRIDGES_TO_BUILD[i][j] == 0)
continue;
if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0)
out = new int[]{i, j};
if (BRIDGES_TO_BUILD[i][j] < BRIDGES_TO_BUILD[out[0]][out[1]])
out = new int[]{i, j};
}
}
if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0) {
return null;
}
return out;
}
@TargetApi(Build.VERSION_CODES.GINGERBREAD)
private int[][] copy(int[][] other){
int[][] out = new int[other.length][other.length == 0 ? 0 : other[0].length];
for(int r=0;r<other.length;r++)
out[r] = Arrays.copyOf(other[r], other[r].length);
return out;
}
public void connect(int r0, int c0, int r1, int c1){
if(r0 == r1 && c0 > c1){
connect(r0, c1, r1, c0);
return;
}
if(c0 == c1 && r0 > r1){
connect(r1, c0, r0, c1);
return;
}
if(!canBuildBridge(r0, c0, r1, c1))
return;
BRIDGES_TO_BUILD[r0][c0]--;
BRIDGES_TO_BUILD[r1][c1]--;
if(r0 == r1){
for (int i = c0; i <= c1 ; i++) {
if(IS_ISLAND[r0][i])
continue;
BRIDGES_ALREADY_BUILT[r0][i] = Direction.EAST;
}
}
if(c0 == c1){
for (int i = r0; i <= r1 ; i++) {
if(IS_ISLAND[i][c0])
continue;
BRIDGES_ALREADY_BUILT[i][c0] = Direction.NORTH;
}
}
}
}回答 2
Stack Overflow用户
发布于 2018-08-26 05:11:02
代码中发生了很多事情，但我注意到的第一件事可能会有所帮助：
// if the node can no longer be expanded, we need to backtrack
if(ds.isEmpty()){
gameTree.pop();
remainingOptions.remove(new Point(row,column));
System.out.println("going back to previous decision");
continue;
}您从堆栈中弹出，然后继续下一次while(true)迭代，此时，堆栈上可能没有任何内容，因为您没有添加任何其他内容。
Stack Overflow用户
发布于 2018-08-29 16:20:17
我同意“罗莎”-
删除或查找空堆栈时应出现EmptyStackException -
=代码======中的迭代/状态
**if(ds.isEmpty()){** //HashMap isEmpty = true and gameTree.size() = 1
gameTree.pop(); // After removing element gameTree.size() = 0 (no elements in stack to peek or pop)
remainingOptions.remove(new Point(row,column));
System.out.println("going back to previous decision");
continue; //Skip all the instruction below this, continue to next iteration
}========Next iteration========
while(true){
AddBridges state = gameTree.peek(); // gameTree.size() = 0 and a peek 操作将失败，程序将返回EmptyStackException。
必需的isEmpty检查-
if(gameTree.isEmpty()){
System.out.println("no valid configuration found");
return;
}
AddBridges state = gameTree.peek(); 因为，除了while循环之外，函数没有执行任何操作。如果要处理其他指令，则需要“中断”。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/51964525
复制相关文章
相似问题