Manquer du problème 15 puzzle tas java

Question

G'day tout, j'ai essayé la solution pour le problème de huit casse-tête posté here par joel Neely et joué avec elle et modifié de sorte que peut être utilisé pour résoudre pour plus grids [Modification de la représentation sous forme de chaîne de la représentation en nombres entiers bidimensionnels et modification de la logique en conséquence]. Cependant, le code modifié peut résoudre les grilles 3x3 mais rapidement manquer d'espace tas pour la grille 4x4. Je suppose que c'est la restriction causée par l'algorithme utilisé qui, je pense, est une variation de la branche et liée et non celle de Java. Si mes hypothèses sont bonnes, quelqu'un peut-il suggérer d'autres bons algorithmes pour résoudre ce problème? Si ce n'est pas le cas, veuillez indiquer ce qui peut être fait pour que ce programme fonctionne pour les grilles d'ordre supérieur.

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; 
       } 
      } 
     } 

    } 
} 

Merci d'avance, paul.

Answer 1

Votre algorithme manque d'heuristique. En d'autres termes, il explore l'espace de recherche sans guide. Pour le 15-puzzle, cet espace est assez grand, proche de 3 ** (profondeur de la solution).

Si vous commandez votre file d'attente par la somme de la distance Manhattan de chaque tuile de sa destination, il pourrait être suffisant pour le rendre solvable. À chaque étape, développez l'élément sur l'agenda avec le moins "erreur".

Etes-vous sûr que l'état de démarrage que vous avez choisi est résolu? Si vous commandez au hasard les tuiles, vous avez seulement 50-50 chances.

Enfin, vous pouvez passer de Integer à byte pour économiser de la mémoire. Combien dépend de l'implémentation java, mais comme Integer est une classe et un octet un type primitif, cela peut être significatif.

Mise à jour