具有节点之间不规则距离的A*算法的启发式算法

Question

我目前正致力于实现A*算法,两个节点之间的距离不规则.包含节点的图是定向和加权图.每个节点连接到至少一个其他节点,也可以存在具有不同距离的对称连接.节点只不过是一个标签,不包含任何特殊信息

我需要的是一种启发式方法,以确定从任何节点A到另一个节点B的最短路径尽可能准确.我尝试使用一种启发式方法来返回到节点最近邻居的距离,但当然这并不像没有启发式算法那样有效(= Dijkstra).

---

我对A*算法的实现主要包括2个类,算法本身的类(AStar)和节点(Node)的类.该代码主要基于Wikipedia伪代码.

源代码 AStar.java

public class AStar {
    private AStar() {}

    private static Node[] reconstructPath(Map<Node, Node> paths, Node current) {
        List<Node> path = new ArrayList<Node>();
        path.add(0, current);
        while (paths.containsKey(current)) {
            current = paths.get(current);
            path.add(0, current);
        }
        return path.toArray(new Node[0]);
    }

    public static Node[] calculate(Node start, Node target, IHeuristic heuristic) {
        List<Node> closed = new ArrayList<Node>();
        PriorityQueue<Node> open = new PriorityQueue<Node>();
        Map<Node, Double> g_score = new HashMap<Node, Double>();
        Map<Node, Double> f_score = new HashMap<Node, Double>();
        Map<Node, Node> paths = new HashMap<Node, Node>();

        g_score.put(start, 0d);
        f_score.put(start, g_score.get(start) + heuristic.estimateDistance(start, target));
        open.set(start, f_score.get(start));

        while (!open.isEmpty()) {
            Node current = null;

            // find the node with lowest f_score value
            double min_f_score = Double.POSITIVE_INFINITY;
            for (Entry<Node, Double> entry : f_score.entrySet()) {
                if (!closed.contains(entry.getKey()) && entry.getValue() < min_f_score) {
                    min_f_score = entry.getValue();
                    current = entry.getKey();
                }
            }

            if (current.equals(target)) return reconstructPath(paths, target);

            open.remove(current);
            closed.add(current);

            for (Node neighbor : current.getAdjacentNodes()) {
                if (closed.contains(neighbor)) {
                    continue;
                }
                double tentative_g_score = g_score.get(current) + current.getDistance(neighbor);

                if (!open.contains(neighbor) || tentative_g_score < g_score.get(neighbor)) {
                    paths.put(neighbor, current);
                    g_score.put(neighbor, tentative_g_score);
                    f_score.put(neighbor, g_score.get(neighbor) + heuristic.estimateDistance(neighbor, target));
                    if (!open.contains(neighbor)) {
                        open.set(neighbor, f_score.get(neighbor));
                    }
                }
            }
        }
        throw new RuntimeException("no path between " + start + " and " + target);
    }
}

源代码 Node.java

public class Node {
    private Map<Node, Double> distances = new HashMap<Node, Double>();

    public final String       name;

    public Node(String name) {
        this.name = name;
    }

    public Set<Node> getAdjacentNodes() {
        return Collections.unmodifiableSet(distances.keySet());
    }

    public double getDistance(Node node) {
        return distances.get(node);
    }

    public void setDistance(Node node, double distance) {
        distances.put(node, distance);
    }

    @Override
    public String toString() {
        return (name == null ? "Node@" + Integer.toHexString(hashCode()) : name);
    }
}

源代码 PriorityQueue.java

public class PriorityQueue<T> {
    transient ArrayList<PriorityEntry<T>> elements     = null;

    private static final int              DEFAULT_SIZE = 10;

    public PriorityQueue() {
        elements = new ArrayList<PriorityEntry<T>>(DEFAULT_SIZE);
    }

    public PriorityQueue(int initialCapacity) {
        elements = new ArrayList<PriorityEntry<T>>(initialCapacity);
    }

    public boolean push(T element, double priority) {
        PriorityEntry<T> entry = new PriorityEntry<T>(element, priority);
        if (elements.contains(entry)) return false;
        elements.add(entry);
        elements.sort(null);
        return true;
    }

    public void set(T element, double priority) {
        PriorityEntry<T> entry = new PriorityEntry<T>(element, priority);
        int index = elements.indexOf(entry);
        if (index >= 0) {
            elements.get(index).setPriority(priority);
        } else {
            elements.add(entry);
        }
        elements.sort(null);
    }

    public T peek() {
        return size() <= 0 ? null : elements.get(0).getValue();
    }

    public T pop() {
        return size() <= 0 ? null : elements.remove(0).getValue();
    }

    public boolean remove(T element) {
        return elements.remove(new PriorityEntry<T>(element, 0));
    }

    public int size() {
        return elements.size();
    }

    public boolean isEmpty() {
        return elements.isEmpty();
    }

    public boolean contains(T element) {
        return elements.contains(new PriorityEntry<T>(element, 0));
    }

    private class PriorityEntry<E> implements Comparable<PriorityEntry<? extends T>> {
        private final E value;
        private double  priority = Double.MIN_VALUE;

        public PriorityEntry(E value, double priority) {
            this.value = value;
            this.priority = priority;
        }

        public E getValue() {
            return value;
        }

        public double getPriority() {
            return priority;
        }

        public void setPriority(double priority) {
            this.priority = priority;
        }

        @Override
        @SuppressWarnings("unchecked")
        public boolean equals(Object o) {
            if (!(o instanceof PriorityEntry)) return false;
            PriorityEntry<?> entry = (PriorityEntry<?>) o;
            return value.equals(entry);
        }

        @Override
        public int compareTo(PriorityEntry<? extends T> entry) {
            return (int) (getPriority() - entry.getPriority());
        }
    }
}

Answer 1

添加到上面的@kiheru 评论。您的解决方案只会与所提供的启发式一样好。

如果以下行和 heuristic.estimate 的范围太窄。该算法将很快达到局部最小值。或者，如果启发法不可接受，则算法将导致无解或不正确的随机解。

    f_score.put(start, g_score.get(start) + heuristic.estimateDistance(start, target));

仔细看看你的启发式并确认它是可接受的。如果可以接受，则可能需要改进以提供更准确的估计。