Задачи оптимизации Алгоритм A*
Я пытаюсь реализовать алгоритм решения A* для решения скользящих головоломок с использованием расстояний Манхэттен / Хэмминга. Этот алгоритм должен уметь решать N x N скользящих головоломок и возвращать «лучшие» ходы для ее решения. Мой текущий алгоритм позволяет решать платы 3x3 и простые платы 4x4, но когда я пробую более сложные платы, я сталкиваюсь с проблемами памяти (>8 ГБ). Я попытался оптимизировать свой код, но ничего не работает.
Я ищу способы оптимизировать использование памяти.
Об алгоритме: этот алгоритм берет конкретную доску (см. Пример) и возвращает шаги, необходимые для ее решения, используя наименьшее количество возможных ходов.
Вход:
1 3
4 2 5
7 8 6
Выход:
1 3
4 2 5
7 8 6
1 3
4 2 5
7 8 6
1 2 3
4 5
7 8 6
1 2 3
4 5
7 8 6
1 2 3
4 5 6
7 8
Мой код:
Решатель:
import java.util.*;
import libpract.PriorityFunc;
import java.lang.instrument.Instrumentation;
public class Solver {
private final Status finalStatus;
private Stack<Board> boards;
private static final int MAXTIME = 300000;
private int moves =0;
/**
* Finds a solution to the initial board.
*
* @param initial is a solvable Board
* @param priority is either PriorityFunc.HAMMING or PriorityFunc.MANHATTAN
*/
public Solver(Board initial, PriorityFunc priority) {
long timeMS = System.currentTimeMillis();
if (initial == null) {
throw new IllegalArgumentException("The initial board is null");
}
if (!initial.isSolvable()) {
throw new IllegalArgumentException("The given board is unsolvable");
}
if (priority == PriorityFunc.HAMMING) {
PriorityQueue<Status> priorityQueue = new PriorityQueue<>();
Set<Board> previousBoards = new HashSet<>();
Board dequeuedBoard = initial;
Status status = new Status(initial, 0, null);
Iterable<Board> boards;
priorityQueue.add(status);
while (!dequeuedBoard.isFinished()) {
if (System.currentTimeMillis() - timeMS > MAXTIME) {
throw new RuntimeException("This board is taking longer than " + MAXTIME + " ms to solve using HAMMING");
}
boards = dequeuedBoard.neighbors();
moves++;
for (Board board : boards) {
if (!previousBoards.contains(board)) {
priorityQueue.add(new Status(board, moves + board.hamming(), status));
previousBoards.add(board);
}
}
status = priorityQueue.poll();
assert status != null;
dequeuedBoard = status.currentBoard;
}
finalStatus = status;
} else if (priority == PriorityFunc.MANHATTAN) {
if (System.currentTimeMillis() - timeMS > MAXTIME) {
throw new RuntimeException("This board is taking longer than " + MAXTIME + " ms to solve using MANHATTAN");
}
PriorityQueue<Status> priorityQueue = new PriorityQueue<>();
Set<Board> previousBoards = new HashSet<>();
Board dequeuedBoard = initial;
Board prev = null;
Status status = new Status(initial, 0, null);
Iterable<Board> boards;
while (!dequeuedBoard.isFinished()) {
boards = dequeuedBoard.neighbors();
moves++;
for (Board board : boards) {
if (!previousBoards.contains(board)) {
priorityQueue.add(new Status(board, moves + board.manhattan(), status));
}
}
previousBoards.add(prev);
prev = dequeuedBoard;
status = priorityQueue.poll();
assert status != null;
dequeuedBoard = status.currentBoard;
}
finalStatus = status;
} else {
throw new IllegalArgumentException("Priority function not supported");
}
}
/**
* Returns a List of board positions as the solution. It should contain the initial
* Board as well as the solution (if these are equal only one Board is returned).
*/
public List<Board> solution() {
if (boards != null) return boards;
boards = new Stack<>();
Status pointer = finalStatus;
while (pointer != null) {
boards.push(pointer.currentBoard);
pointer = pointer.prevStatus;
}
Collections.reverse(boards);
return boards;
}
private static class Status implements Comparable<Status> {
protected Board currentBoard;
protected int priority;
protected Status prevStatus;
/**
* Initialises a class Status which stores the current board, the priority and the previous status.
*
* @param currentBoard is the current board
* @param priority is an integer greater than or equal to zero
* @param prevStatus is the previous status
*/
public Status(Board currentBoard, int priority, Status prevStatus) {
this.currentBoard = currentBoard;
this.priority = priority;
this.prevStatus = prevStatus;
}
/**
* Returns an integer depending on the priority of this object and the other given object.
*
* @param otherStatus is the object to be compared
* @return a negative integer, zero, or a positive integer as this object has a higher, equal, greater priority
* than the specified object.
*/
@Override
public int compareTo(Status otherStatus) {
return Integer.compare(this.priority, otherStatus.priority);
}
}
}
Доска:
import java.util.Collection;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class Board {
private final int[][] tiles;
private int[] zeroLocation;
private final int[][] goal;
/**
* Constructs a valid board from an N-by-N array of tiles
*
* @param tiles is an N-by-N array of positive (including 0) integers in which every integer is unique
* and less than N*N.
*/
// construct a board from an N-by-N array of tiles
public Board(int[][] tiles) {
this.tiles = new int[tiles.length][tiles[0].length];
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
this.tiles[i][j] = tiles[i][j];
if (tiles[i][j] == 0) {
zeroLocation = new int[]{i, j};
}
}
}
isValidBoard();
goal = new int[tiles.length][tiles.length];
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
goal[i][j] = j + 1 + i* tiles.length;
}
}
goal[tiles.length-1][tiles.length-1] = 0;
}
/**
* Returns the Hamming dislocations of this board, meaning the amount of tiles in a wrong solution.
*
* @return is an integer greater than or equal to zero
*/
// return number of blocks out of place
public int hamming() {
int count = 0;
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
if (tiles[i][j] != i * tiles.length + j + 1 && tiles[i][j] != 0) {
count += 1;
}
}
}
return count;
}
/**
* Returns the Manhattan dislocations of this board, meaning the sum of the distances of the tiles and
* their correct positions.
*
* @return is an integer greater than or equal to zero
*/
public int manhattan() {
int count = 0;
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
int realX = (tiles[i][j] - 1) % tiles.length;
int realY = (tiles[i][j] - 1) / tiles.length;
if (tiles[i][j] != 0) {
count += Math.abs(realX - j) + Math.abs(realY - i);
}
}
}
return count;
}
/**
* Returns whether this board is equal to the given board.
*/
@Override
public boolean equals(Object y) {
if (!(y instanceof Board))
return false;
Board other = (Board) y;
return Arrays.deepEquals(tiles, other.tiles);
}
// Since we override equals(), we must also override hashCode(). When two objects are
// equal according to equals() they must return the same hashCode. More info:
// - http://stackoverflow.com/questions/27581/what-issues-should-be-considered-when-overriding-equals-and-hashcode-in-java/27609#27609
// - http://www.ibm.com/developerworks/library/j-jtp05273/
@Override
public int hashCode() {
return Arrays.deepHashCode(tiles);
}
/**
* Returns a collection of all the neighboring boards, meaning all the boards that can be created by moving one tile.
*
* @return a collection of boards
*/
public Collection<Board> neighbors() {
Set<Board> collection = new HashSet<>();
if (zeroLocation[0] - 1 >= 0) {
int[][] newTiles = new int[tiles.length][tiles.length];
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
newTiles[i][j] = tiles.clone()[i][j];
}
}
int temp = newTiles[zeroLocation[0] - 1][zeroLocation[1]];
newTiles[zeroLocation[0] - 1][zeroLocation[1]] = 0;
newTiles[zeroLocation[0]][zeroLocation[1]] = temp;
collection.add(new Board(newTiles));
}
if (zeroLocation[0] + 1 < tiles.length) {
int[][] newTiles = new int[tiles.length][tiles.length];
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
newTiles[i][j] = tiles.clone()[i][j];
}
}
int temp = newTiles[zeroLocation[0] + 1][zeroLocation[1]];
newTiles[zeroLocation[0] + 1][zeroLocation[1]] = 0;
newTiles[zeroLocation[0]][zeroLocation[1]] = temp;
collection.add(new Board(newTiles));
}
if (zeroLocation[1] - 1 >= 0) {
int[][] newTiles = new int[tiles.length][tiles.length];
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
newTiles[i][j] = tiles.clone()[i][j];
}
}
int temp = newTiles[zeroLocation[0]][zeroLocation[1] - 1];
newTiles[zeroLocation[0]][zeroLocation[1] - 1] = 0;
newTiles[zeroLocation[0]][zeroLocation[1]] = temp;
collection.add(new Board(newTiles));
}
if (zeroLocation[1] + 1 < tiles.length) {
int[][] newTiles = new int[tiles.length][tiles.length];
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
newTiles[i][j] = tiles.clone()[i][j];
}
}
int temp = newTiles[zeroLocation[0]][zeroLocation[1] + 1];
newTiles[zeroLocation[0]][zeroLocation[1] + 1] = 0;
newTiles[zeroLocation[0]][zeroLocation[1]] = temp;
collection.add(new Board(newTiles));
}
return collection;
}
/**
* Returns a string representation of this board.
* E.g. tiles = {{1, 2}, {3, 0}} returns "1 2\n3 \n"
*/
public String toString() {
StringBuilder string = new StringBuilder();
for (int[] tileRow : tiles) {
for (int tile : tileRow) {
if (tile == 0) {
string.append(" ");
} else {
string.append(tile);
}
string.append(" ");
}
string.deleteCharAt(string.length() - 1);
string.append("\n");
}
return string.toString();
}
/**
* Returns whether this board is solvable.
*/
public boolean isSolvable() {
int inversions = 0;
for (int i = 0; i < tiles.length * tiles.length; i++) {
int currentRow = i / tiles.length;
int currentCol = i % tiles.length;
for (int j = i; j < tiles.length * tiles.length; j++) {
int row = j / tiles.length;
int col = j % tiles.length;
if (tiles[row][col] != 0 && tiles[row][col] < tiles[currentRow][currentCol]) {
inversions++;
}
}
}
if (tiles.length % 2 != 0 && inversions % 2 != 0) return false;
return tiles.length % 2 != 0 || (inversions + this.zeroLocation[0]) % 2 != 0;
}
public boolean isFinished() {
for (int i = 0; i < tiles.length; i++) {
for (int j = 0; j < tiles.length; j++) {
if (tiles[i][j] != goal[i][j])
return false;
}
}
return true;
}
/**
* Throws a IllegalArgumentException when this board is invalid.
* A board is valid if all conditions are met: * The board is square
* * All tiles are unique
* * All tiles are less than N*N (with N = the length of the board)
*/
private void isValidBoard() {
if (tiles.length != tiles[0].length) {
throw new IllegalArgumentException("The given board has to be a square");
}
Set<Integer> prevNumbers = new HashSet<>();
for (int[] tileRow : tiles) {
for (int tile : tileRow) {
if (tile >= tiles.length * tiles.length || prevNumbers.contains(tile)) {
throw new IllegalArgumentException("The given board is invalid");
}
prevNumbers.add(tile);
}
}
}
}
заранее спасибо