我目前正在研究 A* Algorithm 的实现两个节点之间的距离不规则。包含节点的图是有向加权图。每个节点都至少连接到一个其他节点，也可能存在不同距离的对称连接。节点只是一个标签，不包含任何特殊信息

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

我的 A* 算法实现主要由 2 个类组成，算法本身的类 (AStar) 和节点的类 (Node)。该代码主要基于维基百科伪代码。

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());
        }
    }
}

最佳答案

在尝试为您的问题定义启发式函数之前，请考虑在许多情况下，使用不良(或不正确)的目标成本估计与根本不使用启发式一样会弄巧成拙。

在带有加权弧的图的情况下，您需要考虑节点中是否有一些信息可以导致获得启发值(例如，如果您的节点是城市，一个好的估计可以是长度它们之间的直线；或者如果您的节点是数组，则它们之间的相似性度量)。如果您的节点只是标签并且没有可用于获取启发式值的信息，那么最好的解决方案可能是根本不使用启发式。对于大多数此类问题，这还不是最糟糕的情况。最好使用 Dijkstra 搜索(与 A* 相同，但使用 heuristic=0)，让算法从一开始就根据成本扩展节点，而不是使用不一致的坏启发式，因为在这个在这种情况下，您可能会根据对目标成本的错误估计来扩展看似有前途的不必要节点。

我不知道您的图表有多大，但对于大多数问题，使用启发式算法和根本不使用启发式算法在计算时间上没有显着差异。特别是在错误启发式的情况下。

我可以看到您有自己的 A* 实现。我建议你看一下像 Hipster 这样的启发式搜索库。 .该库允许您定义图表并测试不同的搜索算法，以了解最适合您问题的算法。一些代码示例准确地描述了您的情况:在加权有向图中搜索。它可能对您的问题有用。

希望我的回答对您有所帮助。问候，

关于java - 节点间距离不规则的 A* 算法启发式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27249023/