代码之家  ›  专栏  ›  技术社区  ›  AutoTester213

EmptySackException-二维数组上的Java深度优先搜索算法

depth-first-search stack exception algorithm java
  •  -3
  • AutoTester213  · 技术社区  · 6 年前

    我看了这个问题 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;
            }
        }
    }
}
    3 回复  |  直到 6 年前
        1
  •  4
  •   thenamethatwasnottaken    6 年前

    你的一个问题在我看来是问题的根源:“我在这里遗漏了什么?”?单元测试,除非我在你的项目中没有看到它们。

    1. 在对没有结束的代码段编写测试的过程中 问题是,你会明确地证明他们不是 问题。
    2. 是“太复杂”无法测试,重新编写它会让你 设计师和经常会导致“我不敢相信我没有看到” 瞬间。
    3. 当您重构这个程序时(减少复杂性,重命名变量以使其更易于理解等),如果出现问题,您将立即得到通知 你不用再花一个周末去想办法了。

    例如,不要在搜索它的方法中随机化电路板,而是在其他地方随机化电路板,然后将其作为参数放入该方法中(或放入类的构造函数中)。这样,您可以使用自己提供的值初始化自己的测试板,并查看某些板是否比其他板工作得更好,以及原因。将较大的方法分成较小的方法,每个方法都有自己的参数和测试。目标是用较小的已确认的工件制作一个程序,而不是制作一个大的东西,然后想知道问题是你认为它是小的部分还是其他什么。

    从长远来看,你将节省大量的时间和挫败感,最终你将领先于那些编码数小时,然后调试数小时的人。

        2
  •  0
  •   Rosa Mohammadi    6 年前 

    // 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)迭代,此时堆栈上可能没有任何内容,因为您没有添加任何其他内容。

        3
  •  0
  •   Jatish    6 年前

    我同意@Rosa-

    ===代码中的迭代/状态====== 

     **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迭代======== 

      while(true){
            AddBridges state = gameTree.peek(); // gameTree.size() = 0 and a peek

    必需的空头支票- 

    if(gameTree.isEmpty()){ 
            System.out.println("no valid configuration found");
            return;
        }
        AddBridges state = gameTree.peek();

    推荐文章
    pickle323  ·  C编程:现代方法-第10章项目6-困惑
    6 年前
    lokanadham100  ·  Ruby:堆栈级别太深(SystemStackError)maxlimit
    6 年前
    Gameatro  ·  为什么malloc在函数内部调用时返回空指针?
    6 年前
    Min  ·  在C++中,是否有“-Wl,-stack,[一个数字,例如4194304表示4Mb的堆栈]”的CUDA等价物?
    6 年前
    E. Peracchia  ·  F#函数调用工作不正常
    6 年前
    elvis  ·  整数对象的内存地址
    6 年前
    Carmen Ferrone  ·  哦!(“(”)。equals(stack.peek())工作不正常
    6 年前
    Jorge Zazueta  ·  汉诺塔C++的堆栈实现
    6 年前
    Elle Fie  ·  在Javascript中,Tcl的“uplevel”等效于什么?
    6 年前
    adamcasey  ·  缓冲区溢出“攻击”中的操作序列
    6 年前
    关于   移动版
    代码之家 - 一站式码农服务社区
    沪ICP备11025650号