В настоящее время я пишу реализацию алгоритма A * для решения 8puzzle.Я очень много прогрессировал, но мой алгоритм, похоже, застрял в бесконечном процессе, и я действительно не вижу, где я допустил ошибки.
Вот мой код:
Доска.Java:
public class Board {
private int currentState[][] = new int[3][3];
private int nbMoves; // variable for the cost of the current board
private int manhattanDistance;
private int f = manhattanDistance + nbMoves;
public Board() {}
public Board(int b1[][]) {
this.currentState = b1;
}
public int getValue(int x, int y) {
return currentState[x][y];
}
public void setValue(int n, int x, int y) {
currentState[x][y] = n;
}
public int getNbMoves() {
return nbMoves;
}
public void setNbMoves(int n) {
nbMoves = n;
}
// Function to get the x coordinate of the specified value n
public int getX(int n) {
int posX = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (currentState[i][j] == n) {
posX = i;
break;
}
}
}
return posX;
}
// Function to get the y coordinate of the specified value n
public int getY(int n) {
int posY = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (currentState[i][j] == n) {
posY = j;
break;
}
}
}
return posY;
}
// Function to get and stock the Coordinate of the desired value in a 1D array coord
// We will use it to get the coordinates of the 0 tile.
public void getCoordinate(int coord[], int n) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (currentState[i][j] == n) {
coord[0] = i;
coord[1] = j;
break;
}
}
}
}
// Function to get the current state of the board
public void getCurrentState(int state[][]) {
state = this.currentState;
}
// Function to test if 2 boards are the same
public boolean equals(int b[][]) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.currentState[i][j] != b[i][j]) {
return false;
}
}
}
return true;
}
public void setManhattanDistance() {
int md = 0;
for (int x = 0; x < 3; x++) {
for (int y = 0; y < 3; y++) {
int value = currentState[x][y]; // Contain the value of the tile
// Then we calculate the Manhattan Distance for each tile,
// except for the 0 tile.
if (value != 0) {
int expected_X = (value - 1) / 3; // expected vertical coordinate
int expected_Y = (value - 1) % 3; // expected horizontal coordinate
int true_x = x - expected_X;
int true_y = y - expected_Y;
md += Math.abs(true_x) + Math.abs(true_y);
}
}
}
manhattanDistance = md;
}
// Function to set the f() value
public int getF() {
return f;
}
// Function for printing the current state of board
public void print() {
for (int i = 0; i<3; i++) {
for (int j = 0; j<3; j++) {
System.out.print(currentState[i][j] + " ");
}
System.out.println("");
}
}
}
BFSearch.java:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class BFSearch {
private ArrayList<Board> closedlist = new ArrayList<Board>();
private ArrayList<Board> openlist = new ArrayList<Board>();
private ArrayList<Board> getChildren = new ArrayList<Board>();
private Board currentState,goalState = new Board();
public BFSearch(int start[][], int goal[][]) {
currentState = new Board(start);
goalState = new Board(goal);
}
// Function to get every children possible for the current state of the board
// A board can have a maximum of 4 children (1 for every direction)
public ArrayList<Board> children(Board currentState) {
Board newState = new Board();
ArrayList<Board> children = new ArrayList<Board>();
Pos p = new Pos();
newState = p.Up(currentState);
// If the move is possible, then we increment by 1 the number of moves (to calculate f() value)
// we calculate it's manhattan distance,
// and we add it to the list of children
if (newState != null) {
newState.setNbMoves(currentState.getNbMoves() + 1);
newState.setManhattanDistance();
children.add(newState);
}
newState = p.Down(currentState);
// If the move is possible, then we increment by 1 the number of moves (to calculate f() value)
// we calculate it's manhattan distance,
// and we add it to the list of children
if (newState != null) {
newState.setNbMoves(currentState.getNbMoves() + 1);
newState.setManhattanDistance();
children.add(newState);
}
newState = p.Left(currentState);
// If the move is possible, then we increment by 1 the number of moves (to calculate f() value)
// we calculate it's manhattan distance,
// and we add it to the list of children
if (newState != null) {
newState.setNbMoves(currentState.getNbMoves() + 1);
newState.setManhattanDistance();
children.add(newState);
}
newState = p.Right(currentState);
// If the move is possible, then we increment by 1 the number of moves (to calculate f() value)
// we calculate it's manhattan distance,
// and we add it to the list of children
if (newState != null) {
newState.setNbMoves(currentState.getNbMoves() + 1);
newState.setManhattanDistance();
children.add(newState);
}
return children;
}
public void solve() {
boolean solved = false;
int movecount = 0;
currentState.setNbMoves(0);
// We add the currentState of the board to the open list
openlist.add(currentState);
// While we don't have a solution
while (!solved) {
currentState = openlist.get(0);
// If we arrived at the goal state then we print it and stop the program
if (currentState.equals(goalState)) {
currentState.print();
solved = true;
}
// We get the list of possible children
getChildren = children(currentState);
// We move the First board of the open list to the closed list
closedlist.add(currentState);
openlist.remove(0);
// Need to sort the children depending on their f() value
// I declared an anonymous comparator for that.
Collections.sort(getChildren, new Comparator<Board>() {
@Override
public int compare(Board b1, Board b2) {
Integer f1 = b1.getF();
Integer f2 = b2.getF();
return f1.compareTo(f2);
}
});
// Then, we add the children to the open list
for (Board b : getChildren) {
openlist.add(b);
}
movecount++;
}
// We print every step of the solution
for (Board bd : closedlist) {
bd.print();
}
// We print the number of move required
System.out.println("Number of move required : " + movecount);
}
}
Затем мой основной для выполнения программы, EightPuzzle.java:
public class EightPuzzle {
public static void main(String[] args) {
int startState[][] = {{1,2,3}, {4,5,6}, {7,8,0}};
int goalState[][] = {{1,2,3}, {4,5,6}, {7,8,0}};
BFSearch bfs = new BFSearch(startState, goalState);
System.out.println("Researching the solution...");
bfs.solve();
}
}
У меня есть другие классы(Pos.java), которые в основном выполняют движения для плиток (например, двигаются вверх, меняются местами и т. Д.), Но я не думаю, что проблема в этом.
Когда я выполняю свою программу,есть только печать «Исследование решения ...», тогда ничего, даже если я буду ждать много времени.Даже когда начальное состояние и состояние цели совпадают ... (как вы видите в основной программе)
Если у вас есть какие-либо идеи, большое спасибо!