8-Puzzle Solution无限执行 [英] 8-Puzzle Solution executes infinitely
本文介绍了8-Puzzle Solution无限执行的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在寻找 8-puzzle的解决方案使用 A *算法的问题。我找到了 这个 项目。请参阅文件 - proj1 和 EightPuzzle 。 proj1包含程序的入口点（ main（）函数），EightPuzzle描述了拼图的特定状态。每个州都是8拼图的对象。我觉得逻辑没有错。但它为我尝试的这两个输入永远循环： {8,2,7,5,1,6,3,0,4} 和 {3,1,6,8,4,5,7,2,0} 。它们都是有效的输入状态。代码有什么问题？
I am looking for a solution to 8-puzzle problem using the A* Algorithm. I found this project on the internet. Please see the files - proj1 and EightPuzzle. The proj1 contains the entry point for the program(the main() function) and EightPuzzle describes a particular state of the puzzle. Each state is an object of the 8-puzzle.
I feel that there is nothing wrong in the logic. But it loops forever for these two inputs that I have tried : {8,2,7,5,1,6,3,0,4} and {3,1,6,8,4,5,7,2,0}. Both of them are valid input states. What is wrong with the code?
注意
- 为了更好地查看，请在Notepad ++或其他文本
编辑器（具有识别java源文件的能力）中复制代码
，因为代码中有很多注释。 - 由于A *需要启发式算法，因此他们提供了使用
曼哈顿距离的选项以及计算$ b数量的启发式算法$ b错位了瓷砖。为了确保首先执行最佳启发式
，他们已经实现了PriorityQueue。compareTo（）
函数在EightPuzzle类中实现。 - 可以通过在
main（）函数中更改p1d的值来更改程序的输入。proj1class。 - 我告诉上述两个输入存在解决方案的原因是因为applet 这里解决了这些问题。请确保您从小程序中的选项中选择8-puzzle。
EDIT1
我提供此输入{0,5,7,6,8,1,2， 4,3}。花了大约10秒并以 26次移动给出了结果。但是applet在0.0001秒中以A * 24次移动的结果C $ C>。
EDIT2
调试时我注意到，随着节点的扩展，新节点在一段时间后都有了启发式 -f_nas11或12。他们似乎永远不会减少。所以在一段时间后，PriorityQueue（openset）中的所有状态都具有11或12的启发式。因此，没有太多可供选择的节点来扩展。最小的是11，最高的是12.这是正常的吗？
EDIT3
这是片段（在 proj1中） -astar（））无限循环发生的地方。 openset 是包含未展开节点的PriorityQueue， closedset 是包含展开节点的LinkedList。
- For better viewing copy the code in a Notepad++ or some other text editor(which has the capability to recognize java source file) because there are lot of comments in the code.
- Since A* requires a heuristic, they have provided the option of using
manhattan distance and a heuristic that calculates the number of
misplaced tiles. And to ensure that the best heuristic is executed
first, they have implemented a
PriorityQueue. ThecompareTo()function is implemented in theEightPuzzleclass. - The input to the program can be changed by changing the value of
p1din themain()function ofproj1class. - The reason I am telling that there exists solution for the two my above inputs is because the applet here solves them. Please ensure that you select 8-puzzle from the options in the applet.
EDIT1
I gave this input{0,5,7,6,8,1,2,4,3}. It took about10 secondsand gave a result with 26 moves. But the applet gave a result with24 movesin0.0001 secondswithA*.
EDIT2
While debugging I noticed that as nodes are expanded, the new nodes, after sometime, all have a heuristic -f_nas11or12. They never seem to decrease. So after sometime all the states in thePriorityQueue(openset)have a heuristic of 11 or 12. So there is not much to choose from, to which node to expand. As the least is 11 and the highest is 12. Is this normal?
EDIT3
This is the snippet(in proj1-astar()) where the infinite looping happening. openset is the PriorityQueue containing unexpanded nodes and closedset is the LinkedList containing expanded nodes.
while（openset.size（）> 0）{
while(openset.size() > 0){
EightPuzzle x = openset.peek();
if(x.mapEquals(goal))
{
Stack<EightPuzzle> toDisplay = reconstruct(x);
System.out.println("Printing solution... ");
System.out.println(start.toString());
print(toDisplay);
return;
}
closedset.add(openset.poll());
LinkedList <EightPuzzle> neighbor = x.getChildren();
while(neighbor.size() > 0)
{
EightPuzzle y = neighbor.removeFirst();
if(closedset.contains(y)){
continue;
}
if(!closedset.contains(y)){
openset.add(y);
}
}
}
EDIT4
我得到了这个无限循环的原因。看到我的回答。但执行需要 25-30秒，这是相当长的一段时间。 A *应该比这快得多。小程序在 0.003秒中执行此操作。 我将奖励赏金以提高效果。
EDIT4
I have got the cause of this infinite loop. See my answer. But it takes about 25-30 seconds to execute, which is quite a long time. A* should do much faster than this. the applet does this in 0.003 seconds. I will award the bounty for improving the performance.
对于快速参考我已经粘贴了两个没有评论的课程：
For quick reference I have pasted the the two classes without the comments :
import java.util.*;
public class EightPuzzle implements Comparable <Object> {
int[] puzzle = new int[9];
int h_n= 0;
int hueristic_type = 0;
int g_n = 0;
int f_n = 0;
EightPuzzle parent = null;
public EightPuzzle(int[] p, int h_type, int cost)
{
this.puzzle = p;
this.hueristic_type = h_type;
this.h_n = (h_type == 1) ? h1(p) : h2(p);
this.g_n = cost;
this.f_n = h_n + g_n;
}
public int getF_n()
{
return f_n;
}
public void setParent(EightPuzzle input)
{
this.parent = input;
}
public EightPuzzle getParent()
{
return this.parent;
}
public int inversions()
{
/*
* Definition: For any other configuration besides the goal,
* whenever a tile with a greater number on it precedes a
* tile with a smaller number, the two tiles are said to be inverted
*/
int inversion = 0;
for(int i = 0; i < this.puzzle.length; i++ )
{
for(int j = 0; j < i; j++)
{
if(this.puzzle[i] != 0 && this.puzzle[j] != 0)
{
if(this.puzzle[i] < this.puzzle[j])
inversion++;
}
}
}
return inversion;
}
public int h1(int[] list)
// h1 = the number of misplaced tiles
{
int gn = 0;
for(int i = 0; i < list.length; i++)
{
if(list[i] != i && list[i] != 0)
gn++;
}
return gn;
}
public LinkedList<EightPuzzle> getChildren()
{
LinkedList<EightPuzzle> children = new LinkedList<EightPuzzle>();
int loc = 0;
int temparray[] = new int[this.puzzle.length];
EightPuzzle rightP, upP, downP, leftP;
while(this.puzzle[loc] != 0)
{
loc++;
}
if(loc % 3 == 0){
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 1];
temparray[loc + 1] = 0;
rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
rightP.setParent(this);
children.add(rightP);
}else if(loc % 3 == 1){
//add one child swaps with right
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 1];
temparray[loc + 1] = 0;
rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
rightP.setParent(this);
children.add(rightP);
//add one child swaps with left
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 1];
temparray[loc - 1] = 0;
leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
leftP.setParent(this);
children.add(leftP);
}else if(loc % 3 == 2){
// add one child swaps with left
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 1];
temparray[loc - 1] = 0;
leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
leftP.setParent(this);
children.add(leftP);
}
if(loc / 3 == 0){
//add one child swaps with lower
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 3];
temparray[loc + 3] = 0;
downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
downP.setParent(this);
children.add(downP);
}else if(loc / 3 == 1 ){
//add one child, swap with upper
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 3];
temparray[loc - 3] = 0;
upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
upP.setParent(this);
children.add(upP);
//add one child, swap with lower
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 3];
temparray[loc + 3] = 0;
downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
downP.setParent(this);
children.add(downP);
}else if (loc / 3 == 2 ){
//add one child, swap with upper
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 3];
temparray[loc - 3] = 0;
upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
upP.setParent(this);
children.add(upP);
}
return children;
}
public int h2(int[] list)
// h2 = the sum of the distances of the tiles from their goal positions
// for each item find its goal position
// calculate how many positions it needs to move to get into that position
{
int gn = 0;
int row = 0;
int col = 0;
for(int i = 0; i < list.length; i++)
{
if(list[i] != 0)
{
row = list[i] / 3;
col = list[i] % 3;
row = Math.abs(row - (i / 3));
col = Math.abs(col - (i % 3));
gn += row;
gn += col;
}
}
return gn;
}
public String toString()
{
String x = "";
for(int i = 0; i < this.puzzle.length; i++){
x += puzzle[i] + " ";
if((i + 1) % 3 == 0)
x += "\n";
}
return x;
}
public int compareTo(Object input) {
if (this.f_n < ((EightPuzzle) input).getF_n())
return -1;
else if (this.f_n > ((EightPuzzle) input).getF_n())
return 1;
return 0;
}
public boolean equals(EightPuzzle test){
if(this.f_n != test.getF_n())
return false;
for(int i = 0 ; i < this.puzzle.length; i++)
{
if(this.puzzle[i] != test.puzzle[i])
return false;
}
return true;
}
public boolean mapEquals(EightPuzzle test){
for(int i = 0 ; i < this.puzzle.length; i++)
{
if(this.puzzle[i] != test.puzzle[i])
return false;
}
return true;
}
}
proj1
proj1
import java.util.*;
public class proj1 {
/**
* @param args
*/
public static void main(String[] args) {
int[] p1d = {1, 4, 2, 3, 0, 5, 6, 7, 8};
int hueristic = 2;
EightPuzzle start = new EightPuzzle(p1d, hueristic, 0);
int[] win = { 0, 1, 2,
3, 4, 5,
6, 7, 8};
EightPuzzle goal = new EightPuzzle(win, hueristic, 0);
astar(start, goal);
}
public static void astar(EightPuzzle start, EightPuzzle goal)
{
if(start.inversions() % 2 == 1)
{
System.out.println("Unsolvable");
return;
}
// function A*(start,goal)
// closedset := the empty set // The set of nodes already evaluated.
LinkedList<EightPuzzle> closedset = new LinkedList<EightPuzzle>();
// openset := set containing the initial node // The set of tentative nodes to be evaluated. priority queue
PriorityQueue<EightPuzzle> openset = new PriorityQueue<EightPuzzle>();
openset.add(start);
while(openset.size() > 0){
// x := the node in openset having the lowest f_score[] value
EightPuzzle x = openset.peek();
// if x = goal
if(x.mapEquals(goal))
{
// return reconstruct_path(came_from, came_from[goal])
Stack<EightPuzzle> toDisplay = reconstruct(x);
System.out.println("Printing solution... ");
System.out.println(start.toString());
print(toDisplay);
return;
}
// remove x from openset
// add x to closedset
closedset.add(openset.poll());
LinkedList <EightPuzzle> neighbor = x.getChildren();
// foreach y in neighbor_nodes(x)
while(neighbor.size() > 0)
{
EightPuzzle y = neighbor.removeFirst();
// if y in closedset
if(closedset.contains(y)){
// continue
continue;
}
// tentative_g_score := g_score[x] + dist_between(x,y)
//
// if y not in openset
if(!closedset.contains(y)){
// add y to openset
openset.add(y);
//
}
//
}
//
}
}
public static void print(Stack<EightPuzzle> x)
{
while(!x.isEmpty())
{
EightPuzzle temp = x.pop();
System.out.println(temp.toString());
}
}
public static Stack<EightPuzzle> reconstruct(EightPuzzle winner)
{
Stack<EightPuzzle> correctOutput = new Stack<EightPuzzle>();
while(winner.getParent() != null)
{
correctOutput.add(winner);
winner = winner.getParent();
}
return correctOutput;
}
}
推荐答案
这是一个提案。我的计时器为您的示例报告0毫秒。在这里给出的更难的拼图，需要31步才能完成，需要96毫秒。
Here is a proposal. My timer reports 0 ms for your example. On the harder puzzle given here, which needs 31 moves to complete, it takes 96 ms.
A HashSet 对于闭包而言比链表更有意义。它有O（1）时间插入和成员资格测试，你的链表要求时间与列表的长度成正比，这个时间不断增长。
A HashSet makes much more sense for the closed set than your linked list. It has O(1) time insert and membership test, where your linked list requires time proportional to the length of the list, which is constantly growing.
你正在使用额外的数据结构和代码使您的程序比所需的更复杂和更慢。多想想，少编码，研究别人的好代码来克服这个问题。我不是完美的（没有代码），但它是一个开始的地方。
You are using extra data structures and code that make your program more complex and slower than needed. Think more, code less, and study others' good code to overcome this. Mine is not perfect (no code ever is), but it's a place to start.
我用作启发式，从每个瓷砖的平均位置到它的曼哈顿距离的最大值目标。启发式的选择不会影响解决方案中的步骤数，但 会极大地影响运行时间。例如，h = 0将产生强力广度优先搜索。
I used as the heuristic the max of Manhattan distances from each tile's currrent position to its goal. The choice of heuristic does not affect the number of steps in the solution, but it will affect run time enormously. For example, h=0 will produce brute force breadth first search.
请注意，对于A *来提供最佳解决方案，启发式方法永远不会高估实际达到目标的最小步数。如果它这样做，解决方案的发现可能不是最短的。我不是肯定的反转具有这种属性。
Note that for A* to provide an optimal solution, the heuristic can never over-estimate the actual minimum number of steps to the goal. If it does so, the solution is finds might not be the shortest possible. I'm not positive the "inversions" hueristic has this property.
package eightpuzzle;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
public class EightPuzzle {
// Tiles for successfully completed puzzle.
static final byte [] goalTiles = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
// A* priority queue.
final PriorityQueue <State> queue = new PriorityQueue<State>(100, new Comparator<State>() {
@Override
public int compare(State a, State b) {
return a.priority() - b.priority();
}
});
// The closed state set.
final HashSet <State> closed = new HashSet <State>();
// State of the puzzle including its priority and chain to start state.
class State {
final byte [] tiles; // Tiles left to right, top to bottom.
final int spaceIndex; // Index of space (zero) in tiles
final int g; // Number of moves from start.
final int h; // Heuristic value (difference from goal)
final State prev; // Previous state in solution chain.
// A* priority function (often called F in books).
int priority() {
return g + h;
}
// Build a start state.
State(byte [] initial) {
tiles = initial;
spaceIndex = index(tiles, 0);
g = 0;
h = heuristic(tiles);
prev = null;
}
// Build a successor to prev by sliding tile from given index.
State(State prev, int slideFromIndex) {
tiles = Arrays.copyOf(prev.tiles, prev.tiles.length);
tiles[prev.spaceIndex] = tiles[slideFromIndex];
tiles[slideFromIndex] = 0;
spaceIndex = slideFromIndex;
g = prev.g + 1;
h = heuristic(tiles);
this.prev = prev;
}
// Return true iif this is the goal state.
boolean isGoal() {
return Arrays.equals(tiles, goalTiles);
}
// Successor states due to south, north, west, and east moves.
State moveS() { return spaceIndex > 2 ? new State(this, spaceIndex - 3) : null; }
State moveN() { return spaceIndex < 6 ? new State(this, spaceIndex + 3) : null; }
State moveE() { return spaceIndex % 3 > 0 ? new State(this, spaceIndex - 1) : null; }
State moveW() { return spaceIndex % 3 < 2 ? new State(this, spaceIndex + 1) : null; }
// Print this state.
void print() {
System.out.println("p = " + priority() + " = g+h = " + g + "+" + h);
for (int i = 0; i < 9; i += 3)
System.out.println(tiles[i] + " " + tiles[i+1] + " " + tiles[i+2]);
}
// Print the solution chain with start state first.
void printAll() {
if (prev != null) prev.printAll();
System.out.println();
print();
}
@Override
public boolean equals(Object obj) {
if (obj instanceof State) {
State other = (State)obj;
return Arrays.equals(tiles, other.tiles);
}
return false;
}
@Override
public int hashCode() {
return Arrays.hashCode(tiles);
}
}
// Add a valid (non-null and not closed) successor to the A* queue.
void addSuccessor(State successor) {
if (successor != null && !closed.contains(successor))
queue.add(successor);
}
// Run the solver.
void solve(byte [] initial) {
queue.clear();
closed.clear();
// Click the stopwatch.
long start = System.currentTimeMillis();
// Add initial state to queue.
queue.add(new State(initial));
while (!queue.isEmpty()) {
// Get the lowest priority state.
State state = queue.poll();
// If it's the goal, we're done.
if (state.isGoal()) {
long elapsed = System.currentTimeMillis() - start;
state.printAll();
System.out.println("elapsed (ms) = " + elapsed);
return;
}
// Make sure we don't revisit this state.
closed.add(state);
// Add successors to the queue.
addSuccessor(state.moveS());
addSuccessor(state.moveN());
addSuccessor(state.moveW());
addSuccessor(state.moveE());
}
}
// Return the index of val in given byte array or -1 if none found.
static int index(byte [] a, int val) {
for (int i = 0; i < a.length; i++)
if (a[i] == val) return i;
return -1;
}
// Return the Manhatten distance between tiles with indices a and b.
static int manhattanDistance(int a, int b) {
return Math.abs(a / 3 - b / 3) + Math.abs(a % 3 - b % 3);
}
// For our A* heuristic, we just use max of Manhatten distances of all tiles.
static int heuristic(byte [] tiles) {
int h = 0;
for (int i = 0; i < tiles.length; i++)
if (tiles[i] != 0)
h = Math.max(h, manhattanDistance(i, tiles[i]));
return h;
}
public static void main(String[] args) {
// This is a harder puzzle than the SO example
byte [] initial = { 8, 0, 6, 5, 4, 7, 2, 3, 1 };
// This is taken from the SO example.
//byte [] initial = { 1, 4, 2, 3, 0, 5, 6, 7, 8 };
new EightPuzzle().solve(initial);
}
}
这篇关于8-Puzzle Solution无限执行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
