java - Java 堆空间用完- 15 谜题

Question

大家好， 我尝试了八个难题的解决方案发布 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-puzzle，这个空间相当大，接近 3**(解的深度)。

如果您按每个图 block 与其目的地的曼哈顿距离之和对队列进行排序，则可能足以使其可解。在每一步中，扩展议程上“错误”最少的项目。

此外，您确定您选择的起始状态是可解的吗？如果随机排列方 block ，则只有 50-50 的机会。

最后，您可能会从 Integer 切换到 byte 以节省内存。多少取决于 java 实现，但由于 Integer 是一个类而 byte 是一个基本类型，所以它可能很重要。

已更新