用Java解决n-puzzle

我正在尝试实现一个解决n-puzzle problem的程序 .
我在Java中编写了一个简单的实现，它具有一个问题状态，其特征在于表示tile的矩阵 . 我还能够自动生成给出起始状态的所有状态的图形 . 然后，在图表上，我可以使用BFS来查找目标状态的路径 .
但问题是我的内存不足，甚至无法创建整个图形 . 我尝试了2x2瓷砖，它的工作原理 . 还有一些3x3（它取决于起始状态和图中有多少个节点） . 但总的来说这种方式并不合适 .
所以我尝试在运行时生成节点，同时进行搜索 . 它工作，但它很慢（有时几分钟后它仍然没有结束，我终止程序） .
顺便说一句：我只作为起始状态给出了可解决的配置，而且我没有创建重复的状态 .
所以，我无法创建图表 . 这导致了我的主要问题：我必须实现A *算法并且我需要路径成本（即每个节点与起始状态的距离），但我想我无法在运行时计算它 . 我需要整个图表，对吗？因为A *不遵循BFS对图的探索，所以我不知道如何执行A *搜索 .
有什么建议吗？

EDIT

State:

private int[][] tiles;
private int pathDistance;
private int misplacedTiles;
private State parent;

public State(int[][] tiles) {
    this.tiles = tiles;
    pathDistance = 0;
    misplacedTiles = estimateHammingDistance();
    parent = null;
}

public ArrayList<State> findNext() {
    ArrayList<State> next = new ArrayList<State>();
    int[] coordZero = findCoordinates(0);
    int[][] copy;
    if(coordZero[1] + 1 < Solver.SIZE) {
        copy = copyTiles();
        int[] newCoord = {coordZero[0], coordZero[1] + 1};
        switchValues(copy, coordZero, newCoord);
        State newState = checkNewState(copy);
        if(newState != null)
            next.add(newState);
    }
    if(coordZero[1] - 1 >= 0) {
        copy = copyTiles();
        int[] newCoord = {coordZero[0], coordZero[1] - 1};
        switchValues(copy, coordZero, newCoord);
        State newState = checkNewState(copy);
        if(newState != null)
            next.add(newState);
    }
    if(coordZero[0] + 1 < Solver.SIZE) {
        copy = copyTiles();
        int[] newCoord = {coordZero[0] + 1, coordZero[1]};
        switchValues(copy, coordZero, newCoord);
        State newState = checkNewState(copy);
        if(newState != null)
            next.add(newState);
    }
    if(coordZero[0] - 1 >= 0) {
        copy = copyTiles();
        int[] newCoord = {coordZero[0] - 1, coordZero[1]};
        switchValues(copy, coordZero, newCoord);
        State newState = checkNewState(copy);
        if(newState != null)
            next.add(newState);
    }
    return next;
}

private State checkNewState(int[][] tiles) {
    State newState = new State(tiles);
    for(State s : Solver.states)
        if(s.equals(newState))
            return null;
    return newState;
}

@Override
public boolean equals(Object obj) {
    if(this == null || obj == null)
        return false;
    if (obj.getClass().equals(this.getClass())) {
        for(int r = 0; r < tiles.length; r++) { 
            for(int c = 0; c < tiles[r].length; c++) {
                if (((State)obj).getTiles()[r][c] != tiles[r][c])
                    return false;
            }
        }
            return true;
    }
    return false;
}

Solver:

public static final HashSet<State> states = new HashSet<State>();

public static void main(String[] args) {
    solve(new State(selectStartingBoard()));
}

public static State solve(State initialState) {
    TreeSet<State> queue = new TreeSet<State>(new Comparator1());
    queue.add(initialState);
    states.add(initialState);
    while(!queue.isEmpty()) {
        State current = queue.pollFirst();
        for(State s : current.findNext()) {
            if(s.goalCheck()) {
                s.setParent(current);
                return s;
            }
            if(!states.contains(s)) {
                s.setPathDistance(current.getPathDistance() + 1);
                s.setParent(current);
                states.add(s);
                queue.add(s);
            }
        }
    }
    return null;
}

基本上我就是这样做的：

• Solver 的 solve 有一个 SortedSet . 元素（ States ）根据 Comparator1 进行排序，计算 f(n) = g(n) + h(n) ，其中 g(n) 是路径成本， h(n) 是启发式（错位图块的数量） .
• 我给出了起始配置并寻找所有后继者 .
• 如果尚未访问后继（即，如果它不在全局集 States 中），我将其添加到队列并将其添加到 States ，将当前状态设置为其父级，并将 parent's path + 1 设置为其路径开销 .
• 出列并重复 .

我认为应该有效，因为：

• 我保留了所有访问过的状态，所以我没有循环 .
• 此外，还赢得了't be any useless edge because I immediately store current node'的继任者 . 例如：如果来自AI可以转到B和C，并且从BI也可以转到C，则不会有边缘B-> C（因为每条边的路径成本为1，而A-> B比A便宜 - > B-> C） .
• 每次我选择使用最小 f(n) 扩展路径时，请遵循A * .

但它不起作用 . 或者至少，几分钟后它仍然无法找到解决方案（我认为在这种情况下需要很多时间） .
如果我在执行A *之前尝试创建树结构，那么构建它就会耗尽内存 .

EDIT 2

这是我的启发式功能：

private int estimateManhattanDistance() {
    int counter = 0;
    int[] expectedCoord = new int[2];
    int[] realCoord = new int[2];
    for(int value = 1; value < Solver.SIZE * Solver.SIZE; value++) {
        realCoord = findCoordinates(value);
        expectedCoord[0] = (value - 1) / Solver.SIZE;
        expectedCoord[1] = (value - 1) % Solver.SIZE;
        counter += Math.abs(expectedCoord[0] - realCoord[0]) + Math.abs(expectedCoord[1] - realCoord[1]);
    }
    return counter;
}

private int estimateMisplacedTiles() {
    int counter = 0;
    int expectedTileValue = 1;
    for(int i = 0; i < Solver.SIZE; i++)
        for(int j = 0; j < Solver.SIZE; j++) {
            if(tiles[i][j] != expectedTileValue)
                if(expectedTileValue != Solver.ZERO)
                    counter++;
            expectedTileValue++;
        }
    return counter;
}

如果我使用简单的贪婪算法，它们都可以工作（使用曼哈顿距离非常快（大约500次迭代才能找到解决方案），而错误放置的瓦片数量需要大约10k次迭代） . 如果我使用A *（也评估路径成本）它真的很慢 .

比较器是这样的：

public int compare(State o1, State o2) {
    if(o1.getPathDistance() + o1.getManhattanDistance() >= o2.getPathDistance() + o2.getManhattanDistance())
        return 1;
    else
        return -1;
}

EDIT 3

有一点错误 . 我修好了，现在A *有效 . 或者至少，对于3x3，如果找到只有700次迭代的最优解 . 对于4x4它's still too slow. I' ll尝试使用IDA *，但有一个问题：使用A *找到解决方案需要多长时间？分钟？小时？我离开了10分钟，但没有结束 .