我已经实现了一个能够使用A*算法解决n-拼图问题的程序。由于状态空间太大，我无法预编译，必须在运行时计算可能的状态。这样，A*算法在3-拼图上运行良好，但在4-拼图上可能需要很长时间。使用调整后的曼哈顿距离和线性冲突，如果最优解大约需要25步，仍然很快，35步大约需要10秒，40步需要180秒。我还没有尝试更多步数。
我认为这是因为我必须保留所有访问过的状态，因为我使用的是可接受但（我认为）不一致的函数（我也尝试了汉明距离和Gaschnig距离以及其他几个）。由于解空间是一个图，启发式必须也是一致的，否则算法可能会循环或不是最优的。这就是为什么我保留所有访问过的节点（这也在《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); // 这是一个全局变量 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; // 添加这个全局变量public static State solveIDAStar(State initialState) { int limit = initialState.getManhattanDistance() + 2 * initialState.getLinearConflicts(); bestSolution = null; // 将全局变量重置为null State result = null; while(result == null) { visitedStates.add(initialState); // 这是一个全局变量 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; // 缓存迄今为止的最佳解 } else { if(currentCost < newLimit) newLimit = currentCost; } } } return null;}原始回答
我找到了一个开源实现。奇迹般地，它也是用Java写的。
可以在这里测试该应用程序：http://n-puzzle-solver.appspot.com/
不确定下面建议的第一个更改会对所需时间产生多大影响，但我相当确定你需要进行第二个更改。
第一个更改
通过比较代码，你会发现这个函数
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循环中做了一些奇怪的事情。
在你第一次失败后，你将最大深度（limit）设置为无穷大。基本上，第一次迭代，你尝试找到一个与你的启发式一样好的解。然后你尝试找到任何解。这不是迭代加深。
迭代加深意味着每次尝试时，都要深入一点。
实际上，查看public PuzzleSolution resolve(State start, State goal)中的while循环，你会发现nextCostBound+=2;。这意味着，每次尝试时，尝试找到最多增加2步的解。
否则，其他一切看起来都相似（尽管你对State类的具体实现可能略有不同）。
如果效果更好，你可能还想尝试http://code.google.com/p/julien-labs/source/browse/#svn%2Ftrunk%2FSlidingPuzzle%2Fsrc%2Fbe%2Fdramaix%2Fai%2Fslidingpuzzle%2Fclient中的其他启发式方法。
启发式方法可以在server/search/heuristic文件夹中找到。
