nパズルの問題を解決するプログラムを実装しようとしています。
タイルを表す行列によって特徴付けられる問題の状態を持つJavaでの簡単な実装を作成しました。また、開始状態を示すすべての状態のグラフを自動生成することもできます。グラフでは、BFSを実行して、目標状態へのパスを見つけることができます。
しかし、問題は、メモリが不足していて、グラフ全体を作成することさえできないことです。2x2タイルで試してみましたが、機能します。また、3x3もあります（開始状態とグラフ内のノード数によって異なります）。しかし、一般的にこの方法は適切ではありません。
そこで、検索中に実行時にノードを生成してみました。動作しますが、遅いです（数分経ってもまだ終了しておらず、プログラムを終了する場合があります）。
ところで：私は開始状態として解決可能な構成のみを与え、重複した状態を作成しません。
そのため、グラフを作成できません。これが私の主な問題につながります。A*アルゴリズムを実装する必要があり、パスコスト（つまり、各ノードの開始状態からの距離）が必要ですが、実行時に計算できないと思います。グラフ全体が必要ですよね？A *はグラフのBFS探索に従わないため、各ノードの距離を推定する方法がわかりません。したがって、A*検索を実行する方法がわかりません。
なにか提案を？
編集
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'ssolveには。がありSortedSetます。要素（States）は、に従ってソートされます。これはComparator1、を計算しますf(n) = g(n) + h(n)。ここg(n)で、はパスコストでありh(n)、はヒューリスティック（誤って配置されたタイルの数）です。
-開始構成を示し、すべての後継者を探します。
-サクセサがまだアクセスされていない場合（つまり、グローバルセットにない場合States）、キューとに追加しStates、現在の状態を親およびparent's path + 1パスコストとして設定します。
-デキューして繰り返します。
次の理由で機能するはず
です。-訪問したすべての状態を保持するので、ループしません。
-また、現在のノードの後継をすぐに保存するので、無駄なエッジはありません。例：AIからBとCに移動でき、BIからもCに移動できる場合、エッジB-> Cは存在しません（パスコストは各エッジで1であり、A->BはAよりも安いため） -> B-> C）。-A *に従って
、パスを最小で拡張することを選択するたびに。
しかし、それは機能しません。または、少なくとも、数分経っても解決策を見つけることができません（この場合はかなりの時間がかかると思います）。
A *を実行する前にツリー構造を作成しようとすると、それを構築するためのメモリが不足します。
編集2
これが私のヒューリスティック関数です：f(n)
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;
}
編集3
少しエラーがありました。修正したところ、A*が機能するようになりました。または、少なくとも、3x3の場合、700回の反復で最適なソリューションが見つかった場合。4x4の場合はまだ遅すぎます。IDA *を試してみますが、1つの質問です。A*を使用して解決策を見つけるのにどのくらい時間がかかりますか？分？時間？私はそれを10分間放置しましたが、それは終わりませんでした。