我已经编写了一个程序来使用 A* 算法和曼哈顿启发式解决 8 难题，但是对于所有输入，甚至对于正确的输出，状态数，程序似乎都无法正常工作（最小移动次数）扩展的比它通常应该的大得多。
我的程序有四个类：
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));
}
}
明星名单
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，您可能不需要通过其他课程。