java 8-Puzzle Solution 无限执行
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/13053455/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
8-Puzzle Solution executes infinitely
提问by Ashwin
I am looking for a solution to 8-puzzleproblem using the A* Algorithm. I found thisproject on the internet. Please see the files - proj1and 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?
我要寻找到一个解决方案8拼图使用问题A* Algorithm。我在网上找到了这个项目。请查看文件 -proj1和EightPuzzle. proj1 包含程序（main()函数）的入口点，而 EightPuzzle 描述了拼图的特定状态。每个状态都是 8-puzzle 的一个对象。
我觉得逻辑上没什么问题。但是对于我尝试过的这两个输入，它会永远循环：{8,2,7,5,1,6,3,0,4}和{3,1,6,8,4,5,7,2,0}。它们都是有效的输入状态。代码有什么问题？
Note
笔记
- 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 heresolves 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. opensetis the PriorityQueue containing unexpanded nodes and closedsetis the LinkedList containing expanded nodes.
- 为了更好地查看代码，请在 Notepad++ 或其他一些文本编辑器（具有识别 java 源文件的能力）中复制代码，因为代码中有很多注释。
- 由于 A* 需要启发式方法，因此他们提供了使用曼哈顿距离的选项和计算错位图块数量的启发式方法。并且为了确保最好的启发式算法首先被执行，他们已经实现了一个
PriorityQueue. 该compareTo()函数在EightPuzzle类中实现。 - 输入到程序可以通过改变的值来改变
p1d在main()的函数proj1的类。 - 我告诉我上面的两个输入存在解决方案的原因是因为这里的小程序解决了它们。请确保您从小程序中的选项中选择了 8-puzzle。
EDIT1
我给了这个输入{0,5,7,6,8,1,2,4,3}。花了大约26 步才10 seconds得出结果。但是小程序给出了一个结果in with 。 EDIT2在调试时，我注意到随着节点的扩展，新节点在一段时间后都有一个启发式 - as or 。它们似乎永远不会减少。所以过了一段时间后，所有的州24 moves0.0001 secondsA*f_n1112PriorityQueue(openset)启发式为 11 或 12。因此可供选择的节点不多，要扩展到哪个节点。最小是11，最大是12，这正常吗？
EDIT3
这是发生无限循环的代码段（在proj1-astar() 中）。openset是包含未扩展节点的 PriorityQueue，closedset是包含扩展节点的 LinkedList。
while(openset.size() > 0){
而（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
I have got the cause of this infinite loop. See my answer. But it takes about 25-30 secondsto 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.
EDIT4
我知道了这个无限循环的原因。看我的回答。但是执行大约需要25-30 秒，这是相当长的时间。A* 应该比这快得多。小程序在0.003 秒内完成此操作。我将奖励改善表现的赏金。
Forquick reference I have pasted the the two classes without the comments :
为了快速参考，我粘贴了没有注释的两个类：
EightPuzzle
八拼图
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
项目1
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;
}
}
回答by Gene
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.
这是一个建议。对于您的示例，我的计时器报告 0 毫秒。此处给出的更难的谜题需要 31 步才能完成，需要 96 毫秒。
A HashSetmakes 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.
AHashSet对于封闭集比链表更有意义。它有 O(1) 时间插入和成员资格测试，其中您的链表需要的时间与列表的长度成正比，并且在不断增长。
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.
您正在使用额外的数据结构和代码，使您的程序比所需的更复杂和更慢。多思考，少编码，学习别人的好代码来克服这个问题。我的并不完美（从来没有代码是完美的），但它是一个起点。
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 willaffect run time enormously. For example, h=0 will produce brute force breadth first search.
我使用了从每个瓦片的当前位置到其目标的最大曼哈顿距离作为启发式方法。启发式的选择不会影响解决方案中的步骤数，但会极大地影响运行时间。例如，h=0 将产生蛮力广度优先搜索。
Note that for A* to provide an optimal solution, the heuristic can never over-estimatethe 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.
请注意，为了让 A* 提供最佳解决方案，启发式算法永远不会高估达到目标的实际最小步数。如果这样做，解决方案是 find 可能不是最短的。我不肯定“反转”色调具有此属性。
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);
}
}
回答by Ashwin
Found out the problem. This is the condition that is used to check if a node is present in closedset
发现问题了。这是用于检查节点是否存在于封闭集中的条件
if(!closedset.contains(y))
A linkedlist(closedset) executes the contains()by calling the equals()of the class, in this case EightPuzzle. The equals function in EightPuzzleis defined as follows
链表（封闭集）通过调用类的equals()来执行contains()，在本例中为EightPuzzle。EightPuzzle中的equals函数定义如下
public boolean equals(EightPuzzle test){
if(this.f_n != ((EightPuzzle)test).getF_n())
return false;
//System.out.println("in equals");
for(int i = 0 ; i < this.puzzle.length; i++)
{
if(this.puzzle[i] != ((EightPuzzle)test).puzzle[i])
return false;
}
return true;
}
But this function was never called because if you want to override the equals()of Objectclass the correct signature should be
但是，这个功能是从来没有所谓的，因为如果你想覆盖equals（）方法的对象类的正确的签名应该是
public boolean equals(Object test).
One more change required- comment the first two lines of the equals()
需要再做一个更改- 注释 equals() 的前两行
I got the answer. But the code still takes 25-30seconds for some inputs. This is not expected with A*. the applet solves the puzzle in 0.003 seconds. If someone has an idea how to improve the performance, please do tell me.
I will award the bounty to that person.
我得到了答案。但是对于某些输入，代码仍然需要25-30秒。A* 不会出现这种情况。小程序在0.003 秒内解决了难题。如果有人知道如何提高性能，请告诉我。
我会把赏金奖励给那个人。
回答by Ashwin
Got the answer for optimization from another forum.
Change openset.size()and neightbor.size()
toopenset.isEmpty()and neightbor.isEmpty()respectively.size()iterates through the whole list and as the list gets bigger, it takes more and more time. And also change the EightPuzzle x = openset.peek();
toEightPuzzle x = openset.poll();and reuse x, instead of calling peek()and the poll()
从另一个论坛得到了优化的答案。
变化openset.size()和neightbor.size()
对openset.isEmpty()和neightbor.isEmpty()分别。size()遍历整个列表，随着列表变大，它需要越来越多的时间。并且还更改 EightPuzzle x = openset.peek();
为EightPuzzle x = openset.poll();并重用 x，而不是调用peek()和poll()
Now it processes within 1 second
现在它处理内 1 second
回答by Hamad AlMarri
I believe there is nothing wrong with your code, however, note that not all 8-puzzle problems are solvable! so check first if "{8,2,7,5,1,6,3,0,4} and {3,1,6,8,4,5,7,2,0}" are solvable 8-puzzles.
我相信您的代码没有问题，但是请注意，并非所有 8 拼图问题都可以解决！所以首先检查“{8,2,7,5,1,6,3,0,4} 和 {3,1,6,8,4,5,7,2,0}”是否是可解的 8-puzzles .
