java - AI:使用曼哈顿启发式技术进行图搜索和A *实现

This is my project佛罗伦萨大学的AI课程。我必须解决一个经典的游戏：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();
}

@Override
public 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;
}

@Override
public void setHeuristic(Heuristic heuristic) {
    this.heuristic = heuristic;
}

@Override
protected 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;
        }
    });
}

}

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

    @Override
public 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。这将导致算法的最佳性能。您的右行计算应为：

int rowRight = (valueFound - 1) / N;

关于java - AI:使用曼哈顿启发式技术进行图搜索和A *实现，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16664676/