用完java堆空間-15拼圖問題

Question

G'day全部， 我試過解決八拼圖問題發佈here joel Neely和玩過它並修改它，以便可以用來解決更高網格[將網格的字符串表示更改爲二維整數表示並相應地修改了邏輯]。然而，修改後的代碼可以解決3x3網格問題，但快速用完4x4網格的堆空間。我想這是由使用的算法造成的限制，我認爲這是一些分支和界限的變體，而不是java的變體。如果我的假設是正確的，有人可以提出任何其他好的算法來解決這個問題嗎？如果沒有，請提示可以做些什麼來使該程序 適用於更高階的網格。

import java.util.HashMap; 
import java.util.LinkedList; 
import java.util.Map; 
import java.util.Queue; 

class EightPuzzle { 

    //Queue<Integer[][]> agenda = new LinkedList<Integer[][]>(); // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS. 
    //Map<Integer[][],Integer> stateDepth = new HashMap<Integer[][], Integer>(); // HashMap is used to ignore repeated nodes 
    //Map<Integer[][],Integer[][]> stateHistory = new HashMap<Integer[][],Integer[][]>(); // relates each position to its predecessor 
    Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor 
    Map<String,Integer> stateDepth = new HashMap<String,Integer>(); 
    Queue<Integer[][]> agenda=new LinkedList<Integer[][]>(); 
    final int GRIDSIZE=4; 
    int row=0,col=0; 
    public static void main(String args[]){ 

     // Integer[][] str="087465132";         // Input the Board State as a Integer[][] with 0 as the Blank Space 
     Integer init[][]={{1,3,12,4},{2,9,10,7},{0,14,8,15},{5,6,13,11}}; 
     //Integer init[][]={{0,8,7},{4,6,5},{1,3,2}}; 
     EightPuzzle e = new EightPuzzle();    // New Instance of the EightPuzzle 

     e.add(init,null);             // Add the Initial State 

     while(!e.agenda.isEmpty()){ 
      Integer[][] currentState = e.agenda.remove(); 
      e.up(currentState);          // Move the blank space up and add new state to queue 
      e.down(currentState);          // Move the blank space down 
      e.left(currentState);          // Move left 
      e.right(currentState);       // Move right and remove the current node from Queue 
     } 

     System.out.println("Solution doesn't exist"); 
    } 

    //Add method to add the new Integer[][] to the Map and Queue 
    void add(Integer newState[][], Integer oldState[][]){ 
     if(!stateDepth.containsKey(convertToString(newState))){ 
      int newValue = oldState == null ? 0 : stateDepth.get(convertToString(oldState)) + 1; 
      stateDepth.put(convertToString(newState), newValue); 
      agenda.add(newState); 
      stateHistory.put(convertToString(newState), convertToString(oldState)); 
     } 
    } 

    /* Each of the Methods below Takes the Current State of Board as Integer[][]. Then the operation to move the blank space is done if possible. 
     After that the new Integer[][] is added to the map and queue.If it is the Goal State then the Program Terminates. 
    */ 
    void up(Integer[][] currentState){ 
     Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE]; 
     getIndicesOfZero(currentState, nextState); 
     if(row!=0){ 
      nextState[row-1][col]=currentState[row][col]; 
      nextState[row][col]=currentState[row-1][col]; 
      checkCompletion(currentState, nextState); 
     } 
    } 

    /** 
    * @param currentState 
    */ 
    /** 
    * @param currentState 
    */ 
    void down(Integer[][] currentState){ 
     Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE]; 
     getIndicesOfZero(currentState, nextState); 
     if(row!=GRIDSIZE-1){ 
      nextState[row+1][col]=currentState[row][col]; 
      nextState[row][col]=currentState[row+1][col]; 
      checkCompletion(currentState, nextState); 
     } 
    } 
    void left(Integer[][] currentState){ 
     Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE]; 
     getIndicesOfZero(currentState, nextState); 
     if(col!=0){ 
      nextState[row][col-1]=currentState[row][col]; 
      nextState[row][col]=currentState[row][col-1]; 
      checkCompletion(currentState, nextState); 
     } 
    } 
    void right(Integer[][] currentState){ 
     Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE]; 
     getIndicesOfZero(currentState, nextState); 
     if(col!=GRIDSIZE-1){ 
      nextState[row][col+1]=currentState[row][col]; 
      nextState[row][col]=currentState[row][col+1]; 
      checkCompletion(currentState, nextState); 
     } 
    } 

    private void checkCompletion(Integer[][] oldState, Integer[][] newState) { 
     add(newState, oldState); 
     Integer[][] completeState={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}}; 
     //Integer[][] completeState={{1,2,3},{4,5,6},{7,8,0}}; 
     boolean equality=true; 
     outer:for(int i=0;i<GRIDSIZE;i++){ 
      for(int j=0;j<GRIDSIZE;j++){ 
       if(newState[i][j]!=completeState[i][j]){ 
        equality=false; 
        break outer; 
       } 
      } 
     } 

     if(equality){ 
      System.out.println("Solution Exists at Level "+stateDepth.get(convertToString(newState))+" of the tree"); 
      String traceState = convertToString(newState); 
      while (traceState != null) { 
       System.out.println(traceState + " at " + stateDepth.get(traceState)); 
       traceState = stateHistory.get(traceState); 
      } 
      System.exit(0); 

     } 
    } 
    String convertToString(Integer[][] a){ 
     String str=""; 
     if(a!=null){ 
      for(int i=0;i<GRIDSIZE;i++){ 
       for(int j=0;j<GRIDSIZE;j++){ 
        str+=a[i][j]; 
       } 
      } 
     } 
     else{ 
      str=null; 
     } 
     return str; 
    } 
    void getIndicesOfZero(Integer[][] currentState,Integer[][] nextState){ 
     for(int i=0;i<GRIDSIZE;i++){ 
      for(int j=0;j<GRIDSIZE;j++){ 
       nextState[i][j]=currentState[i][j]; 
      } 
     } 
     outer:for(int i=0;i<GRIDSIZE;i++){ 
      for(int j=0;j<GRIDSIZE;j++){ 
       if(currentState[i][j]==0){ 
        row=i; 
        col=j; 
        break outer; 
       } 
      } 
     } 

    } 
} 

在此先感謝， 保羅。

Answer 1

你的算法缺乏啓發式。換句話說，它是在沒有指導的情況下探索搜索空間。對於15個難題，這個空間非常大，接近3 **（解決方案的深度）。

如果您按照每個瓷磚距離其目的地的曼哈頓距離的總和排列您的隊列，則可能足以使其可解決。在每一步中，用最少的「錯誤」展開議程上的項目。

此外，你確定你選擇的開始狀態是可以解決的嗎？如果你隨機訂購瓷磚，你只有50-50的機會。

最後，您可以從Integer切換到byte以節省內存。多少取決於Java的實現，但由於Integer是一個類和字節的原始類型，它可能是重要的。

更新