我正在寻找使用的8难题问题的解决方案A* Algorithm。我在互联网上找到了 这个 项目。请查看文件- proj1和EightPuzzle。proj1包含程序（main()函数）的入口点，EightPuzzle描述拼图的特定状态。每个状态都是8拼图的对象。 我觉得逻辑上没有错。但是对于我尝试的这两个输入，它永远循环：{8,2,7,5,1,6,3,0,4}和{3,1,6,8,4,5,7,2,0}。它们都是有效的输入状态。代码有什么问题？
A* Algorithm
proj1
EightPuzzle
main()
{8,2,7,5,1,6,3,0,4}
{3,1,6,8,4,5,7,2,0}
注意
PriorityQueue
compareTo()
p1d
EDIT1* 我给了这个输入{0,5,7,6,8,1,2,4,3}。它进行了 26次动作10 seconds并给出了结果。但小程序给出了与结果中有。 EDIT2 在调试我注意到，随着节点的扩展，新的节点，一段时间后，都有一个启发- 作为或。他们似乎从未减少。因此，一段时间后， *24 moves``0.0001 seconds``A*
{0,5,7,6,8,1,2,4,3}
10 seconds
24 moves``0.0001 seconds``A*
f_n``11``12``PriorityQueue(openset)具有11或12的试探法。因此，要扩展到哪个节点没有太多选择。最少的是11，最高的是12。这正常吗？
f_n``11``12``PriorityQueue(openset)
EDIT3 这是无限循环发生的代码片段（在 proj1-astar（）中 ）。 openset 是包含未扩展节点的PriorityQueue， closeset 是包含扩展节点的LinkedList。
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秒内 完成此操作。 我将奖励改善性能的赏金。*
为了 快速参考，我在没有注释的情况下粘贴了两个类：
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; } }
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毫秒。
一个HashSet做了闭集比你的链表更有意义。它具有O（1）时间插入和成员资格测试，其中链接列表所需要的时间与列表的长度成正比，并且该长度在不断增长。
HashSet
您正在使用额外的数据结构和代码，这些数据和代码会使您的程序变得比所需的复杂和缓慢。多思考，少编写代码，研究其他人的好代码以克服这一问题。我的不是完美的（从来没有代码是完美的），但这是一个起点。
我将每个瓷砖的当前位置到目标的最大曼哈顿距离用作启发式方法。启发式的选择不会影响解决方案中的步骤数，但是 会 极大地影响运行时间。例如，h = 0将产生蛮力广度优先搜索。
请注意，为使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 <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); } }
