优化N皇后代码，以避免堆栈溢出

我一直在尝试编写一个Java类来解决使用某种堆叠和递归，答案存储在网格（二维数组）的n皇后问题，但我'在n = 8时达到递归堆栈溢出的死墙（最大递归深度达到2298）所以我一直在想，是否有一些方法可以通过执行一些复杂的事情来绕过这个死亡，比如在java中分配更多的堆空间如果可能的话？），或者使用多线程（点我出去教程/例）......还是请你就如何优化代码... 在此先感谢优化N皇后代码，以避免堆栈溢出

public void resoudre(){ 

     this.gridPile.push(copyGrid(grid)); 
     try{ 
      int row = gridPile.size()-1; 
      if(gridPile.size()==0)row = 0; 
      chooseGridSpace(this.grid, locateFirstAvailable(grid, row)); 
      if(gridPile.size() == this.taille){ 
       gridSolutions.push(copyGrid(grid)); 
       grid = gridPile.pop(); 
       boolean erronous = true; 
       while(erronous){ 
        try{ 
         MakeNextUnavailable(grid, gridPile.size()); 
         erronous = false; 
        } 
        catch(UnavailabilityException r1){ 
         try{ 
          grid = gridPile.pop(); 
         } 
         catch(java.util.EmptyStackException r2){ 
          return; 
         } 
        } 
       } 
      } 

     } 
     catch(InvalidPositionException e1){ 
      this.grid = gridPile.pop(); 
      boolean error = true; 
      while(error){ 
       try{ 
        MakeNextUnavailable(grid, gridPile.size()); 
        error = false; 
       } 
       catch(UnavailabilityException er){ 
        try{ 
         this.grid = gridPile.pop(); 
        } 
        catch(java.util.EmptyStackException err){ 
         return; 
        } 
       } 
      } 
     } 
     catch(java.lang.ArrayIndexOutOfBoundsException e2){ 
      return; 
     } 
     this.resoudre(); 
    } 

    private static void chooseGridSpace(int[][] grid, Position a){ 
     grid[a.getLigne()][a.getColonne()] = 1; 
     fillNotAvailable(grid, a); 
    }

来源

2009-07-26 user145296

我已经做了一些简单的优化，一个是避免递归结构所以不是 public void resoudre(){ /** * Lines of code */ resourdre(); } 我把它 public void resoudre(){ do{ /** * Lines of code */ } while(true); } 无论如何，我同意一些下面的意见，程序结构更简单，但我选择了这种方式来缓解gui操作以后... – user145296 2009-07-26 15:44:13

-3

在Java中，命令的意见-ss和-oss可以b也可用于更改堆栈大小。

$java -ss156k (native) 
$java -oss600k (Java)

参数是您希望的堆栈大小，以千字节或mbytes为单位。尝试一些增加的值，直到不溢出。

来源

2009-07-26 14:46:41

你的答案有助于绕过我的问题n = 8和9，但我再次撞到死墙，但一次我解决了递归结构（resoudre）函数，我不需要使用这些命令......但是， anks寻求帮助:) – user145296 2009-07-26 16:28:53

阅读代码，它看起来像你的程序使用堆栈< ..>而不是Java递归。因此它可能用完Java堆空间而不是Java堆栈空间。如果是这种情况，您可以使用-Xms和-Xmx选项来增加堆大小的初始和最大值。

来源

2009-07-26 14:56:11

但是@vos是对的，你的算法不雅，可怕的效率低下，修复这个问题会更好地解决问题。 – 2009-07-26 15:13:54

直接回答：没有必要将整个网格推入堆栈，并且您可能希望将网格表示为表示每行的女王位置的8个整数的数组。

真正的问题：您的代码太长，太复杂。把事情简单化！女王的问题通常由两个函数来解决，每个函数为<。是很简单，只要：

public static boolean isSolution(final int[] board) 
{ 
    for (int i = 0; i < board.length; i++) { 
     for (int j = i + 1; j < board.length; j++) { 
      if (board[i] == board[j]) return false;  // same column "|" 
      if (board[i]-board[j] == i-j) return false; // diagonal "\" 
      if (board[i]-board[j] == j-i) return false; // diagonal "/" 
     } 
    } 
    return true; 
} 

public static void solve(int depth, int[] board) 
{ 
    if (depth == board.length && isSolution(board)) { 
     outputSolution(board); 
    } 
    if (depth < board.length) { // try all positions of the next row 
     for (int i = 0; i < board.length; i++) { 
      board[depth] = i; 
      solve(depth + 1, board); 
     } 
    } 
}

添加一些输出码和主程序，你就完蛋了！

public static void outputSolution(final int[] board) 
{ 
    System.out.println("--- Solution ---"); 
    for (int i = 0; i < board.length; i++) { 
     for (int j = 0; j < board[i]; j++) System.out.print(" "); 
     System.out.println("Q"); 
    } 
} 

public static void main(String[] args) 
{ 
    int n = 8; 
    solve(0, new int[n]); 
}

来源

2009-07-26 15:02:56 vog

您好，感谢您的时间......我必须同意你的代码是非常雄辩和简洁，我第一次尝试失败，因为使用消耗内存在递归的方式重复结构的...但一旦我淘汰的递归性，我收获我不是那么简洁的代码的好处...例如，对于n = 10，高雄辩性运行超过3分钟（然后我停止了它），而我的代码花了3秒钟，它输出所有的解决方案... @stephen c，现在我可以说我非常不同意;） – user145296 2009-07-26 16:20:28

这与简洁与非简洁没有任何关系！这只是我的isSolution（）函数，它有点愚蠢。它以错误的顺序检查内容并且不执行部分解决方案的检查。如果您优化它，我的代码会增长大约1-2行。 – vog 2009-07-26 22:11:51

没有理由以达到2298堆栈深度为N = 8！

正确的算法是用8个整数的数组来表示皇后，每个整数代表第i个皇后（皇后每列）的行位置。

你的最大堆栈大小应为8

来源

2009-07-26 15:13:51 ripper234

优化N皇后代码，以避免堆栈溢出

回答

相关问题