A Star in Javascript

Gepostet: , Zuletzt aktualisiert:

/**
 * Finds the shortest distance between two nodes using the A-star (A*) algorithm
 * @param graph an adjacency-matrix-representation of the graph where (x,y) is the weight of the edge or 0 if there is no edge.
 * @param heuristic an estimation of distance from node x to y that is guaranteed to be lower than the actual distance. E.g. straight-line distance
 * @param start the node to start from.
 * @param goal the node we're searching for
 * @return The shortest distance to the goal node. Can be easily modified to return the path.
 */
const aStar = function (graph, heuristic, start, goal) {

    //This contains the distances from the start node to all other nodes
    var distances = [];
    //Initializing with a distance of "Infinity"
    for (var i = 0; i < graph.length; i++) distances[i] = Number.MAX_VALUE;
    //The distance from the start node to itself is of course 0
    distances[start] = 0;

    //This contains the priorities with which to visit the nodes, calculated using the heuristic.
    var priorities = [];
    //Initializing with a priority of "Infinity"
    for (var i = 0; i < graph.length; i++) priorities[i] = Number.MAX_VALUE;
    //start node has a priority equal to straight line distance to goal. It will be the first to be expanded.
    priorities[start] = heuristic[start][goal];

    //This contains whether a node was already visited
    var visited = [];

    //While there are nodes left to visit...
    while (true) {

        // ... find the node with the currently lowest priority...
        var lowestPriority = Number.MAX_VALUE;
        var lowestPriorityIndex = -1;
        for (var i = 0; i < priorities.length; i++) {
            //... by going through all nodes that haven't been visited yet
            if (priorities[i] < lowestPriority && !visited[i]) {
                lowestPriority = priorities[i];
                lowestPriorityIndex = i;
            }
        }

        if (lowestPriorityIndex === -1) {
            // There was no node not yet visited --> Node not found
            return -1;
        } else if (lowestPriorityIndex === goal) {
            // Goal node found
            // console.log("Goal node found!");
            return distances[lowestPriorityIndex];
        }

        // console.log("Visiting node " + lowestPriorityIndex + " with currently lowest priority of " + lowestPriority);

        //...then, for all neighboring nodes that haven't been visited yet....
        for (var i = 0; i < graph[lowestPriorityIndex].length; i++) {
            if (graph[lowestPriorityIndex][i] !== 0 && !visited[i]) {
                //...if the path over this edge is shorter...
                if (distances[lowestPriorityIndex] + graph[lowestPriorityIndex][i] < distances[i]) {
                    //...save this path as new shortest path
                    distances[i] = distances[lowestPriorityIndex] + graph[lowestPriorityIndex][i];
                    //...and set the priority with which we should continue with this node
                    priorities[i] = distances[i] + heuristic[i][goal];
                    // console.log("Updating distance of node " + i + " to " + distances[i] + " and priority to " + priorities[i]);
                }
            }
        }

        // Lastly, note that we are finished with this node.
        visited[lowestPriorityIndex] = true;
        //console.log("Visited nodes: " + visited);
        //console.log("Currently lowest distances: " + distances);

    }
};

module.exports = {aStar};

Über den Algorithmus und die Programmiersprache in diesem Snippet:

A Star

Der A-Stern-Algorithmus (A & ast;) ist ein Algorithmus, der verwendet wird, um das Problem des kürzesten Pfades in einem Graphen zu lösen. Dies bedeutet, dass bei einer Anzahl von Knoten und den Kanten zwischen ihnen sowie der “Länge” der Kanten (als “Gewicht” bezeichnet) und einer Heuristik (dazu später mehr) die A & ast; Der Algorithmus findet den kürzesten Weg vom angegebenen Startknoten zu allen anderen Knoten.

Beschreibung des Algorithmus

Das Grundprinzip des A-Stern-Algorithmus (A & ast;) besteht darin, den Knoten mit der aktuell kleinsten Priorität (der kürzesten Entfernung vom Start plus der Heuristik zum Ziel) iterativ zu betrachten und alle noch nicht besuchten Nachbarn zu aktualisieren, wenn der Pfad dazu über ist der aktuelle Knoten kürzer. Dies ist dem Dijkstra-Algorithmus sehr ähnlich, mit dem Unterschied, dass der Knoten mit der niedrigsten Priorität als nächstes besucht wird und nicht der Knoten mit der kürzesten Entfernung. Im Wesentlichen verwendet Dijkstra die Entfernung als Priorität, während A & ast; verwendet den Abstand plus der Heuristik.

Warum ist das Hinzufügen der Heuristik sinnvoll? Ohne sie hat der Algorithmus keine Ahnung, ob er in die richtige Richtung geht. Bei der manuellen Suche nach dem kürzesten Pfad in diesem Beispiel haben Sie wahrscheinlich Pfade nach rechts gegenüber Pfaden nach oben oder unten priorisiert. Dies liegt daran, dass sich der Zielknoten rechts vom Startknoten befindet, sodass das Gehen nach rechts zumindest im Allgemeinen die richtige Richtung ist. Die Heuristik gibt dem Algorithmus diese räumlichen Informationen.

Wenn also ein Knoten die derzeit kürzeste Entfernung hat, aber im Allgemeinen in die falsche Richtung geht, während Dijkstra diesen Knoten als nächstes besucht hätte, wird A Star dies nicht tun. Damit dies funktioniert, muss die Heuristik zulässig sein, was bedeutet, dass sie die tatsächlichen Kosten (d. H. Die Entfernung) niemals überschätzen darf - was beispielsweise für die geradlinige Entfernung in Straßennetzen der Fall ist. Intuitiv übersieht der Algorithmus auf diese Weise niemals einen kürzeren Pfad, da die Priorität immer niedriger als die tatsächliche Entfernung ist (Wenn der aktuell kürzeste Pfad A ist, wird Pfad B untersucht, wenn er auf irgendeine Weise kürzer sein könnte.) Eine einfache Heuristik, die diese Eigenschaft erfüllt, ist die geradlinige Entfernung (z. B. in einem Straßennetz).

Im Einzelnen führt dies zu den folgenden Schritten:

  1. Initialisieren Sie den Abstand zum Startknoten als 0 und den Abstand zu allen anderen Knoten als unendlich
  2. Initialisieren Sie die Priorität zum Startknoten als geradlinigen Abstand zum Ziel und die Prioritäten aller anderen Knoten als unendlich
  3. Setzen Sie alle Knoten auf “nicht besucht”.
  4. Während wir nicht alle Knoten besucht und den Zielknoten nicht gefunden haben:     1. Suchen Sie den Knoten mit der aktuell niedrigsten Priorität (beim ersten Durchgang ist dies der Quellknoten selbst).     1. Wenn es sich um den Zielknoten handelt, geben Sie dessen Entfernung zurück     1. Überprüfen Sie für alle Knoten daneben, die wir noch nicht besucht haben, ob die derzeit kleinste Entfernung zu diesem Nachbarn größer ist, als wenn wir über den aktuellen Knoten gehen würden     1. Wenn dies der Fall ist, aktualisieren Sie die kleinste Entfernung dieses Nachbarn auf die Entfernung von der Quelle zum aktuellen Knoten plus die Entfernung vom aktuellen Knoten zu diesem Nachbarn und aktualisieren Sie die Priorität auf die Entfernung plus die geradlinige Entfernung zu der Zielknoten

Beispiel des Algorithmus

Betrachten Sie das folgende Diagramm: Grafik für den A-Star-Algorithmus (A & ast;) für kürzeste Wege

Die Schritte, die der Algorithmus in diesem Diagramm ausführt, wenn Knoten 0 als Startpunkt und Knoten 5 als Ziel in der angegebenen Reihenfolge angegeben werden, sind:

  1. Besuch des Knotens 0 mit der derzeit niedrigsten Priorität von 8,0
  2. Aktualisieren der Entfernung von Knoten 1 bis 3 und der Priorität auf 9.32455532033676
  3. Aktualisieren der Entfernung von Knoten 2 bis 4 und der Priorität auf 10.32455532033676
  4. Besuch von Knoten 1 mit der derzeit niedrigsten Priorität von 9.32455532033676
  5. Aktualisieren der Entfernung von Knoten 3 auf 9 und der Priorität auf 11.82842712474619
  6. Aktualisieren der Entfernung von Knoten 4 auf 13 und der Priorität auf 15.82842712474619
  7. Besuch von Knoten 2 mit der derzeit niedrigsten Priorität von 10.32455532033676
  8. Besuch von Knoten 3 mit der derzeit niedrigsten Priorität von 11.82842712474619
  9. Aktualisieren der Entfernung von Knoten 5 auf 12 und der Priorität auf 12.0
  10. Zielknoten gefunden!

Endgültig niedrigster Abstand von Knoten 0 zu Knoten 5: 12

Laufzeit des Algorithmus

Die Laufzeitkomplexität von A Star hängt davon ab, wie es implementiert wird. Wenn ein Min-Heap verwendet wird, um den nächsten zu besuchenden Knoten zu bestimmen, und die Adjazenz unter Verwendung von Adjazenzlisten implementiert wird, ist die Laufzeit O(| E | + | V | log | V|) (|V| = Nummer Anzahl der Knoten, |E| = Anzahl der Kanten). Wenn wir einfach alle Entfernungen durchsuchen, um den Knoten mit der niedrigsten Entfernung in jedem Schritt zu finden, und mithilfe einer Matrix nachsehen, ob zwei Knoten benachbart sind, steigt die Laufzeitkomplexität auf O(| V | ^ 2).

Beachten Sie, dass dies dasselbe ist wie bei Dijkstra. In der Praxis können jedoch bei Auswahl einer guten Heuristik viele der Pfade eliminiert werden, bevor sie untersucht werden, was zu einer signifikanten Zeitverbesserung führt.

Weitere Informationen darüber, wie die Heuristik die Komplexität beeinflusst, finden Sie im Wikipedia-Artikel.

Speicherkomplexität des Algorithmus

Die Speicherplatzkomplexität von A Star hängt davon ab, wie es ebenfalls implementiert ist, und entspricht der Laufzeitkomplexität sowie dem für die Heuristik erforderlichen Speicherplatz.

JavaScript

JavaScript ist eine interpretierte Skriptsprache, die zuvor hauptsächlich in Webseiten verwendet wurde (die in Browsern ausgeführt werden) und seitdem über node.js auch für Back-End- und andere Aufgaben beliebt ist

Während es einen Großteil seiner Syntax von Java entlehnt, ist es eine ganz andere Sprache und sollte nicht verwechselt werden.

Getting to “Hello World” in JavaScript

Das Wichtigste zuerst - hier erfahren Sie, wie Sie Ihre erste Codezeile in JavaScript ausführen können. Wenn Sie JavaScript für das Backend verwenden möchten, lesen Sie das Kapitel zum Drucken von Hello World mit Node.js. Wenn Sie JavaScript im Frontend (d. H. Auf Webseiten) verwenden möchten, lesen Sie das Kapitel zum Drucken von Hello World im Browser.

Getting to “Hello World” in JavaScript using the browser

  1. Erstellen Sie eine Datei mit dem Namen hello_world.html
  2. Öffnen Sie es mit einem Texteditor (z. B. Sublime Text oder nur mit dem Standard-Windows-Editor).
  3. Fügen Sie den folgenden Codeausschnitt ein:
<html>
<head>
    <script type="application/javascript">
        // This prints to the browsers console
        console.log("Hello World")
        // This opens a popup
        alert("Hello world")
    </script>
</head>
<body>
    (Website content)
</body>
</html>
  1. Öffnen Sie diese Datei mit Ihrem Browser (indem Sie den Speicherort in die Adressleiste eingeben).
  2. Sie sollten ein Popup mit der Aufschrift “Hallo Welt” sehen.
  3. Wenn Sie die Browserkonsole verwenden (z. B. in Chrome: Rechtsklick -> Überprüfen), wird diese auch dort gedruckt.

Der Grund, warum wir das Skript in HTML verpacken, ist, dass der Browser das JavaScript ansonsten nicht ausführt, sondern nur dessen Inhalt anzeigt.

Getting to “Hello World” in JavaScript using Node.js

  1. Laden Sie die neueste Version von Node.js von nodejs.org herunter und installieren Sie sie. Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert.
  2. Öffnen Sie ein Terminal und stellen Sie sicher, dass der Befehl node funktioniert. Wenn der Fehler “Befehl nicht gefunden” (oder ähnlich) angezeigt wird, starten Sie die Befehlszeile und, falls dies nicht hilft, Ihren Computer neu. Wenn das Problem weiterhin besteht, finden Sie hier einige hilfreiche Fragen zu StackOverflow für jede Plattform:

  3. Sobald dies funktioniert, kopieren Sie das folgende Snippet in eine Datei mit dem Namen hello_world.js:

    console.log("Hello World");
  4. Wechseln Sie das Verzeichnis, indem Sie “cd path / to / helloworld” eingeben und dann “node helloworld.js” ausführen. Dies sollte “Hello World” auf Ihrem Terminal drucken.

Das ist es! Beachten Sie, dass die Eintrittsbarriere ähnlich niedrig ist wie bei Python und vielen anderen Skriptsprachen.

Fundamentals in JavaScript

Um in JavaScript implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen. Jedes der folgenden Snippets kann mit Node.js einzeln ausgeführt werden, da kein Boilerplate erforderlich ist. Im Browser muss der Code wie im Hello World-Beispiel für den oben gezeigten Browser von HTML umgeben sein.

Variables and Arithmetic

Variablen in JavaScript werden dynamisch typisiert, dh der Inhalt einer Variablen wird zur Laufzeit festgelegt und muss beim Schreiben des Codes nicht angegeben werden.

var number = 5;
var decimalNumber = 3.25;
var result = number * decimalNumber;
var callout = "The number is ";
// In this instance, the values are concatenated rather than added because one of them is a String.
console.log(callout + result);

Dies wird “The number is 16.25” drucken.

Arrays

Arrays in JavaScript werden als Objekte implementiert, wobei der Index nur der Name der Eigenschaft ist. Dies macht sie dynamisch dimensioniert. Die gesamten Konzepte von Objekten und Arrays werden in JavaScript zusammengeführt, wie das folgende Snippet zeigt.

var integers = {}; // initialized as object
integers[3] = 42; // assigned using array index
console.log(integers["3"]); // Accessed using property name, prints "42"

var strings = ["Hello"]; // strings[0] is now Hi
strings[2] = "World"; // index 1 skipped
strings.beautiful = "Beautiful" // Assigned using property name

console.log(strings[0] + " " + strings["beautiful"] + " " + strings[2]); // Prints "Hello World"

Conditions

Wie die meisten Programmiersprachen kann JavaScript “if-else” -Anweisungen ausführen. Darüber hinaus kann JavaScript auch “switch-case” -Anweisungen ausführen.

var value = 5;
if(value === 5){
    console.log("Value is 5");
} else if(value < 5){
    console.log("Value is less than 5");
} else {
    console.log("Value is something else");
}

switch (value){
    case 1:
        console.log("Value is 1");
        break; // Don't go further down the cases
    case 2:
        console.log("Value is 2");
        break; // Don't go further down the cases
    case 3:
        console.log("Value is 3");
        break; // Don't go further down the cases
    case 4:
        console.log("Value is 4");
        break; // Don't go further down the cases
    case 5:
        console.log("Value is 5");
        break; // Don't go further down the cases
    default:
        console.log("Value is something else");
}

Der obige JavaScript-Code gibt zweimal “Wert ist 5” aus.

Schleifen

JavaScript unterstützt sowohl for-, while- als auch do while-Schleifen. Die Anweisungen break undcontinue werden ebenfalls unterstützt. Das folgende Beispiel zeigt die Unterschiede:

var value = 2;
for (var i = 0; i < value; i++) {
    console.log(i);
}
while (value > 0) {
    console.log(value);
    value--;
}
do {
    console.log(value);
    value--;
} while (value > 0);

Dadurch wird Folgendes auf das Terminal gedruckt:

0
1
2
1
0

Beachten Sie die letzte “0”: Sie wird gedruckt, weil in der “do-while” -Schleife im Vergleich zur “while” -Schleife. Der Codeblock wird mindestens einmal ausgeführt, bevor die Bedingung überprüft wird.

Funktionen

Funktionen in JavaScript können mit vielen verschiedenen Syntaxen deklariert werden, z. B. als Objekteigenschaften, als Variablen oder in neueren JavaScript-Versionen als Teil einer Klasse.

Hier ist ein Beispiel für eine JavaScript-Funktion als Variable:

var my_function = function(){
    console.log("Hello World")
}

my_function()

Hier ist ein Beispiel für eine JavaScript-Funktion als Objekteigenschaft:

var function_object = {}
function_object.my_function = function(){
    console.log("Hello World")
}

function_object.my_function()

Und hier ist ein Beispiel für den Aufruf einer Funktion eines Objekts einer Klasse:

class FunctionClass {
    my_function(){
        console.log("Hello World")
    }
}

new FunctionClass().my_function();

(Alle diese Beispiele drucken “Hello World”.)

Syntax

Wie bereits erwähnt, teilt JavaScript einen Großteil seiner Syntax mit Java. JavaScript erfordert die Verwendung von geschweiften Klammern ({}), um Codeblöcke in Bedingungen, Schleifen, Funktionen usw.; Es sind nicht immer Semikolons am Ende von Anweisungen erforderlich, aber ihre Verwendung wird empfohlen, da ihre Verwendung bedeutet, dass die Verwendung von Leerzeichen für die bevorzugte Formatierung (z. B. Einrücken von Codeteilen) den Code nicht beeinflusst.

Fortgeschrittenes Wissen in JavaScript

JavaScript wurde erstmals 1993 veröffentlicht und ist ein Multi-Paradigma.

Es ist in erster Linie ereignisgesteuert und funktional, folgt aber auch objektorientierten und imperativen Paradigmen. Es ist dynamisch typisiert, bietet jedoch in neueren Versionen und Dialekten wie TypeScript eine gewisse statische Typisierung. Für weitere Informationen hat JavaScript einen großartigen Artikel Wikipedia.