这是一个建议。我的计时器报告您的示例为0毫秒。在此处给出的难度较大的难题中，需要完成31个动作才能完成，耗时96毫秒。
一个
HashSet做了闭集比你的链表更有意义。它具有O（1）时间插入和成员资格测试，其中链接列表所需要的时间与列表的长度成正比，并且该长度在不断增长。
您正在使用额外的数据结构和代码，这些数据和代码会使您的程序变得比所需的复杂和缓慢。多思考，少编写代码，研究其他人的好代码以克服这一问题。我的不是完美的（从来没有代码是完美的），但这是一个起点。
我将每个瓷砖的当前位置到目标的最大曼哈顿距离用作启发式方法。启发式的选择不会影响解决方案中的步骤数，但是 会 极大地影响运行时间。例如，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); }}
