ラッシュアブソーバーが無限ループに陥っていても意味がありません

Question

私は、JavaでRush Hourソルバーを書いています。これは設定hereを解くことを目的としています。しかし、そのページの最も単純なパズルであっても、ソルバーは無限に実行され、最終的にはメモリ不足になります。私は各ボード状態から発生する可能性のあるすべての動き（自分自身を繰り返さないことを保証するためにHashSetを使用して）、各状態をそこに持っている動きにマッピングするための幅広い最初の検索を使用しているので、後でそれらを通して。

私は自分自身を思いついたより些細なパズルで試してみましたが、それを解決することはできますが（ゆっくりですが）。

私はこの問題にどのように近づいているのか、まったく間違っていますか？関連するクラスのコードも必要に応じて置くことができますが、かなり徹底的にテストしましたが、問題は次のコードのどこかにあると確信しています。私の腸は、それがハッシュセットと関係していると私は自分自身を繰り返さないことを確認している（キューのサイズは定期的に十万に達するので）と言います。

提案がありますか？ここでは、要求されたよう

// Start at the original configuration 
    queue.add(originalBoard); 

    // We add this to our map, but getting here did not require a move, so we use 
    // a dummy move as a placeholder move 
    previous.put(originalBoard, new Move(-1, -1, "up")); 

    // Breadth first search through all possible configurations 
    while(!queue.isEmpty()) { 
     // Dequeue next board and make sure it is unique 
     Board currentBoard = queue.poll(); 
     if (currentBoard == null)   continue; 
     if (seen.contains(currentBoard)) continue; 
     seen.add(currentBoard); 

     // Check if we've won 
     if (currentBoard.hasWon()) { 
      System.out.println("We won!"); 
      currentBoard.renderBoard(); 
      return solved(currentBoard); 
     } 

     // Get a list of all possible moves for the current board state 
     ArrayList<Move> possibleMoves = currentBoard.allPossibleMoves(); 

     // Check if one of these moves is the winning move 
     for (Move move : possibleMoves) { 
      Board newBoard = move.execute(currentBoard); 

      // We don't need to enqueue boards we've already seen 
      if (seen.contains(newBoard)) continue; 
      queue.add(newBoard); 

      // Map this board to the move that got it there 
      previous.put(newBoard, move); 
     } 
    } 

は（彼らはクラスレベルの変数です）HashSetの私のinitialisationsです：

private static HashSet<Board> seen = new HashSet<>(); 

そして、私のBoard.equals（）メソッド：

@Override 
public boolean equals (Object b) { 
    Board otherBoard = (Board) b; 
    boolean equal = false; 
    if (this.M == otherBoard.getM() && this.N == otherBoard.getN()) { 
     equal = true; 

     // Each board has an ArrayList of Car objects, and boards are only 
     // considered equal if they contain the exact same cars 
     for (Car car : this.cars) { 
      if (otherBoard.getCar(car.getPosition()) == null) { 
       equal = false; 
      } 
     } 
    } 
    System.out.println(equal); 
    return equal; 
} 

Answer 1

ますデフォルトのObjectベースのバージョンをオーバーライドするには、Board.hashCode()を実装する必要があります。これにより、コントラクトごとに等しい2つの等しいBoardオブジェクトが同じハッシュコードを持つようになります。あなたがしない場合、あなたのseenセットは実際にあなたのために何かを達成するわけではありません。

別の問題では、ボードの車をチェックしている方法が完全ではないと思われます。それは、私はそれがないと思うように動作している場合、それは、これら二つのボードが等しくなるように検討する：車

...... 
.**.*. 
....*. 
.*.... 
.*.**. 
...... 

...... 
.*..** 
.*.... 
...... 
.**.*. 
....*.