如何提高 A-Star 算法的性能？

Question

我已经实现了 A-Star 算法，但没有得到预期的性能，我该如何提高算法的性能。

下面是在while循环中调用直到到达目标节点的主函数，这是单向AStar实现。

public void step(boolean useQueueOnly) {
        count ++;
        m_fixedNodeId = m_nextNodeId;
        m_fixedCost = m_nextCost;
        int fromNodeId = m_current.getPrevNodeId();

        int arcId = m_network.getFirstArc(m_fixedNodeId);
        while (arcId != Integer.MIN_VALUE) {
            int nextNodeId = m_network.getBegNodeId(arcId);
            if (nextNodeId == m_fixedNodeId) {
                nextNodeId = m_network.getEndNodeId(arcId);
            }
            int arcCost;
            if (m_forwardDirection) {
                arcCost = m_network.getCost(arcId, m_fixedNodeId, fromNodeId);
            } else {
                arcCost = m_network.getCost(arcId, nextNodeId, fromNodeId);
            }

            arcCost = Math.max(MIN_COST_ALLOWED, arcCost);

            if (arcCost != Integer.MAX_VALUE) {
                int newNodeCost = (int) Math.min((long) m_fixedCost + arcCost,
                        Integer.MAX_VALUE);

                int nodePrevCost  = fromMap.get(nextNodeId) != null ? fromMap.get(nextNodeId).getCost() : Integer.MAX_VALUE;

                double approxCost = newNodeCost + m_approximator.approximate(nextNodeId);

                AStarEntry ase = new AStarEntry(nextNodeId, approxCost, arcId, m_current, m_fixedNodeId, newNodeCost);

                if ((nodePrevCost == Integer.MAX_VALUE) &&
                        (newNodeCost != Integer.MAX_VALUE)) {
                    //haven't yet reached this node.
                    if(fromMap.get(nextNodeId) == null){
                        fromMap.put(nextNodeId, ase);
                        m_priorityNodeQueue.add(ase);
                    }

                } else if (newNodeCost < nodePrevCost) {
                    //already reached this node.
                    m_priorityNodeQueue.remove(ase);

                }
            }
            arcId = m_network.getNextArc(m_fixedNodeId, arcId);
        }

        m_current = m_priorityNodeQueue.poll();
        m_nextNodeId = m_current.getNodeId();
        m_nextCost = m_current.getCost();

}

这是我在优先级队列中使用的 class。

class AStarEntry implements Cloneable, Comparable<AStarEntry>{

    public double m_weight;
    public int m_nodeId;
    public int m_arcId;
    public int m_prevNodeId;
    public int m_cost;

    public AStarEntry m_parent;

    public AStarEntry(int nodeId, double weight, int arcId, AStarEntry parent, int prevNodeId, int cost) {
        m_nodeId = nodeId;
        m_weight = weight;
        m_arcId = arcId;
        m_parent = parent;
        m_prevNodeId = prevNodeId;
        m_cost = cost;
    }

    @Override
    public int compareTo(AStarEntry o) {

        // assumption no NaN and no -0        
        return m_weight > o.m_weight ? +1 : m_weight < o.m_weight ? -1 : 0;
    }

    public double getWeight() {
        return m_weight;
    }

    public int getNodeId() {
        return m_nodeId;
    }

    public int getArcId() {
        return m_arcId;
    }

    public AStarEntry getParent() {
        return m_parent;
    }

    public int getPrevNodeId() {
        return m_prevNodeId;
    }

    public int getCost() {
        return m_cost;
    }

    @Override
    public String toString() {

        return m_nodeId + " (" + m_arcId + ") weight: " + m_weight;
    }
}

我无法找出性能不佳的原因，请帮我找出一个。

Answer 1

在找到解决方案之前，您应该检查探索了多少个节点。

你可以尝试改进你的overestimation-function（启发式）剩余路径的成本以减少探索节点的数量。

一般来说，A* 算法的性能主要取决于您使用的启发式算法，而不是真正的代码优化。因此，请尝试将尽可能多的领域知识放入您的启发式中，以减少探索节点的数量。

如何提高 A-Star 算法的性能？

How can i improve performance of the A-Star algorithm?

java

algorithm

a-star

graph-algorithm