8-Puzzle Solution无限执行

我正在寻找使用A* Algorithm 8-puzzle问题的解决方案。 我在互联网上找到了这个项目。 请参阅文件 – proj1和EightPuzzle 。 proj1包含程序的入口点（ main()函数），EightPuzzle描述了拼图的特定状态。 每个州都是8拼图的对象。
我觉得逻辑没有错。 但它为我尝试的这两个输入永远循环： {8,2,7,5,1,6,3,0,4}和{3,1,6,8,4,5,7,2,0} 。 它们都是有效的输入状态。 代码有什么问题？

---

注意

• 为了更好地查看，请在Notepad ++或其他文本编辑器（具有识别java源文件的能力）中复制代码，因为代码中有很多注释。
• 由于A *需要启发式算法，因此他们提供了使用曼哈顿距离的选项以及计算错位图块数量的启发式算法。 为了确保首先执行最佳启发式，他们实现了PriorityQueue 。 compareTo()函数在EightPuzzle类中实现。
• 可以通过更改proj1类的main()函数中的p1d值来更改程序的输入。
• 我告诉我上述两个输入存在解决方案的原因是因为这里的applet解决了它们。 请确保您从小程序中的选项中选择8-puzzle。

  EDIT1
  我给出了这个输入{0,5,7,6,8,1,2,4,3} 。 花了大约10 seconds ，结果有26个动作 。 但是小程序用A*在0.0001 seconds进行了24 moves 。

  EDIT2
  调试时我注意到，随着节点的扩展，新节点在一段时间后都有一个启发式 – f_n为11或12 。 他们似乎永远不会减少。 因此，在一段时间之后， PriorityQueue(openset)中的所有状态都具有11或12的启发式。因此，没有太多可供选择的扩展节点。 最小的是11，最高的是12.这是正常的吗？

  EDIT3
  这是无限循环发生的片段（在proj1-astar（）中 ）。 openset是包含未展开节点的PriorityQueue，而closedset是包含展开节点的LinkedList。

while（openset.size（）> 0）{

  EightPuzzle x = openset.peek(); if(x.mapEquals(goal)) { Stack toDisplay = reconstruct(x); System.out.println("Printing solution... "); System.out.println(start.toString()); print(toDisplay); return; } closedset.add(openset.poll()); LinkedList  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秒内执行此操作。 我将奖励奖励以改善表现。

---

为了快速参考，我已经粘贴了两个没有注释的类：

EightPuzzle

  import java.util.*; public class EightPuzzle implements Comparable  { 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 getChildren() { LinkedList children = new LinkedList(); 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; 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

 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 closedset = new LinkedList(); // openset := set containing the initial node // The set of tentative nodes to be evaluated. priority queue PriorityQueue openset = new PriorityQueue(); 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 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  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 x) { while(!x.isEmpty()) { EightPuzzle temp = x.pop(); System.out.println(temp.toString()); } } public static Stack reconstruct(EightPuzzle winner) { Stack correctOutput = new Stack(); while(winner.getParent() != null) { correctOutput.add(winner); winner = winner.getParent(); } return correctOutput; } } 

Answer 1

这是一个提案。 我的计时器为您的示例报告0毫秒。 在这里给出的更难的拼图，需要31步才能完成，需要96毫秒。

对于闭合集， HashSet比链表更有意义。 它具有O（1）时间插入和成员资格测试，其中您的链接列表需要与列表长度成比例的时间，该列表不断增长。

您正在使用额外的数据结构和代码，使您的程序比所需的更复杂和更慢。 多想想，少编码，研究别人的好代码来克服这个问题。 我的不完美（没有代码），但它是一个开始的地方。

我使用了启发式算法，从每个瓷砖的当前位置到其目标的曼哈顿距离的最大值。 启发式的选择不会影响解决方案中的步骤数，但会极大地影响运行时间。 例如，h = 0将产生powershell广度优先搜索。

请注意，对于A *来提供最佳解决方案，启发式方法永远不能高估目标的实际最小步数。 如果它这样做，解决方案的发现可能不是最短的。 我不是肯定的“反转”具有这种属性。

 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  queue = new PriorityQueue(100, new Comparator() { @Override public int compare(State a, State b) { return a.priority() - b.priority(); } }); // The closed state set. final HashSet  closed = new HashSet (); // 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); } } 

Answer 2

发现了问题。 这是用于检查节点是否存在于closedset中的条件

 if(!closedset.contains(y)) 

链表（closedset）通过调用类的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; } 

但是从未调用此函数，因为如果要覆盖Object类的equals（） ，则应该使用正确的签名

  public boolean equals(Object test). 

还需要一个更改 - 评论equals的前两行（）

我得到了答案。 但是对于某些输入，代码仍需要25-30秒。 A *不会出现这种情况。 小程序在0.003秒内解决了这个难题。 如果有人知道如何提高性能，请告诉我。
我将奖励给那个人。

Answer 3

从另一个论坛得到优化的答案。

更改openset.size()和openset.size() neightbor.size()
至
openset.isEmpty()和openset.isEmpty() 。

size()遍历整个列表，随着列表变大，需要花费越来越多的时间。 并且还改变了EightPuzzle x = openset.peek();
至
EightPuzzle x = openset.poll(); 并重用x，而不是调用peek()和poll()

现在它在1 second内处理

Answer 4

我相信你的代码没有任何问题，但请注意，并非所有的8-puzzle问题都是可以解决的！ 所以首先检查“{8,2,7,5,1,6,3,0,4}和{3,1,6,8,4,5,7,2,0}”是否可以解决8-puzzles 。