A* アルゴリズムとマンハッタン ヒューリスティックを使用して 8 パズルを解くプログラムを作成しましたが、プログラムはすべての入力に対して、また正しい出力、状態数に対しても正しく動作していないようです (移動の最小数)。展開されたサイズは、通常よりもはるかに大きくなります。
私のプログラムには 4 つのクラスがあります。
Game State: ゲームを表す
AStar: AStar アルゴリズム
AStarList: オープン リストとクローズ リストを表すデータ構造。(私のデータ構造はパフォーマンスの面で非常に悪いことを知っています。後で改善します
)
コードの一部を次に示します。
(コード サイズが大きくて申し訳ありません。私の AStar アルゴリズムに何か問題があるのではないかと思います。そのため、おそらく他のクラスを実行する必要はありません。)
星
public class AStar {
public static void solve(GameState gameStateToSolve) {
AStarList openList = new AStarList();
AStarList closedlList = new AStarList();
openList.add(gameStateToSolve);
int iteration = 1;
while (!openList.isEmpty()) {
System.out.println((iteration++));
GameState current = openList.getNext();
if (current.isGoalState()) {
current.print();
return;
}
GameState children[] = current.expand();
closedlList.addWithoutDuplication(current);
for (int i = 0; i < children.length; i++) {
boolean presentInOpenList = openList.isPresent(children[i]);
boolean presentInClosedList = closedlList.isPresent(children[i]);
if (!presentInOpenList && !presentInClosedList) {
openList.add(children[i]);
} else if (presentInClosedList && !presentInOpenList) {
if (closedlList.getCostOf(children[i]) > children[i].getMovementsCount()) {
closedlList.remove(children[i]);
openList.add(children[i]);
}
} else if (presentInOpenList && !presentInClosedList) {
if (openList.getCostOf(children[i]) > children[i].getMovementsCount()) {
openList.remove(children[i]);
openList.add(children[i]);
}
}
}
}
}
public static void main(String[] args) {
solve(new GameState(
new int[]{0,7,3,1,8,6,5,4,2},
new ArrayList<Integer>(),
GameState.NUMBERS_ARRAY));
}
}
Aスターリスト
public class AStarList {
ArrayList<GameState> list;
public AStarList() {
list = new ArrayList<>();
}
public boolean isPresent(GameState gameState) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals(gameState)) {
return true;
}
}
return false;
}
public void remove(GameState gameState) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals(gameState)) {
list.remove(i);
}
}
}
public void add(GameState gameState) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).manhattanDistance() > gameState.manhattanDistance()) {
list.add(i, gameState);
return;
}
}
list.add(gameState);
}
public void addWithoutDuplication(GameState gameState) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals(gameState)) {
list.remove(i);
list.add(i, gameState);
}
if (list.get(i).manhattanDistance() > gameState.manhattanDistance()) {
list.add(i, gameState);
return;
}
}
list.add(gameState);
}
public boolean isEmpty() {
return list.isEmpty();
}
public GameState getNext() {
return list.remove(0);
}
public int getHeuristicOf(GameState gameState) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals(gameState)) {
return list.get(i).manhattanDistance();
}
}
throw new RuntimeException();
}
public int getCostOf(GameState gameState) {
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals(gameState)) {
return list.get(i).getMovementsCount();
}
}
return -1;
}
}
ゲーム状態
public final class GameState1 {
public GameState1(GameState gameState) {
// creates a GameState exactly similar to the one passed
}
public GameState1(int[] array, ArrayList<Integer> movements, int type) {
//...
}
public int getMovementsCount() {
// returns number of movements made so far
}
public int[] getPositionsArrayOf(int[] numbersArray) {
//...
}
public int[] getNumbersArrayOf(int[] positionsArray) {
//...
}
public void move(int direction) {
//...
}
public GameState getStateOnMovement(int direction) {
//...
}
public boolean movePossible(int direction) {
//...
}
public int[] getPossibleMovements() {
//...
}
public GameState[] expand() {
//..
}
public boolean equals(GameState anotherState) {
// returns true if the board state is the same
}
public boolean isGoalState() {
// returns true if it is goal state
}
public void print() {
//...
}
public int numberOfInversions() {
// returns number of inversions
}
public boolean isSolvable() {
//returns true if solvable
}
public int manhattanDistance() {
// returns manhattan distance
}
}
コードサイズが大きくてすみません。私の AStar アルゴリズムに何か問題があると思われます。S0、おそらく他のクラスを通過する必要はありません。