java - 如何模块化 A* 中的启发式(运行时启发式)

Question

我想使用 strategy pattern在我的 A* 实现中模块化启发式，但在分离它时遇到了一些麻烦。我尝试使用 Comparator 初始化我的优先级队列，该Comparator 以下列方式使用我的启发式方法:

public AStarSearch(Graph g, AStarHeuristic heuristic) {
        this.heuristic = heuristic;
        this.open = new PriorityQueue<Node>(10, new Comparator<Node>(){
            @Override
            public int compare(Node n1, Node n2) {
                int fScoreOne = n1.getTotalPathWeight() + heuristic.calculate(n1, open);
                int fScoreTwo = n1.getTotalPathWeight() + heuristic.calculate(n1, open);
                if (fScoreOne < fScoreTwo)
                    return 1;
                else if (fScoreOne > fScoreTwo)
                    return -1;
                return 0;
            }
        });
    }

但我得到:“无法引用非最终变量启发式内部和以不同方法定义的内部类。”

我在加权完整图上运行它，计划使用基本启发式方法向开放集中最近的节点移动(我没有目标节点，只有一组需要访问的节点).当然，为了在开放集中找到一个节点的最小权重边，我需要开放节点的列表/队列和当前节点(它有一个边列表)，所以我做了 Heuristic 接口(interface)如下:

public interface AStarHeuristic {
    public int calculate(Node curr, Queue<Node> open);
}

我怎样才能分离出我的启发式，以便它可以在运行时用于对我的队列进行排序？

Answer 1

这里的问题是您正在创建一个匿名内部类，并试图在调用函数中引用一个局部变量(此处，heuristic)。为此，Java 要求将变量标记为 final。如果您尝试将方法更改为

public AStarSearch(Graph g, final AStarHeuristic heuristic) {
     // ... Same as before ...
}

问题应该消失了。

希望这对您有所帮助!