迭代加深 A Star (IDA*) 在 Java 中解决 n-puzzle（滑动拼图）

我已经实现了一个能够解决这个问题的程序n-拼图问题 http://en.wikipedia.org/wiki/Fifteen_puzzle与 A*。由于状态空间太大，我无法预编译它，我必须在运行时计算可能的状态。通过这种方式，A* 对于 3 谜题来说效果很好，但对于 4 谜题可能需要很长时间。使用线性冲突调整的曼哈顿距离，如果最优解需要大约 25 次移动仍然很快，大约 35 次需要 10 秒，40 次需要 180 秒。我还没有尝试更多。
我认为这是因为我必须保留所有访问过的状态，因为我使用的是可接受的函数，但（我认为）不一致（我也尝试过汉明和加施尼格距离等）。由于解的空间是图，启发式也必须一致，否则算法可能会循环或不是最优的。这就是为什么我保留所有访问过的节点（它也写在《AI：一种现代方法》一书中）。但无论如何，这个存储速度一点也不慢。减慢速度的是保持要访问的节点队列的有序性。
因此，我决定尝试 IDA*，正如我所见，它不需要此存储（但我仍然必须保留所有访问过的状态以避免循环）。对于需要 35 步或更少步数的解决方案来说速度更快，但对于 40 步步数来说则慢得多。
这是我的代码。难道我做错了什么？

public static State solveIDAStar(State initialState) {
    int limit = initialState.getManhattanDistance() + 2 * initialState.getLinearConflicts();
    State result = null;
    while(result == null) {
        visitedStates.add(initialState); // It's a global variable
        result = limitedSearch(initialState, limit);
        limit = newLimit;
        visitedStates.clear();
    }
    return result;
}

public static State limitedSearch(State current, int limit) {
    for(State s : current.findNext()) {
        if(s.equals(GOAL)) {
            s.setParent(current);
            return s;
        }
        if(!visitedStates.contains(s)) {
            s.setPathCost(current.getPathCost() + 1);
            s.setParent(current);
            int currentCost = s.getManhattanDistance() + 2 * s.getLinearConflicts() + s.getPathCost();
            if(currentCost <= limit) {
                visitedStates.add(s);
                State solution = limitedSearch(s, limit);
                if(solution != null)
                    return solution;
            } else {
                if(currentCost < newLimit)
                    newLimit = currentCost;
            }
        }
    }
    return null;
}

旧的东西搬下来了。

进行更改，以便 newLimit 可以跳过步骤（bestSolution 的东西）：

State bestSolution; // add this global

public static State solveIDAStar(State initialState) {
    int limit = initialState.getManhattanDistance() + 2 * initialState.getLinearConflicts();
    bestSolution = null; // reset global to null
    State result = null;
    while(result == null) {
        visitedStates.add(initialState); // It's a global variable
        newLimit = INFINITY;
        result = limitedSearch(initialState, limit);
        limit = newLimit;
        visitedStates.clear();
    }
    return result;
}

public static State limitedSearch(State current, int limit) {
    for(State s : current.findNext()) {
        if(s.equals(GOAL)) {
            s.setParent(current);
            return s;
        }
        if(!visitedStates.contains(s)) {
            s.setPathCost(current.getPathCost() + 1);
            s.setParent(current);
            int currentCost = s.getManhattanDistance() + 2 * s.getLinearConflicts() + s.getPathCost();
            if(currentCost <= limit) {
                visitedStates.add(s);
                State solution = limitedSearch(s, limit);
                if(solution != null &&
                   (bestSolution == null || solution.getPathCost() < bestSolution.getPathCost()))
                        bestSolution = solution; // cache solution so far
            } else {
                if(currentCost < newLimit)
                    newLimit = currentCost;
            }
        }
    }
    return null;
}

原答案

所以我找到了一个开源实现。神奇的是，它也在java中。

该应用程序可以在这里进行测试：http://n-puzzle-solver.appspot.com/ http://n-puzzle-solver.appspot.com/

具体相关的源代码是：http://code.google.com/p/julien-labs/source/browse/trunk/SlidingPuzzle/src/be/dramaix/ai/slidingpuzzle/server/search/IDAStar.java http://code.google.com/p/julien-labs/source/browse/trunk/SlidingPuzzle/src/be/dramaix/ai/slidingpuzzle/server/search/IDAStar.java

不确定下面建议的第一个更改可能会改变多少时间，但我很确定您需要进行第二个更改。

第一次改变

通过对比代码，你会发现这个函数

private Node depthFirstSearch(Node current, int currentCostBound, State goal)

基本上是你在这里的功能

public static State limitedSearch(State current, int limit)

Julien Dramaix 的实现没有：

if(!visitedStates.contains(s)) {
    ...
    visitedStates.add(s);

所以把这两条线拿出来测试一下。

第二次改变

你的职能public static State solveIDAStar(State initialState)在 while 循环中做了一些奇怪的事情。

失败一次后，您将最大深度（限制）设置为无穷大。基本上，第一次迭代时，您尝试找到与您的启发式一样好的解决方案。然后你尝试寻找任何解决方案。这不是迭代深化.

迭代深化意味着每次尝试时，都要更深入一点。

事实上，看看 while 循环public PuzzleSolution resolve(State start, State goal)， 你会找到nextCostBound+=2;。这意味着，每次尝试时，请尝试通过最多 2 个动作找到解决方案。

否则，其他一切看起来都很相似（尽管 State 类的确切实现可能略有不同）。

如果效果更好，您可能还想尝试其他一些启发式方法http://code.google.com/p/julien-labs/source/browse/#svn%2Ftrunk%2FSlidingPuzzle%2Fsrc%2Fbe%2Fdramaix%2Fai%2Fslidingpuzzle%2Fclient http://code.google.com/p/julien-labs/source/browse/#svn%2Ftrunk%2FSlidingPuzzle%2Fsrc%2Fbe%2Fdramaix%2Fai%2Fslidingpuzzle%2Fclient.

启发式方法可在 server/search/heuristic 文件夹中找到。