我正在使用A * Search创建一个8解谜游戏。
我相信错误是在下面的我的Search.class中。但是我还附上了其他两个类，以防万一。
搜索类别
public class Search {
/**
* Active instance of <code>Board</code>
*/
private Board board;
/**
* Set of fringes
*/
private ArrayList<Integer> fringes = new ArrayList<>();
/**
* Current nodes
*/
private int node;
/**
* Map linking tiles(by number) to the goal state
*/
private static Map<Integer, int[]> goalStates = new HashMap<>();
/**
* g value
*/
private int g = 0;
/**
* Is the search complete
*/
private boolean searchComplete = false;
/**
* The last move
*/
private int lastMove = 0;
/**
* Fills goalStates Map
*/
static {
goalStates.put(1, new int[]{0, 0});
goalStates.put(2, new int[]{1, 0});
goalStates.put(3, new int[]{2, 0});
goalStates.put(4, new int[]{0, 1});
goalStates.put(5, new int[]{1, 1});
goalStates.put(6, new int[]{2, 1});
goalStates.put(7, new int[]{0, 2});
goalStates.put(8, new int[]{1, 2});
};
/**
* Construct the <code>Search</code> instance
*
* @param board
* The board
*/
public Search(Board board){
this.board = board;
searchAlgo();
}
/**
* Main search algorithm
*/
private void searchAlgo() {
ArrayList<Integer> nodeFValues = new ArrayList();
ArrayList<Tile> nodeTiles = new ArrayList<>();
/* Stores all the f values for the nodes in the fringe */
for(Tile tile: board.checkNeighbouringTiles(board.findTile(0))){
if(lastMove != tile.getNumber()) {
nodeFValues.add(node(tile));
nodeTiles.add(tile);
}
}
/* Gets the minimum fringe */
int minFValueIndex = nodeFValues.indexOf(Collections.min(nodeFValues));
/* If there are no tiles out of place then you are at goal state */
if (tilesOutOfPlaceHeuristic(board) == 0){
System.out.println("Complete");
board.print();
searchComplete = true;
return;
}
/* Goes to the node with the lowest f value. */
board.moveTile(board.findTile(0),
nodeTiles.get(minFValueIndex).getXPosition(),
nodeTiles.get(minFValueIndex).getYPosition());
lastMove = nodeTiles.get(minFValueIndex).getNumber();
g += 1;
/* If search is incomplete, it recursively calls itself */
if(!searchComplete)
searchAlgo();
}
/**
* Represents each node
*
* @param tile
* The tile to be moved in the node
* @return
* f value
*/
private int node(Tile tile){
/** Initialises new board object */
Board nodeBoard = new Board(board.getNumbers());
nodeBoard.moveTile(nodeBoard.findTile(0), tile.getXPosition(), tile.getYPosition());
int h1 = tilesOutOfPlaceHeuristic(nodeBoard);
int h2 = manhattanHeuristic(nodeBoard);
int f = g + h2;
return f;
}
/**
* Calculates horizontal and vertical distances of tiles from their proper places.
* Admissible Heuristic.
*
* @return
* Sum of horizontal and vertical distances of tiles from their proper places.
*/
private int manhattanHeuristic(Board board) {
int sum = 0;
ArrayList<Tile> tiles = board.getTiles();
int[] goalState;
int goalX;
int goalY;
int differenceX;
int differenceY;
for(Tile tile: tiles){
if(tile.getNumber() != 0) {
goalState = goalStates.get(tile.getNumber());
goalX = goalState[0];
goalY = goalState[1];
differenceX = goalX - tile.getXPosition();
differenceY = goalY - tile.getYPosition();
sum += Math.abs(differenceX) + Math.abs(differenceY);
}
}
return sum;
}
/**
* Calculates number of tiles out of place. Admissible Heuristic.
*
* @return
* Number of tiles out of place
*/
private int tilesOutOfPlaceHeuristic(Board board) {
int tilesInWrongPlace = 0;
ArrayList<Tile> tiles = board.getTiles();
for(Tile tile: tiles){
if(tile.getNumber() != 0) {
if ((tile.getXPosition() != goalStates.get(tile.getNumber())[0])
|| (tile.getYPosition() != goalStates.get(tile.getNumber())[1])){
tilesInWrongPlace += 1;
}
}
}
return tilesInWrongPlace;
}
}
董事会级别：
public class Board {
/**
* Numbers in the board
*/
private int[][] numbers = {};
private int rows = 3;
private int columns = 3;
/**
* The board
*/
private ArrayList<Tile> board = new ArrayList();
/**
* Constructs a <code>Board</code> instance and fills
* it with <code>Tile</code> instances
*/
public Board(int[][] numbers) {
this.numbers = numbers;
int j = 0;
for(int[] row: numbers){
for (int i = 0; i < row.length; i++) {
board.add(new Tile(row[i], i, j));
}
j += 1;
}
}
/**
* @return
* Numbers for board
*/
public int[][] getNumbers(){
return numbers;
}
/**
* @return
* Tiles in board
*/
public ArrayList<Tile> getTiles(){
return board;
}
/**
* Moves the specified <code>Tile</code> to the specified position.
* Swaps positions with <code>Tile</code> at that position.
*
* @param tile
* <code>Tile</code> to be moved
* @param x
* The horizontal position you want <code>Tile</code> to move to.
* @param y
* The vertical position you want <code>Tile</code> to move to.
*/
public void moveTile(Tile tile, int x, int y) {
int _x = tile.getXPosition();
int _y = tile.getYPosition();
Tile tileToBeMoved = tile;
Tile tileAtPosition;
if(findTile(x, y) != null) {
tileAtPosition = findTile(x, y);
} else {
System.out.println("No tile exists at that position");
return;
}
/* Move tileToBeMoved to chosen position */
tileToBeMoved.setPosition(x, y);
/* swap*/
tileAtPosition.setPosition(_x, _y);
}
/**
* Checks if neighbouring <code>Tile</code>s exist, if so, it returns the <code>Tile</code>
*
* @param tile
* Current <code>Tile</code>
* @return
* Set of <code>Tile</code>s
*/
public ArrayList<Tile> checkNeighbouringTiles(Tile tile){
ArrayList<Tile> neighbouringTiles = new ArrayList<>();
int x = tile.getXPosition();
int y = tile.getYPosition();
/* Neighbour to the right of tile */
int rightNeighbourX = x + 1;
int rightNeighbourY = y;
/* Neighbour to the left of tile */
int leftNeighbourX = x - 1;
int leftNeighbourY = y;
/* Neighbour to the top of tile */
int topNeighbourX = x;
int topNeighbourY = y - 1;
/* Neighbour to the bottom of tile */
int bottomNeighbourX = x;
int bottomNeighbourY = y + 1;
for(Tile t: board) {
if ((t.getXPosition() == rightNeighbourX) && (t.getYPosition() == rightNeighbourY)) {
neighbouringTiles.add(t);
} else if((t.getXPosition() == leftNeighbourX) && (t.getYPosition() == leftNeighbourY)){
neighbouringTiles.add(t);
} else if((t.getXPosition() == topNeighbourX) && (t.getYPosition() == topNeighbourY)){
neighbouringTiles.add(t);
} else if((t.getXPosition() == bottomNeighbourX) && (t.getYPosition() == bottomNeighbourY)){
neighbouringTiles.add(t);
}
}
return neighbouringTiles;
}
/**
* Finds a <code>Tile</code> with matching position
*
* @param x
* The horizontal position
* @param y
* The vertical position
* @return
* matching <code>Tile</code>
*/
public Tile findTile(int x, int y){
for(Tile t: board) {
if(t.getXPosition() == x && t.getYPosition() == y)
return t;
}
return null;
}
/**
* Finds a <code>Tile</code> with matching number
*
* @param number
* The number on the <code>Tile</code>
* @return
* matching <code>Tile</code>
*/
public Tile findTile(int number){
for(Tile t: board) {
if(t.getNumber() == number)
return t;
}
return null;
}
/**
*Prints the board
*/
public void print() {
System.out.println("*=====*");
for(int j = 0; j < rows; j++){
System.out.print("||");
for(int i = 0; i < columns; i++){
if(findTile(i, j) != null){
System.out.print(findTile(i, j).getNumber());
}
}
System.out.println("||");
}
System.out.println("*=====*");
}
}
瓷砖类别：
public class Tile {
/**
* Number on Tile
*/
private int number;
/**
* Horizontal position of tile
*/
private int x;
/**
* Vertical position of tile
*/
private int y;
/**
* Constructs a <code>Tile</code> instance with a number and position.
*
* @param number
* The number for the <code>Tile</code>.
* @param x
* The Horizontal position for the <code>Tile</code>.
*/
public Tile(int number, int x, int y){
this.number = number;
this.x = x;
this.y = y;
}
/**
* @param x
* Horizontal position for the <code>Tile</code>
* @param y
* Vertical position for the <code>Tile</code>
*/
public void setPosition(int x, int y){
this.x = x;
this.y = y;
}
/**
* @return
* Current horizontal position of <code>Tile</code>
*/
public int getXPosition(){
return x;
}
/**
* @return
* Current vertical position of <code>Tile</code>
*/
public int getYPosition(){
return y;
}
/**
* @param number
* Number on Tile
*/
public void setNumber(int number){
this.number = number;
}
/**
* @return
* Current number on tile
*/
public int getNumber(){
return number;
}
}
主类：
public class Main {
public static void main(String[] args){
int[][] numbers = {
{1, 0, 4},
{3, 2, 6},
{7, 5, 8}
};
Board board = new Board(numbers);
Search search = new Search(board);
}
}
以下是堆栈跟踪：
Exception in thread "main" java.lang.StackOverflowError
at java.util.Arrays.copyOf(Arrays.java:3175)
at java.util.ArrayList.grow(ArrayList.java:246)
at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:220)
at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:212)
at java.util.ArrayList.add(ArrayList.java:443)
at Board.checkNeighbouringTiles(Board.java:138)
at Search.searchAlgo(Search.java:89)
请注意，在某些情况下没有错误，但提供了完整的答案（目标状态）。
最佳答案
在moveTile方法中，tileToBeMoved只是板上的Tile的副本。它需要在板上ArrayList中进行更新。您可能应该执行以下操作：
board.get(indexOf(tileToBeMoved)).setPosition(x, y);
board.get(indexOf(tileAtPosition)).setPosition(_x, _y);
否则，当您一遍又一遍地调用searchAlgo方法时，所有图块每次都将位于同一位置。
另外，请看一下如何初始化电路板以及如何计算f值。您需要考虑邻居何时已位于其正确位置：
第一遍：
0的邻居：1、4、2
F邻居的值：{1、0}，{4、4}，{2、1}
moveTile（0，0，0）;
新板：
{0，1，4}，
{3，2，6}，
{7，5，8}
第二遍：
0：1、3的邻居
F邻居的值：{1、2}，{3、5}
moveTile（0，0，1）;
新板：
{1，0，4}，
{3，2，6}，
{7，5，8}
看看发生了什么事？