Iterative Tiefensuche in Javascript

Gepostet: , Zuletzt aktualisiert: 

var bottomReached = false; // Variable to keep track if we have reached the bottom of the tree

/**
 * Implementation of iterative deepening DFS (depth-first search) Algorithm to find the shortest path from a start to a target node..
 * Given a start node, this returns the node in the tree below the start node with the target value (or null if it doesn't exist)
 * Runs in O(n), where n is the number of nodes in the tree, or O(b^d), where b is the branching factor and d is the depth.
 * @param start  the node to start the search from
 * @param target the value to search for
 * @return The node containing the target value or null if it doesn't exist.
 */
const iterativeDeepeningDFS = function (start, target) {
    // Start by doing DFS with a depth of 1, keep doubling depth until we reach the "bottom" of the tree or find the node we're searching for
    var depth = 1;
    while (!bottomReached) {
        bottomReached = true; // One of the "end nodes" of the search with this depth has to still have children and set this to false again
        var result = iterativeDeepeningDFSRec(start, target, 0, depth);
        if (result != null) {
            // We've found the goal node while doing DFS with this max depth
            return result;
        }

        // We haven't found the goal node, but there are still deeper nodes to search through
        depth *= 2;
        console.log("Increasing depth to " + depth);
    }

    // Bottom reached is true.
    // We haven't found the node and there were no more nodes that still have children to explore at a higher depth.
    return null;
};

const iterativeDeepeningDFSRec = function (node, target, currentDepth, maxDepth) {
    console.log("Visiting Node " + node.value);
    if (node.value === target) {
        // We have found the goal node we we're searching for
        console.log("Found the node we're looking for!");
        return node;
    }

    if (currentDepth === maxDepth) {
        console.log("Current maximum depth reached, returning...");
        // We have reached the end for this depth...
        if (node.children.length > 0) {
            //...but we have not yet reached the bottom of the tree
            bottomReached = false;
        }
        return null;
    }

    // Recurse with all children
    for (var i = 0; i < node.children.length; i++) {
        var result = iterativeDeepeningDFSRec(node.children[i], target, currentDepth + 1, maxDepth);
        if (result != null) {
            // We've found the goal node while going down that child
            return result;
        }
    }

    // We've gone through all children and not found the goal node
    return null;
};

module.exports = {iterativeDeepeningDFS};

Über den Algorithmus und die Programmiersprache in diesem Snippet:

Iterative Tiefensuche Algorithmus

Der Iterative Tiefensuche-Algorithmus (Iterative Deepening Depth-First Search, ID-DFS) ist ein Algorithmus, mit dem ein Knoten in einem Baum gefunden wird. Dies bedeutet, dass der Algorithmus bei einer Baumdatenstruktur den ersten Knoten in diesem Baum zurückgibt, der der angegebenen Bedingung entspricht. Die Kanten müssen ungewichtet sein. Dieser Algorithmus kann auch mit ungewichteten Diagrammen arbeiten, wenn ein Mechanismus zum Verfolgen bereits besuchter Knoten hinzugefügt wurde.

Beschreibung des Algorithmus

Das Grundprinzip des Algorithmus besteht darin, mit einem Startknoten zu beginnen und dann das erste untergeordnete Element dieses Knotens zu betrachten. Anschließend wird das erste untergeordnete Element dieses Knotens (Enkel des Startknotens) usw. angezeigt, bis ein Knoten keine untergeordneten Elemente mehr hat (wir haben einen Blattknoten erreicht). Es geht dann eine Ebene höher und schaut auf das nächste Kind. Wenn keine Kinder mehr vorhanden sind, wird eine weitere Ebene erhöht, bis weitere Kinder gefunden werden oder der Startknoten erreicht wird. Wenn der Zielknoten nach der Rückkehr vom letzten untergeordneten Element des Startknotens nicht gefunden wurde, kann der Zielknoten nicht gefunden werden, da bis dahin alle Knoten durchlaufen wurden.

Bisher wurde hier die Tiefensuche (Depth-First Search, DFS) beschrieben. Die iterative Vertiefung trägt dazu bei, dass der Algorithmus nicht nur eine Ebene im Baum zurückgibt, wenn der Knoten keine untergeordneten Elemente mehr zu besuchen hat, sondern auch, wenn eine zuvor festgelegte maximale Tiefe erreicht wurde. Wenn wir zum Startknoten zurückkehren, erhöhen wir die maximale Tiefe und starten die Suche von vorne, bis wir alle Blattknoten (untere Knoten) besucht haben und eine Erhöhung der maximalen Tiefe nicht dazu führt, dass wir mehr Knoten besuchen.

Im Einzelnen sind dies die folgenden Schritte:

  1. Für jedes Kind des aktuellen Knotens
  2. Wenn es sich um den Zielknoten handelt, kehren Sie zurück
  3. Wenn die aktuelle maximale Tiefe erreicht ist, kehren Sie zurück
  4. Setzen Sie den aktuellen Knoten auf diesen Knoten und kehren Sie zu 1 zurück.
  5. Nachdem Sie alle Kinder durchlaufen haben, gehen Sie zum nächsten Kind des Elternteils (dem nächsten Geschwister).
  6. Nachdem Sie alle untergeordneten Elemente des Startknotens durchlaufen haben, erhöhen Sie die maximale Tiefe und kehren Sie zu 1 zurück.
  7. Wenn wir alle Blattknoten (unten) erreicht haben, existiert der Zielknoten nicht.

Beispiel des Algorithmus

Betrachten Sie den folgenden Baum:

Baum für den Algorithmus zur iterativen Vertiefung der Tiefensuche

Die Schritte, die der Algorithmus für diesen Baum ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:

  1. Besuche Knoten 0
  2. Besuche Knoten 1
  3. Aktuelle maximale Tiefe erreicht, Rückkehr …
  4. Besuche Knoten 2
  5. Aktuelle maximale Tiefe erreicht, Rückkehr …
  6. Tiefe auf 2 erhöhen
  7. Besuche Knoten 0
  8. Besuche Knoten 1
  9. Besuche Knoten 3
  10. Aktuelle maximale Tiefe erreicht, Rückkehr …
  11. Besuche Knoten 4
  12. Aktuelle maximale Tiefe erreicht, Rückkehr …
  13. Besuche Knoten 2
  14. Besuche Knoten 5
  15. Aktuelle maximale Tiefe erreicht, Rückkehr …
  16. Besuche Knoten 6
  17. Den gesuchten Knoten gefunden und zurückgegeben …

Laufzeit des Algorithmus

Wenn wir die maximale Tiefe jedes Mal verdoppeln, wenn wir tiefer gehen müssen, ist die Laufzeitkomplexität der iterativen vertiefenden Tiefensuche (ID-DFS) dieselbe wie bei der regulären Tiefensuche (DFS). da alle vorherigen addierten Tiefen dieselbe Laufzeit haben wie die aktuelle Tiefe (1/2 + 1/4 + 1/8 + … <1). Die Laufzeit der regulären Tiefensuche (DFS) beträgt O(| N|) (|N| = Anzahl der Knoten im Baum), da jeder Knoten höchstens einmal durchlaufen wird. Die Anzahl der Knoten ist gleich b^d, wobei b der Verzweigungsfaktor und d die Tiefe ist, sodass die Laufzeit als O(b ^ d) umgeschrieben werden kann.

Speicherkomplexität des Algorithmus

Die räumliche Komplexität der iterativen vertiefenden Tiefensuche (ID-DFS) entspricht der regulären Tiefensuche (DFS), dh, wenn wir den Baum selbst ausschließen, O(d), wobei d ist die Tiefe, die auch die Größe des Aufrufstapels bei maximaler Tiefe ist. Wenn wir den Baum einschließen, entspricht die Speicherplatzkomplexität der Laufzeitkomplexität, da jeder Knoten gespeichert werden muss.

Iterative Tiefensuche Algorithmus in anderen Programmierspraches:
Iterative Tiefensuche in allen Programmiersprachen

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.

Andere Algorithmen in Javascript:
Alle Algorithmen in Javascript