Я проверял код на 4x4 головоломках. Он решал правильно головоломки, требующие до 14 шагов, но занял много времени. Я остановил 15-шаговую головоломку через 19 часов.
Чтобы ускорить код, я ввел метод hashCode() в State. Реализация hashCode() позволила мне изменить дорогостоящий тест if(IsPuzzleStateNew(allStates, state)), используя Set для visited и сделав isPuzzleStateNew и isPuzzleSame избыточными. Я также переработал isSolution, чтобы сделать его более универсальным c и быстрее.
Время резко изменилось, и головоломки до 16 шагов выполняются без проблем: Загадка
- 11 шагов снизилась с 13 секунд до 0,2 с * Загадка c
- 12 шагов снизилась с 56 секунд до 0,2 Загадка
- 13 шагов снизилась с 100 секунд до 0,2 Загадка
- 14 шагов снизилась с 340 секунд до 0,4 Загадка
- 15 шагов остановлена через 19 часов 0,6
- 16 шагов головоломки занимает 1,2
Тестирование головоломок, требующих 35 и 80 шагов до sh, по причинам, которые еще предстоит расследовать.
Следующее в mre , которое вы ожидаете опубликовать при запросе или ответе (вы можете скопировать и вставить код wntire в Program.java и запустить):
import java.awt.Point;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
public class Program {
public static int[][] solve, solved;
public static State solvedState, initialState;
static Solution solution;
public static void main(String[] args) throws IOException {
solved = new int[][] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 0 } };
solvedState = new State(solved);
//run various tests (consider writing a JUnit test)
int[] testcases = {1, 4, 10, 11, 12, 13, 14, 15, 16, 35, 80};
for(int test : testcases) {
System.out.println("########## "+test+" ##########");
testCase(test);
solution = new BFS(initialState, solvedState, "udlr");
long starttime = System.nanoTime();
String solutionString = solution.findSolution();
long elapsedTimeMS = (System.nanoTime() - starttime)/1000000;
if(test != solutionString.length()) {
System.err.println("Test "+ test + " wrong length "+ solutionString.length() );
}
int solutionLength = solutionString != "No solution found!" ? solutionString.length() : -1;
WriteResultState(solutionString);
WriteAdditionalInfo(
solutionLength,
solution.getNumberOfVisitedStates(),
solution.getNumberOfProcessedStates(),
solution.getMaxDepth(),
elapsedTimeMS
);
}
}
private static void testCase(int numberOfTestCase){
switch (numberOfTestCase){
case 1:
solve = new int[][] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 0, 15 } };
break;
default: case 4: //4 steps to solve
solve = new int[][] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 0, 10, 11, 12 }, { 9, 13, 14, 15 } };
break;
case 10: // 10 steps to solve
solve = new int[][] { { 1, 3, 4, 8 }, { 6, 2, 7, 0 }, { 5, 10, 11, 12 }, { 9, 13, 14, 15 } };
break;
case 11:// 11 steps to solve
solve = new int[][] { { 1, 3, 4, 8 }, { 6, 2, 0, 7 }, { 5, 10, 11, 12 }, { 9, 13, 14, 15 } };
break;
case 12:// 12 steps to solve
solve = new int[][] { { 1, 3, 4, 8 }, { 6, 0, 2, 7 }, { 5, 10, 11, 12 }, { 9, 13, 14, 15 } };
break;
case 13:// 13 steps to solve
solve = new int[][] { { 1, 3, 4, 8 }, { 6, 10, 2, 7 }, { 5, 0, 11, 12 }, { 9, 13, 14, 15 } };
break;
case 14:// 14 steps to solve
solve = new int[][] { { 5, 1, 2, 4 }, { 6, 10, 3, 7 }, { 0, 14, 12, 8 }, { 9, 13, 11, 15 } };
//solve = new int[][] { { 1, 7, 2, 4},{ 9, 5, 3, 0},{ 6, 10, 12, 8},{ 13, 14, 11, 15} };
break;
case 15: // 15 steps to solve
solve = new int[][] { { 1, 7, 2, 0},{ 9, 5, 3, 4},{ 6, 10, 12, 8},{ 13, 14, 11, 15} };
break;
case 16:// 16 steps to solve
solve = new int[][] { { 0, 2, 11, 3 }, { 1, 6, 7, 4 }, { 5, 9, 12, 8 }, { 13, 10, 14, 15 } };
break;
case 35:// 35 steps to solve
solve = new int[][] { { 1, 10, 15, 4 }, { 13, 6, 3, 8 }, { 2, 9, 12, 7 }, { 14, 5, 0, 11 } };
break;
case 80:// 80 steps to solve. max possible steps for 15 puzzle
solve = new int[][] { { 0, 12, 9, 13 }, { 15, 11, 10, 14 }, { 3, 7, 2, 5 }, { 4, 8, 6, 1 } };
break;
}
initialState = new State(solve);
}
private static void WriteResultState(/*String resultStatePath,*/ String solution) throws IOException {
int resultLenght = solution != "No solution found!" ? solution.length() : -1;
System.out.println("solution length: "+resultLenght);
if(resultLenght != -1) {
System.out.println(solution.toUpperCase());
}
}
private static void WriteAdditionalInfo(/*String additionalInfoPath,*/int resultLength, int numberOfVisitedStates,
int numberOfProcessedStates, int maxDepth, long calculationTime) throws IOException {
System.out.println("Length: "+resultLength);
System.out.println("Processed states: "+numberOfProcessedStates);
System.out.println("Visited states : "+ numberOfVisitedStates);
System.out.println("Depth: "+maxDepth);
System.out.println("Time: "+String.valueOf(calculationTime));
}
}
class State {
//use private fields. access with getters / setters
private State previousState;
private final List<State> nextStates;
private final int[][] puzzle;
private char move;
private String moveSet;
private final int width, height; //should not be static
private final Point zeroIndex;
private int depth = 0;
public State(int[][] puzzle) {
nextStates = new ArrayList<>();
this.puzzle = puzzle;
width = puzzle[0].length;
height = puzzle.length;
zeroIndex = get0Location();
if(zeroIndex == null) throw new IllegalArgumentException("No 0 is puzzle");
moveSet = "";
}
public State(int[][] puzzle, int height, int width, Point zeroIndex) {
nextStates = new ArrayList<>();
this.width = width;
this.height = height;
this.puzzle = puzzle;
this.zeroIndex = zeroIndex;
moveSet = "";
}
public State(State state)
{
moveSet = state.moveSet;
nextStates = new ArrayList<>();
width = state.width;
height = state.height;
puzzle = new int[state.height][state.width];
previousState = state.previousState;
for(int i=0; i < state.height;i++){
puzzle[i] = Arrays.copyOf(state.puzzle[i], state.puzzle[i].length);
}
zeroIndex = new Point(state.zeroIndex);
}
public State move(char direction)
{
State newState = new State(this);
newState.move = direction;
newState.moveSet += direction;
newState.previousState = this;
newState.depth = depth + 1;
switch (direction)
{
case 'u':
int tempu = newState.puzzle[zeroIndex.x][zeroIndex.y];
newState.puzzle[zeroIndex.x][zeroIndex.y] = newState.puzzle[zeroIndex.x - 1][zeroIndex.y];
newState.puzzle[zeroIndex.x - 1][zeroIndex.y] = tempu;
newState.zeroIndex.x--;
break;
case 'd':
int tempd = newState.puzzle[zeroIndex.x][zeroIndex.y];
newState.puzzle[zeroIndex.x][zeroIndex.y] = newState.puzzle[zeroIndex.x + 1][zeroIndex.y];
newState.puzzle[zeroIndex.x + 1][zeroIndex.y] = tempd;
newState.zeroIndex.x++;
break;
case 'l':
int templ = newState.puzzle[zeroIndex.x][zeroIndex.y];
newState.puzzle[zeroIndex.x][zeroIndex.y] = newState.puzzle[zeroIndex.x][zeroIndex.y-1];
newState.puzzle[zeroIndex.x][zeroIndex.y-1] = templ;
newState.zeroIndex.y--;
break;
case 'r':
int tempr = newState.puzzle[zeroIndex.x][zeroIndex.y];
newState.puzzle[zeroIndex.x][zeroIndex.y] = newState.puzzle[zeroIndex.x][zeroIndex.y + 1];
newState.puzzle[zeroIndex.x][zeroIndex.y + 1] = tempr;
newState.zeroIndex.y++;
break;
}
return newState;
}
public void generateNextStates(String order)
{
char [] chars = order.toCharArray();
for(char direction : chars)
{
if(isMovePossible(direction) == true && isNotGoingBack(direction) == true)
{
nextStates.add(this.move(direction));
}
}
}
public boolean isMovePossible(char direction)
{
if (!"udlr".contains(Character.toString(direction)) ||
zeroIndex.x == 0 && direction == 'u' ||
zeroIndex.x == height - 1 && direction == 'd' ||
zeroIndex.y == 0 && direction == 'l' ||
zeroIndex.y == width - 1 && direction == 'r')
return false;
return true;
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
for(int i = 0; i < height;i++)
{
for (int j = 0; j < width; j++)
{
sb.append(String.format("%1$4s", puzzle[i][j]));
}
sb.append("\n");
}
return sb.toString();
}
private boolean isNotGoingBack(char direction)
{
if(move == 'l' && direction == 'r' ||
move == 'u' && direction == 'd' ||
move == 'r' && direction == 'l' ||
move == 'd' && direction == 'u')
return false;
return true;
}
private Point get0Location() {
for (int row = 0; row < height; row++){
for (int col = 0; col < width ; col++){
if (puzzle[row][col] == 0) return new Point(row, col);
}
}
return null;
}
List<State> getNextStates() {
return nextStates;
}
String getMoveSet() {
return moveSet;
}
int getDepth() {
return depth;
}
int[][] getPuzzle(){
return puzzle;
}
@Override
public int hashCode() {
StringBuilder sb = new StringBuilder();
for(int[] row : puzzle) {
for(int i : row) {
sb.append(i);
}
}
return sb.toString().hashCode();
}
}
abstract class Solution {
protected State initialState, solutionState;
protected String neighborhoodSearchOrder;
protected int numberOfVisitedStates;
protected int numberOfProcessedStates;
protected int maxDepth;
public abstract String findSolution();
protected boolean isSolution(State state)
{
return Arrays.deepEquals(state.getPuzzle(), solutionState.getPuzzle());
}
public int getNumberOfVisitedStates() {
return numberOfVisitedStates;
}
public int getNumberOfProcessedStates() {
return numberOfProcessedStates;
}
public int getMaxDepth() {
return maxDepth;
}
}
class BFS extends Solution {
private State currentState;
private long starttime ;
public BFS(State initialState,State solutionState, String neighborhoodSearchOrder)
{
this.initialState = initialState;
this.solutionState = solutionState;
this.neighborhoodSearchOrder = neighborhoodSearchOrder.toLowerCase();
}
@Override
public String findSolution() {
starttime = System.nanoTime();
Queue<State> toVisit = new LinkedList<>();
Set<State> visited = new HashSet<>();
String solutionString = "";
boolean solutionReady = false;
numberOfVisitedStates = 0;
numberOfProcessedStates = 0;
maxDepth = 0;
toVisit.add(initialState);
visited.add(initialState);
while(toVisit.size() > 0)
{
currentState = toVisit.remove();
numberOfProcessedStates++;
if(currentState.getDepth() > maxDepth)
{
maxDepth = currentState.getDepth();
System.out.println("Processed: "+ numberOfProcessedStates +" nodes, depth: " + maxDepth+ " in "
+ (System.nanoTime() - starttime)/1000000000 + " seconds " );
}
if(isSolution(currentState))
{
solutionString = currentState.getMoveSet();
solutionReady = true;
break;
}
currentState.generateNextStates(neighborhoodSearchOrder);
for (State state : currentState.getNextStates())
{
if( visited.add(state))
{
toVisit.add(state);
}
}
}
numberOfVisitedStates = numberOfProcessedStates+ toVisit.size();
//System.out.println("End state: "+ "\n" + currentState);
return solutionReady ? solutionString : "No solutionString found";
}
}
Для дальнейшего улучшения я бы порекомендовал: -Проверьте разрешимость , прежде чем пытаться решить. -Проверьте, нужно ли вообще visited.
Примечание: см. Java Соглашения об именах .