Ein * Suchalgorithmus

69793
JavaDeveloper

NodeDataspeichert alle Informationen des Knotens, die der AStar Algorithmus benötigt . Diese Informationen umfassen den Wert von g, hund f. Der Wert aller 3 Variablen ist jedoch von Quelle und Ziel abhängig und wird daher zur Laufzeit abgerufen.

@param <T>

Ich bin auf der Suche nach Bewertungen zu Optimierung, Genauigkeit und Best Practices.

final class NodeData<T> { 

    private final T nodeId;
    private final Map<T, Double> heuristic;

    private double g;  // g is distance from the source
    private double h;  // h is the heuristic of destination.
    private double f;  // f = g + h 

    public NodeData (T nodeId, Map<T, Double> heuristic) {
        this.nodeId = nodeId;
        this.g = Double.MAX_VALUE; 
        this.heuristic = heuristic;
    }

    public T getNodeId() {
        return nodeId;
    }

    public double getG() {
        return g;
    }

    public void setG(double g) {
        this.g = g;
    }

    public void calcF(T destination) {
        this.h = heuristic.get(destination);
        this.f = g + h;
    } 

    public double getH() {
        return h;
    }

    public double getF() {
        return f;
    }
 }

/**
 * The graph represents an undirected graph. 
 * 
 * @author SERVICE-NOW\ameya.patil
 *
 * @param <T>
 */
final class GraphAStar<T> implements Iterable<T> {
    /*
     * A map from the nodeId to outgoing edge.
     * An outgoing edge is represented as a tuple of NodeData and the edge length
     */
    private final Map<T, Map<NodeData<T>, Double>> graph;
    /*
     * A map of heuristic from a node to each other node in the graph.
     */
    private final Map<T, Map<T, Double>> heuristicMap;
    /*
     * A map between nodeId and nodedata.
     */
    private final Map<T, NodeData<T>> nodeIdNodeData;

    public GraphAStar(Map<T, Map<T, Double>> heuristicMap) {
        if (heuristicMap == null) throw new NullPointerException("The huerisic map should not be null");
        graph = new HashMap<T, Map<NodeData<T>, Double>>();
        nodeIdNodeData = new HashMap<T, NodeData<T>>();
        this.heuristicMap = heuristicMap;
    } 

    /**
     * Adds a new node to the graph.
     * Internally it creates the nodeData and populates the heuristic map concerning input node into node data.
     * 
     * @param nodeId the node to be added
     */
    public void addNode(T nodeId) {
        if (nodeId == null) throw new NullPointerException("The node cannot be null");
        if (!heuristicMap.containsKey(nodeId)) throw new NoSuchElementException("This node is not a part of hueristic map");

        graph.put(nodeId, new HashMap<NodeData<T>, Double>());
        nodeIdNodeData.put(nodeId, new NodeData<T>(nodeId, heuristicMap.get(nodeId)));
    }

    /**
     * Adds an edge from source node to destination node.
     * There can only be a single edge from source to node.
     * Adding additional edge would overwrite the value
     * 
     * @param nodeIdFirst   the first node to be in the edge
     * @param nodeIdSecond  the second node to be second node in the edge
     * @param length        the length of the edge.
     */
    public void addEdge(T nodeIdFirst, T nodeIdSecond, double length) {
        if (nodeIdFirst == null || nodeIdSecond == null) throw new NullPointerException("The first nor second node can be null.");

        if (!heuristicMap.containsKey(nodeIdFirst) || !heuristicMap.containsKey(nodeIdSecond)) {
            throw new NoSuchElementException("Source and Destination both should be part of the part of hueristic map");
        }
        if (!graph.containsKey(nodeIdFirst) || !graph.containsKey(nodeIdSecond)) {
            throw new NoSuchElementException("Source and Destination both should be part of the part of graph");
        }

        graph.get(nodeIdFirst).put(nodeIdNodeData.get(nodeIdSecond), length);
        graph.get(nodeIdSecond).put(nodeIdNodeData.get(nodeIdFirst), length);
    }

    /**
     * Returns immutable view of the edges
     * 
     * @param nodeId    the nodeId whose outgoing edge needs to be returned
     * @return          An immutable view of edges leaving that node
     */
    public Map<NodeData<T>, Double> edgesFrom (T nodeId) {
        if (nodeId == null) throw new NullPointerException("The input node should not be null.");
        if (!heuristicMap.containsKey(nodeId)) throw new NoSuchElementException("This node is not a part of hueristic map");
        if (!graph.containsKey(nodeId)) throw new NoSuchElementException("The node should not be null.");

        return Collections.unmodifiableMap(graph.get(nodeId));
    }

    /**
     * The nodedata corresponding to the current nodeId.
     * 
     * @param nodeId    the nodeId to be returned
     * @return          the nodeData from the 
     */ 
    public NodeData<T> getNodeData (T nodeId) {
        if (nodeId == null) { throw new NullPointerException("The nodeid should not be empty"); }
        if (!nodeIdNodeData.containsKey(nodeId))  { throw new NoSuchElementException("The nodeId does not exist"); }
        return nodeIdNodeData.get(nodeId);
    }

    /**
     * Returns an iterator that can traverse the nodes of the graph
     * 
     * @return an Iterator.
     */
    @Override public Iterator<T> iterator() {
        return graph.keySet().iterator();
    }
}

public class AStar<T> {

    private final GraphAStar<T> graph;


    public AStar (GraphAStar<T> graphAStar) {
        this.graph = graphAStar;
    }

    // extend comparator.
    public class NodeComparator implements Comparator<NodeData<T>> {
        public int compare(NodeData<T> nodeFirst, NodeData<T> nodeSecond) {
            if (nodeFirst.getF() > nodeSecond.getF()) return 1;
            if (nodeSecond.getF() > nodeFirst.getF()) return -1;
            return 0;
        }
    } 

    /**
     * Implements the A-star algorithm and returns the path from source to destination
     * 
     * @param source        the source nodeid
     * @param destination   the destination nodeid
     * @return              the path from source to destination
     */
    public List<T> astar(T source, T destination) {
        /**
         * http://stackoverflow.com/questions/20344041/why-does-priority-queue-has-default-initial-capacity-of-11
         */
        final Queue<NodeData<T>> openQueue = new PriorityQueue<NodeData<T>>(11, new NodeComparator()); 

        NodeData<T> sourceNodeData = graph.getNodeData(source);
        sourceNodeData.setG(0);
        sourceNodeData.calcF(destination);
        openQueue.add(sourceNodeData);

        final Map<T, T> path = new HashMap<T, T>();
        final Set<NodeData<T>> closedList = new HashSet<NodeData<T>>();

        while (!openQueue.isEmpty()) {
            final NodeData<T> nodeData = openQueue.poll();

            if (nodeData.getNodeId().equals(destination)) { 
                return path(path, destination);
            }

            closedList.add(nodeData);

            for (Entry<NodeData<T>, Double> neighborEntry : graph.edgesFrom(nodeData.getNodeId()).entrySet()) {
                NodeData<T> neighbor = neighborEntry.getKey();

                if (closedList.contains(neighbor)) continue;

                double distanceBetweenTwoNodes = neighborEntry.getValue();
                double tentativeG = distanceBetweenTwoNodes + nodeData.getG();

                if (tentativeG < neighbor.getG()) {
                    neighbor.setG(tentativeG);
                    neighbor.calcF(destination);

                    path.put(neighbor.getNodeId(), nodeData.getNodeId());
                    if (!openQueue.contains(neighbor)) {
                        openQueue.add(neighbor);
                    }
                }
            }
        }

        return null;
    }


    private List<T> path(Map<T, T> path, T destination) {
        assert path != null;
        assert destination != null;

        final List<T> pathList = new ArrayList<T>();
        pathList.add(destination);
        while (path.containsKey(destination)) {
            destination = path.get(destination);
            pathList.add(destination);
        }
        Collections.reverse(pathList);
        return pathList;
    }


    public static void main(String[] args) {
        Map<String, Map<String, Double>> hueristic = new HashMap<String, Map<String, Double>>();
        // map for A    
        Map<String, Double> mapA = new HashMap<String, Double>();
        mapA.put("A",  0.0);
        mapA.put("B", 10.0);
        mapA.put("C", 20.0);
        mapA.put("E", 100.0);
        mapA.put("F", 110.0);


        // map for B
        Map<String, Double> mapB = new HashMap<String, Double>();
        mapB.put("A", 10.0);
        mapB.put("B",  0.0);
        mapB.put("C", 10.0);
        mapB.put("E", 25.0);
        mapB.put("F", 40.0);


        // map for C
        Map<String, Double> mapC = new HashMap<String, Double>();
        mapC.put("A", 20.0);
        mapC.put("B", 10.0);
        mapC.put("C",  0.0);
        mapC.put("E", 10.0);
        mapC.put("F", 30.0);


        // map for X
        Map<String, Double> mapX = new HashMap<String, Double>();
        mapX.put("A", 100.0);
        mapX.put("B", 25.0);
        mapX.put("C", 10.0);
        mapX.put("E",  0.0);
        mapX.put("F", 10.0);

        // map for X
        Map<String, Double> mapZ = new HashMap<String, Double>();
        mapZ.put("A", 110.0);
        mapZ.put("B",  40.0);
        mapZ.put("C",  30.0);
        mapZ.put("E", 10.0);
        mapZ.put("F",  0.0);

        hueristic.put("A", mapA);
        hueristic.put("B", mapB);
        hueristic.put("C", mapC);
        hueristic.put("E", mapX);
        hueristic.put("F", mapZ);

        GraphAStar<String> graph = new GraphAStar<String>(hueristic);
        graph.addNode("A");
        graph.addNode("B");
        graph.addNode("C");
        graph.addNode("E");
        graph.addNode("F");

        graph.addEdge("A", "B",  10);
        graph.addEdge("A", "E", 100);
        graph.addEdge("B", "C", 10);
        graph.addEdge("C", "E", 10);
        graph.addEdge("C", "F", 30);
        graph.addEdge("E", "F", 10);

        AStar<String> aStar = new AStar<String>(graph);

        for (String path : aStar.astar("A", "F")) {
            System.out.println(path);
        }
    }
}
Antworten
25
Warum: if (! OpenQueue.contains (nachbar)) {openQueue.add (nachbar); } ist nur wenn `tentativeG <neighbourn.getG ()`? Tiziano Parriani vor 3 Jahren 0

4 Antworten auf die Frage

20
amon

Dies ist ein ziemlich guter und professionell aussehender Code. Es gibt viele kleine Aspekte, die ich wirklich mag:

  • Die Verwendung Collections.unmodifiableMapanstelle einer flachen Kopie ist brillant.
  • Die Verwendung eines Generikums nodeIdist clever und sorgt für einen eleganten Code.
  • Es gibt Eingangskontrollen in allen öffentlichen Methoden (na ja, es gibt einige Ausnahmen: nur die AStarund NodeDataKonstrukteuren, NodeComparator#compareund AStar#astarwerden nicht überprüft).
  • Sie nutzen leere Zeilen perfekt, um nicht zusammenhängende Blöcke zu trennen.

Es gab jedoch einige Aspekte, die dazu führten, dass der Code manchmal etwas schwerer zu befolgen war:

  • Fehlende Verkapselung einiger Teile wie heuristic: Was ist das Map<T, Map<T, Double>>? Kann ich für eine Heuristic<T>Instanz keine schönen selbstdokumentierenden Zugriffsmethoden haben?

  • Sequentielle Kopplung in NodeData: wann immer setGich auch anrufen muss calcF. Sie hätten es einfacher machen können, indem Sie return thisstatt voidMethoden eine dort einhaken, aber die wirkliche Lösung besteht darin, sie loszuwerden public calcFund privatestattdessen zu machen. Die NodeDataKlasse ist selbst dafür verantwortlich, ihre Invarianten beizubehalten, daher setGsollten alle Aufrufe von abhängig abhängige Felder aktualisieren.

  • Schlechte Benennung Die Buchstaben g, fund hhaben eine spezifische Bedeutung im Kontext von A * und sind in Ordnung hier. Natürlich wäre es besser gewesen, einen Link zur Wikipedia-Seite dieses Algorithmus hinzuzufügen, damit ein zukünftiger Betreuer verstehen kann, warum Sie ihn ganstelle von verwendet haben distance.

    Knoten haben jedoch keinen Abstand, Knoten oder Kanten haben Gewichte . Im Zusammenhang mit Optimierungsproblemen ist es auch üblich, von Kosten zu sprechen - einem Begriff, der in Ihrem Code nicht einmal vorkommt.

    Es heißt heuristicnicht hueristic. Tippfehler sind leicht zu korrigieren und sollten korrigiert werden, wenn sie noch jung sind (Der Ursprung des refererFelds in einer HTTP-Anforderung sollte hier angegeben werden).

  • Es gibt einige Formatierungsfehler. Das kann durch einen automatischen Formatierer leicht korrigiert werden. Verwenden Sie z. B. keine Klammern, wenn sich eine Bedingung in einer einzelnen Zeile befindet, z. B. durch das if (cond) { single_statement; }Entfernen der Klammern werden Leitungsgeräusche reduziert. Ansonsten könnten Sie die Aussage auch in eine eigene Zeile stellen.

    Einige Ihrer Zeilen sind zu lang und sollten aufgelöst werden (siehe auch den nächsten Tipp).

  • So lobenswert Ihre Eingabeüberprüfungen auch sind, sie wirken visuell aufgeräumt. Verstecken Sie sie hinter Hilfsmethoden, z. B. heuristic.assertContains(nodeId)oder vorzugsweise Assert.nonNull(nodeId, "node")(was eine ganze Klasse für die Eingabeprüfung voraussetzt). Argumente dagegen sind weniger nützliche Stack-Traces und verringerte Leistung (Methodenaufruf-Overhead, Compiler-Optimierungen sind schwieriger), aber Pro-Argumente enthalten mehr selbstdokumentierenden, prägnanten Code.

Weitere Hinweise:

  • In Ihrer Dokumentation wird nicht angegeben, was passiert, wenn vom Start zum Ziel kein Pfad vorhanden ist (z. B. wenn sich die Knoten in nicht verbundenen Untergraphen befinden). Die Implementierung ist hier ziemlich klar: A nullwird statt einer Liste zurückgegeben.

  • Der auf der A * Wikipedia-Seite angegebene Pseudocode verwendet eine etwas andere Bedingung zum Aktualisieren pathund möglicherweise Hinzufügen von Nachbarn zu openQueue:

    if (!openQueue.contains(neighbor) || tentativeG < neighbor.getG())`
    

    während Sie verwenden if (tentativeG < neighbor.getG()). Es kann sich lohnen, anhand einer autoritativen Quelle die korrekte Bedingung zu überprüfen.

  • Sie könnten zwischen TInstanzen und einem kontinuierlichen Bereich von ints an den Grenzen Ihrer Komponente übersetzen (mit anderen Worten: intern nodeIdwäre jedes eine ganze Zahl). Die Verwendung von Ganzzahlen ermöglicht effizientere Datenstrukturen wie Arrays. Dies würde die meisten MapSuchvorgänge entfernen, aber auch die NodeDataKlasse. Der Nachteil ist, dass Ihr Code danach wie C aussehen würde. Ich würde einfach die Transformation ausprobieren und sehen (a), ob es eine merkliche Leistungssteigerung gibt und (b) ob sich die erhöhte Hässlichkeit wirklich lohnt.

Der auf der A * Wikipedia-Seite angegebene Pseudocode verwendet eine etwas andere Bedingung für die Aktualisierung des Pfads und das Hinzufügen von Nachbarn zu openQueue. Es ist ein toller Fang, aber ich denke, mein `this.g = Double.MAX_VALUE;` kümmert sich darum. JavaDeveloper vor 6 Jahren 0
Lack of encapsulation of some parts like heuristic: What is this Map>? Can't I have nice self-documenting accessors for a Heuristic instance? - `very good point.` ,> JavaDeveloper vor 6 Jahren 0
6
Pablo R. Mier

Der Code scheint in Ordnung zu sein, aber meiner bescheidenen Meinung nach gibt es einige Dinge, die Ihren Code verbessern können:

  1. Warum hat jeder Knoten eine Heuristiktabelle? Es ist möglicherweise besser, nur den Knoten zu verwenden, um die Kosten und die Bewertung einzukapseln, lassen Sie den Algorithmus jedoch die fKosten für Sie berechnen .
  2. In ähnlicher Weise ist die fBerechnung in den Knoten eingebettet, aber auch im AStarAlgorithmus. Warum nicht eine andere Komponente zur Berechnung verwenden f? Lassen Sie den Knoten nur als "Container" der Daten fungieren. Ich denke, es ist viel besser, das fin dem AStareinzigen zu berechnen, anstatt eine ähnliche Berechnung im Nodeund im zu haben AStar:

            // You are calculating g here, why f is computed in the node?
            // Responsabilities of each component are not clear
            double distanceBetweenTwoNodes = neighborEntry.getValue();
            double tentativeG = distanceBetweenTwoNodes + nodeData.getG();
    
            if (tentativeG < neighbor.getG()) {
                neighbor.setG(tentativeG);
                neighbor.calcF(destination); // confusing
    
  3. AStarkann nur mit verwendet werden AStarGraph. Dieser Code ist etwas gebunden. Sie können stattdessen eine Funktion definieren, die die Nachfolger für einen Status berechnet, sodass Sie sie anstelle von verwenden graph.edgesFromkönnen transitions.from(state). Diese Funktion kann mit Ihrer Diagrammstruktur oder einem anderen Element berechnet werden.

Überprüfen Sie diese Implementierung, um einige dieser Ideen zu sehen. Sie erhalten möglicherweise einige Hinweise zur Implementierung einer noch besseren Version des A *.

3
mzivi

Ich mag Ihren Code, aber ich denke, dass es einen Fehler gibt: neighbor.setG(tentativeG)Aktualisieren Sie die Priorität eines Knotens, der möglicherweise bereits in openQueue eingefügt wurde. Letzteres ist ein Java PriorityQueue, das keine Prioritätsaktualisierungen unterstützt. Wenn Sie die Priorität eines Objekts in der Warteschlange ändern, ohne dessen Position zu ändern (in Ihrem Fall nach oben zu sichten), könnte dies die Struktur des Objekts beeinträchtigen. Damit Sie das Update sicher in einem Java durchführen können PriorityQueue, sollten Sie den Knoten (O (N)) entfernen, aktualisieren und wieder einfügen. In Bezug auf die Leistung zahlen Sie bereits ein O (N) (hier ist N das typische.) Größe des offenen Satzes) inopenQueue.contains(neighbor)So wird die Entfernung damit vergleichbar sein. Ich denke, Sie können dies verbessern, indem Sie beispielsweise die Überprüfung der Prioritätswarteschlange vermeiden, stattdessen jedoch die Buchhaltung für separate Hashs durchführen. Dies würde jedoch nicht das O (N) lösen, das Sie beim Entfernen eines Knotens vor dem Aktualisieren bezahlen müssen. Ein möglicher Ausweg könnte darin bestehen, den veralteten Knoten nicht einfach zu entfernen und einfach einen neuen Knoten mit der aktualisierten Priorität hinzuzufügen. Wenn Sie dies tun, stellen Sie sicher, dass Sie die close-Einstellung durch eine id anstatt mit dem Objekt selbst kennzeichnen, sodass beim Abfragen eines veralteten Knotens (der die gleiche ID des neueren hat, der bereits besucht wurde, da letzterer eine höhere Priorität hatte) es wird als bereits besucht klassifiziert. Die Kosten für diesen Ansatz sind, dass Sie im Allgemeinen eine längere Warteschlange haben, aber alle Operationen sind höchstens O (log (N)).

0
Tiziano Parriani

Warum:

if (!openQueue.contains(neighbor)) {
     openQueue.add(neighbor);
}

ist nur wenn tentativeG < neighbor.getG()?

In einem generischen A * -Pseudocode wird die Aktualisierung in jedem Fall durchgeführt.

Siehe zB bei Wikipedia

Ich habe versucht, den Code auszuführen, er findet die optimale Lösung nur "dank" des anderen von mzivi erwähnten Fehlers.