这是我在佛罗伦萨大学人工智能课程中的项目。我需要解决一个经典游戏：8和15格的滑动拼图。这是我的通用图搜索算法实现：

public abstract class GraphSearch implements SearchAlgorithm {protected Queue<Node> fringe;protected HashSet<Node> closedList;public GraphSearch() {    fringe = createFringe();    closedList = new HashSet<Node>(100);}protected abstract Queue<Node> createFringe();public int getNodeExpanded() {    return closedList.size();}@Overridepublic Solution search(Puzzle puzzle) {    fringe.add(new Node(puzzle.getInitialState(), null, null));    while (!fringe.isEmpty()) {        Node selectedNode = fringe.poll();        if (puzzle.getGoalTest().isGoalState(selectedNode.getState())) {            return new Solution(selectedNode, getNodeExpanded());        }        closedList.add(selectedNode);        LinkedList<Node> expansion = selectedNode.expandNode();        for (Node n : expansion) {            if (!closedList.contains(n) && !fringe.contains(n))                fringe.add(n);        }    }    return new Solution(null, getNodeExpanded());}}

这是我的A*算法代码：

public class AStar extends GraphSearch implements InformedSearch {private Heuristic heuristic;public AStar(Heuristic heuristic) {    setHeuristic(heuristic);}public Heuristic getHeuristic() {    return heuristic;}@Overridepublic void setHeuristic(Heuristic heuristic) {    this.heuristic = heuristic;}@Overrideprotected Queue<Node> createFringe() {    return new PriorityQueue<Node>(1000, new Comparator<Node>() {        @Override        public int compare(Node o1, Node o2) {            o1.setH(heuristic.h(o1));            o2.setH(heuristic.h(o2));            o1.setF(o1.getG() + o1.getH());            o2.setF(o2.getG() + o2.getH());            if (o1.getF() < o2.getF())                return -1;            if (o1.getF() > o2.getF())                return 1;            return 0;        }    });}}

这是我的曼哈顿启发式代码：

    @Overridepublic int h(Node n) {    int distance = 0;    ArrayList<Integer> board = n.getState().getBoard();    int[][] multiBoard = new int[N][N];    for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            multiBoard[i][j] = board.get(i * N + j);        }    }    for (int i = 0; i < N; i++) {        for (int j = 0; j < N; j++) {            int value = multiBoard[i][j];            if (multiBoard[i][j] != 0) {                int targetX = (value - 1) / N;                int targetY = (value - 1) % N;                distance += Math.abs(i - targetX) + Math.abs(j - targetY);            }        }    }    return distance;}

现在，代码可以工作并找到拼图的解（拼图状态是一个N*N的值数组，目标状态是[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]（对于N=3），空白格为0），但是与其他程序（使用相同算法和相同启发式）的结果相比，我的程序扩展了不同数量的节点。我认为通用图搜索中存在问题…有什么想法吗？ :D谢谢！！！

回答：

你的启发式计算有误。假设9位于你的棋盘的索引4处。你计算它的rowRight值为3而不是2。这会导致你的算法性能不佳。你的row right计算应该是：

int rowRight = (valueFound - 1) / N;