我正在尝试使用Java中的BFS算法为15个难题创建一个求解器。问题是，当我启动程序时，它以无限循环结束。我尝试使用简单的输入状态，例如从已解决状态仅交换2个数字，它就可以工作。似乎很难解决更复杂的问题。
我检查了所有内容，如果队列中填充了正确的状态，如果零索引可以很好地容纳这些状态。看起来应该可以正常工作，但事实并非如此。这是我的代码：
Program.java
package Puzzle;
import java.awt.*;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
public class Program {
public static final int[][] solved = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 0 } };
public static final State solvedState = new State(solved, 4, 4, new Point(3, 3));
static Solution solution;
public static void main(String[] args) throws IOException {
if(args.length != 5)
{
System.out.println("Wrong number of arguments in configuration. Given args:");
int nr = 0;
for (var arg : args)
{
System.out.println(nr++ + ": " + arg);
}
return;
}
State initialState = ReadInitialStateFromFile(args[2]);
switch (args[0])
{
case "bfs":
solution = new BFS(initialState, args[1]);
break;
case "dfs":
//solution = new DFS(initialState, args[1]);
break;
case "astr":
//solution = new AStar(initialState, args[1]);
break;
default:
System.out.println("incorrect method parameter");
return;
}
long starttime = System.nanoTime();
String solutionString = solution.FindSolution();
long endtime = System.nanoTime();
long elapsedTime = endtime - starttime;
long elapsedTimeMS = elapsedTime/1000000;
int solutionLength = solutionString != "No solution found!" ? solutionString.length() : -1;
WriteResultState(args[3], solutionString);
WriteAdditionalInfo(args[4],
solutionLength,
solution.numberOfVisitedStates,
solution.numberOfProcessedStates,
solution.maxDepth,
elapsedTimeMS
);
}
public static State ReadInitialStateFromFile(String filename) throws IOException {
String data = null;
int height = -1;
int width = -1;
Point point = new Point();
int [][] puzzle = null;
BufferedReader br = new BufferedReader(new FileReader(filename));
try {
data = br.readLine();
if(data == null || data.length() != 3)
{
throw new Exception("Dimentions are not correct");
}
String[] dimentions = data.split(" ");
height = Integer.parseInt(dimentions[0]);
width = Integer.parseInt(dimentions[1]);
puzzle = new int[width][height];
for(int i=0; i<width;i++){
String values[] = br.readLine().split(" ");
if(values.length != width)
{
throw new Exception(String.format("Values in row {0} are not correct", i));
}
for (int j = 0; j < height; j++)
{
int value = Integer.parseInt(values[j]);
//System.out.println(value);
if(value == 0)
{
point = new Point(i, j);
System.out.println("zero point" + point.toString());
}
puzzle[i][j] = value;
}
}
} catch (Exception e) {
e.printStackTrace();
} finally {
br.close();
}
return new State(puzzle, height, width, point);
}
private static void WriteResultState(String resultStatePath, String solution) throws IOException {
int resultLenght = solution != "No solution found!" ? solution.length() : -1;
FileWriter fw = new FileWriter(resultStatePath);
fw.write(resultLenght);
if(resultLenght != -1)
fw.write(solution.toUpperCase());
fw.close();
}
private static void WriteAdditionalInfo(String additionalInfoPath, int resultLength, int numberOfVisitedStates, int numberOfProcessedStates, int maxDepth, long calculationTime) throws IOException {
FileWriter fw = new FileWriter(additionalInfoPath);
fw.write(resultLength);
fw.write(numberOfProcessedStates);
fw.write(numberOfVisitedStates);
fw.write(maxDepth);
fw.write(String.valueOf(calculationTime));
}
}
State.java
package Puzzle;
import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class State {
public State previousState;
public List<State> nextStates;
public int[][] puzzle;
public char move;
public String moveSet;
public static int width, height;
public Point zeroIndex;
public int depth = 0;
public State(int[][] p, int _height, int _width, Point _zeroIndex) {
nextStates = new ArrayList<State>();
puzzle = new int[_height][_width];
width = _width;
height = _height;
puzzle = Arrays.copyOf(p, p.length);
zeroIndex = _zeroIndex;
moveSet = "";
}
public State(State state)
{
moveSet = state.moveSet;
nextStates = new ArrayList<State>();
puzzle = new int[state.height][state.width];
previousState = state.previousState;
for(int i=0; i < state.height;i++){
for(int j =0; j<state.width; j++)
{
this.puzzle[i][j] = state.puzzle[i][j];
}
}
//this.puzzle = Arrays.copyOf(state.puzzle, state.puzzle.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++;
// System.out.println(newState.zeroIndex.toString());
// System.out.println(this.zeroIndex.toString());
break;
default:
break;
}
return newState;
}
public void GenerateNextStates(String order)
{
char [] chars = order.toCharArray();
for(char direction : chars)
{
if(IsMovePossible(direction) == true && IsNotGoingBack(direction) == true)
{
this.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;
}
public void Print()
{ for(int i = 0; i < height;i++)
{
for (int j = 0; j < width; j++)
{
System.out.println(puzzle[i][j] + " ");
}
System.out.println();
}
}
public boolean IsSolution()
{
int correctValue = 1;
for (int i = 0; i < State.height; i++)
{
for (int j = 0; j < State.width; j++)
{
if (i == State.height - 1 && j == State.width - 1)
{
break;
}
if (puzzle[i][j] != correctValue++)
{
return false;
}
}
}
return true;
}
public boolean IsPuzzleSame(State other)
{
for (int i = 0; i < State.height; i++)
{
for (int j = 0; j < State.width; j++)
{
if(this.puzzle[i][j] != other.puzzle[i][j])
{
return false;
}
}
}
return true;
}
private boolean IsNotGoingBack(char direction)
{
if((this.move == 'l' && direction == 'r') ||
(this.move == 'u' && direction == 'd') ||
(this.move == 'r' && direction == 'l') ||
(this.move == 'd' && direction == 'u'))
{
//System.out.println("znaleziono powrót");
return false;
}
return true;
}
}
Solution.java
package Puzzle;
import java.util.Queue;
public abstract class Solution {
public static State solutionState;
public static String neighborhoodSearchOrder;
public static int numberOfVisitedStates;
public static int numberOfProcessedStates;
public static int maxDepth;
public abstract String FindSolution();
protected boolean IsPuzzleStateNew(Queue<State> q, State newState)
{
for (State state : q)
{
if (state.IsPuzzleSame(newState))
{
return false;
}
}
return true;
}
}
BFS.java
package Puzzle;
import java.util.*;
public class BFS extends Solution {
public BFS(State _initialState, String _neighborhoodSearchOrder)
{
this.solutionState = _initialState;
this.neighborhoodSearchOrder = _neighborhoodSearchOrder.toLowerCase();
}
@Override
public String FindSolution() {
Queue<State> toVisit = new LinkedList<State>();
Queue<State> visited = new LinkedList<State>();
String solutionString = "";
boolean solutionReady = false;
toVisit.add(solutionState);
int z = 0;
while(toVisit.size() > 0)
{
// System.out.println("visited");
// for(int i=0; i<visited.size();i++){
// System.out.println("visited size: " + visited.size());
// }
//
//System.out.println(toVisit.size());
State currentState = toVisit.remove();
visited.add(currentState);
System.out.println("Numer iteracji: " + z);
//currentState.Print();
if(currentState.depth > maxDepth)
{
maxDepth = currentState.depth;
}
if(currentState.IsSolution())
{
solutionString = currentState.moveSet;
solutionReady = true;
break;
}
currentState.GenerateNextStates(neighborhoodSearchOrder);
Queue<State> allStates = new LinkedList<State>();
allStates.addAll(toVisit);
allStates.addAll(visited);
// for (State state: currentState.nextStates){
// System.out.println(state.zeroIndex.toString());
// state.Print();
// }
for (State state : currentState.nextStates)
{
if(IsPuzzleStateNew(allStates, state))
{
toVisit.add(state);
}
}
allStates.clear();
z++;
}
numberOfVisitedStates = visited.size() + toVisit.size();
numberOfProcessedStates = visited.size();
System.out.println(numberOfVisitedStates);
System.out.println(numberOfProcessedStates);
return solutionReady ? solutionString : "No solutionString found";
}
}
我花了很多时间进行故障排除，现在我实在无可救药。预先感谢您的帮助。
我在4x4拼图上测试了代码。它正确地解决了需要多达14个步骤的难题，但是花费了很长时间。19小时后，我停止了15个步骤的拼图解决方案。
为了加速代码，我在hashCode()中引入了State方法。实施hashCode()使我可以通过使用if(IsPuzzleStateNew(allStates, state))来更改昂贵的Set测试visited并使isPuzzleStateNew和isPuzzleSame冗余。我还重构了isSolution，使其更通用，更快。
时间发生了巨大变化，多达16个步骤的难题毫无问题地运行：
由于尚需调查的原因，测试难题需要35和80步崩溃。
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";
}
}
为了进一步改进，我建议：-在尝试求解之前，请检查solvability。-检查是否完全需要visited。
旁注：请参阅Java naming conventions。