我已经实现了一个能够解决 n-puzzle problem 问题的程序与*。由于状态空间太大，我无法预编译它，我必须在运行时计算可能的状态。通过这种方式，A* 对于 3-puzzle 可以很好地工作，但对于 4-puzzle 可能会花费太长时间。使用线性冲突调整的曼哈顿距离，如果最优解需要大约 25 次移动仍然很快，大约 35 次需要 10 秒，40 次需要 180 秒。我还没有尝试更多。
我认为那是因为我必须保留所有访问过的状态，因为我使用的函数是可接受的但(我认为)不一致(我还尝试了 Hamming 和 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); // 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/
不确定下面建议的第一个更改可能会改变多少时间，但我很确定您需要进行第二个更改。
第一个变化
通过对比代码，你会发现这个函数
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 循环中做了一些奇怪的事情。
失败一次后，将最大深度(限制)设置为无穷大。基本上，第一次迭代，你尝试找到一个与你的启发式一样好的解决方案。然后你尝试找到任何解决方案。这不是迭代深化。
迭代深化意味着每次尝试时，都深入一点。
确实，查看 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 文件夹中。
关于java - Iterative Deepening A Star (IDA*) 解决 Java 中的 n-puzzle(滑动拼图)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12033252/