A* でn パズル問題を解くことができるプログラムを実装しました。状態のスペースが大きすぎるため、プリコンパイルできず、実行時に可能な状態を計算する必要があります。このように、A* は 3 パズルでは問題なく機能しますが、4 パズルでは時間がかかりすぎる可能性があります。線形競合で調整されたマンハッタン距離を使用すると、最適解が約 25 回の移動を必要とする場合でも高速であり、約 35 回で 10 秒、40 回で 180 秒かかります。私はまだそれ以上試していません。
これは、許容できる関数を使用しているため、すべての訪問済み状態を保持する必要があるためだと思いますが、一貫性がありません (ハミング距離とガシュニッヒ距離などでも試しました)。ソリューションの空間はグラフであるため、ヒューリスティックも一貫している必要があります。そうしないと、アルゴリズムがループしたり、最適でなくなったりする可能性があります。そのため、訪問したすべてのノードを保持しています (「AI: A modern approach」という本にも書かれています)。とにかく、このストレージはまったく遅くなりません。速度が低下するのは、訪問するノードのキューを順序付けたままにすることです。
そこで、私が見たように、このストレージを必要としない 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;
}