Я пишу программу, в которой используется 8-элементная головоломка, для поиска которой используется поиск в ширину. Я получаю его, чтобы запустить и решить проблему, но я не получаю правильный вывод для числа узлов, расширенного до поиска, например, если у меня есть вход 123 456 708 (в массиве из трех D), и у меня есть состояние цели123,456,780, тогда я должен увеличить число состояний до трех, потому что от начального значения ноль может идти вверх, влево или вправо. Но я запускаю свою программу и получаю число расширенных узлов, равное 7. Это почти положительно, потому что я неправильно выполняю циклы по всем преемникам или развернутым узлам в очереди, чтобы создать и проверять, равны ли оницель. Кто-нибудь знает, как бы я получил правильное количество расширенных узлов? Вот мой код.
public class BreadthFirst {
public static void search(int[] start, int[] goalState) {
Node root = new Node(start);
Node goal = new Node(goalState);
BFSSearch(root, goal);
}
/**
* the breadth-first search
*
* @param
*/
public static void BFSSearch(Node start, Node goal) {
int branchFactor = 0;
int NodesLookedAt = 0;
Queue<Node> q = new LinkedList<>();
q.add(start);
ArrayList<Node> visited = new ArrayList<>(); // arraylist of visited states.
visited.add(start);// adding the initial state to the queue.
while (!q.isEmpty()) {
Node theNode = q.remove(); // pop it off the queue
if (!Arrays.equals(theNode.curr, goal.curr)) { // if the current state of the board is not equal to the goal
// state
ArrayList<Node> tempSuccessors = theNode.genSuccessors(); // generate that states successors.
branchFactor++;
if (branchFactor == 10) { // only allow ten branches to be allowed (Not sure if this is right)
System.out.println(" 10 Levels were opened and no solution was found. ");
System.exit(0);
}
for (int i = 0; i < tempSuccessors.size(); i++) { // loop through all the generated successors.
Node newNode = new Node(tempSuccessors.get(i).curr, theNode);
visited.add(newNode); // add node to visited
for (int j = 0; j < visited.size(); j++) { // loop through visited nodes and check if that node is
// the same as a node we already saw
if (!Arrays.equals(visited.get(j).curr, newNode.curr))
q.add(newNode); // if it is not then add it to the queue
}
NodesLookedAt++; // increase the nodes looked at.
}
}
else { // found the goal now we need to print off the goal path.
Stack<Node> path = new Stack<>(); // create stack
path.push(theNode); // push the last node onto the stacks
theNode = theNode.getParent();
while (theNode.getParent() != null) { // keep pushing the nodes parents onto the stack so that we get
// the path.
path.push(theNode);
theNode = theNode.getParent();
}
path.push(theNode);
int StackSize = path.size();
for (int i = 0; i < StackSize; i++) {
// when printing it is going to print out in reverse order which is what we need
// for
// it to be printed off as start state to goal state.
theNode = path.pop();
theNode.printState();
System.out.println();
System.out.println();
}
System.out.println(NodesLookedAt); // print out the number of nodes looked at before the goal is found.
System.out.println("Number of Nodes Searched to Goal Path. " + (StackSize)); // number of nodes in the
// solution path.
System.exit(0);
}
}
}
}