Iterative Tiefensuche in C

Gepostet: 2020-07-11 13:56, Zuletzt aktualisiert: 2020-07-11 13:56

package iterative_deepening_dfs.c.simple;

/**
 * Used to perform the Iterative Deepening Depth-First Search (DFS) Algorithm to find the shortest path from a start to a target node.
 */
public class IterativeDeepeningDFS {
    private static boolean bottomReached = false; // Variable to keep track if we have reached the bottom of the tree

    /**
     * Implementation of iterative deepening DFS (depth-first search).
     * 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.
     */
    public static Node iterativeDeepeningDFS(Node start, int 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
        int 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
            Node result = iterativeDeepeningDFS(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;
            System.out.println("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;
    }

    private static Node iterativeDeepeningDFS(Node node, int target, int currentDepth, int maxDepth) {
        System.out.println("Visiting Node " + node.value);
        if (node.value == target) {
            // We have found the goal node we we're searching for
            System.out.println("Found the node we're looking for!");
            return node;
        }

        if (currentDepth == maxDepth) {
            System.out.println("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 (int i = 0; i < node.children.length; i++) {
            Node result = iterativeDeepeningDFS(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;
    }
}

// used to store a tree datastructure
class Node {
    Node[] children;
    int value;
}

Ü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:

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

Beispiel des Algorithmus

Betrachten Sie den folgenden Baum:

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

Besuche Knoten 0
Besuche Knoten 1
Aktuelle maximale Tiefe erreicht, Rückkehr …
Besuche Knoten 2
Aktuelle maximale Tiefe erreicht, Rückkehr …
Tiefe auf 2 erhöhen
Besuche Knoten 0
Besuche Knoten 1
Besuche Knoten 3
Aktuelle maximale Tiefe erreicht, Rückkehr …
Besuche Knoten 4
Aktuelle maximale Tiefe erreicht, Rückkehr …
Besuche Knoten 2
Besuche Knoten 5
Aktuelle maximale Tiefe erreicht, Rückkehr …
Besuche Knoten 6
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

C

C ist eine kompilierte Sprache, die für viele Zwecke verwendet wird, obwohl sie hauptsächlich in Systemen zu finden ist, in denen Wichtigkeit wichtig ist. Dies liegt daran, dass C viel Unterstützung auf niedriger Ebene für die Optimierung bietet, auf Kosten der Tatsache, dass einige der praktischen Abstraktionen, die andere Sprachen bieten, nicht vorhanden sind. C tritt daher hauptsächlich in Situationen auf, in denen die verfügbare Rechenleistung gering ist, wie beispielsweise eingebettete Systeme, oder in Situationen, in denen die erforderliche Rechenleistung hoch ist, wie z. B. Simulation oder Deep Learning.

“Hello World” in C

Das Wichtigste zuerst - hier erfahren Sie, wie Sie Ihre erste Codezeile in C ausführen können.

Wenn Sie unter Linux oder Mac arbeiten, laden Sie die neueste Version von GCC, einem C-Compiler, von gcc.gnu.org herunter und installieren Sie sie. Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert.
Wenn Sie unter Windows arbeiten, können Sie auch GCC installieren, obwohl dies zu Problemen führen kann. Sie haben auch andere Optionen, z. hier.
Öffnen Sie ein Terminal, stellen Sie sicher, dass der Befehl gcc funktioniert (oder der entsprechende Befehl für den von Ihnen verwendeten Compiler) und dass sich der Befehl, den Sie verwenden werden, auf die Version bezieht, die Sie gerade durch Ausführen installiert haben gcc --version. 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 Forumfragen für jede Plattform:
- Windows
- Mac
- Linux
Sobald dies funktioniert, kopieren Sie das folgende Snippet in eine Datei mit dem Namen HelloWorld.c:
```
#include<stdio.h>
int main() {
printf("Hello World\n");
return 0;
}
```
Ändern Sie das Verzeichnis, indem Sie “cd path / to / HelloWorld” eingeben, dann “gcc HelloWorld.c” ausführen, um die Datei zu kompilieren (die den Bytecode erstellt), und dann “. / A.out” ausführen. Dies sollte “Hello World” auf Ihrem Terminal drucken.

Das ist es! Personen, die mehrere Programmiersprachen kennen, werden feststellen, dass die Eintrittsbarriere in C etwas niedriger ist als in Java, obwohl sie niedriger ist, während die Eintrittsbarriere für Python niedriger ist, obwohl sie höher ist. Meine persönliche Beobachtung ist, dass Sprachen auf niedriger und hoher Ebene tendenziell niedrige Eintrittsbarrieren aufweisen, während Sprachen auf mittlerer Ebene höhere Barrieren aufweisen.

Grundlagen in C

Um in C implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen. Jedes der folgenden Snippets sollte mit den oben genannten Befehlen kompiliert und ausgeführt werden.

Variablen und Arithmetik

Variablen in C sind statisch typisiert, was bedeutet, dass der Inhalt einer Variablen beim Schreiben des Codes angegeben werden muss. Der Datentyp für ganze Zahlen ist beispielsweise “int”. Zahlen mit Dezimalstellen werden je nach erforderlicher Genauigkeit mit “float” oder “double” eingegeben. Der Typ für Text ist “String”.

#include<stdio.h>

int main() {
    int number = 5;
    double decimalNumber = 3.25;
    double result = number * decimalNumber;
    char callout [] = "The number is ";
    // In this instance, the values are concatenated rather than added because one of them is a String.
    printf("%s", callout);
    printf("%f", result);
    printf("\n");
    return 0;
}

Arrays

Arrays in C sind real Arrays (im Gegensatz zu beispielsweise Python, wo sie als Listen implementiert sind). Dies hat zur Folge, dass die Größe beim Erstellen festgelegt werden muss und nicht geändert werden kann, aber auch, dass sie in C effizienter sind als in Python. Im Gegensatz zu Java überprüft C auch keine Array-Grenzen. Wenn Sie auf einen Index zugreifen, der nicht vorhanden ist, liest das Programm alles, was sich an dieser Stelle im Speicher befindet (was wahrscheinlich Kauderwelsch sein wird).

int integers[5];
integers[3] = 12; // Assigning values to positions in the array
printf("%d\n", integers[0]); // will be 0
printf("%d\n", integers[3]); // will be 12
printf("%d\n", integers[6]); // will print something random that happened to be at that location in memory
return 0;

Bedingungen

Wie die meisten Programmiersprachen kann C “if-else” -Anweisungen ausführen. Zusätzlich kann C auch “switch-case” -Anweisungen ausführen.

int value = 5;
    if(value == 5){
        printf("%s\n", "Value is 5");
    } else if(value < 5){
        printf("%s\n", "Value is less than 5");
    } else {
        printf("%s\n", "Value is something else");
    }
    
    switch (value){
        case 1:
            printf("%s\n", "Value is 1");
            break; // Don't go further down the cases
        case 2:
            printf("%s\n", "Value is 2");
            break; // Don't go further down the cases
        case 3:
            printf("%s\n", "Value is 3");
            break; // Don't go further down the cases
        case 4:
            printf("%s\n", "Value is 4");
            break; // Don't go further down the cases
        case 5:
            printf("%s\n", "Value is 5");
            break; // Don't go further down the cases
        default:
            printf("%s\n", "Value is something else");
    }

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

Schleifen

C unterstützt “for” -, “while” - und “do while” -Schleifen. Die Anweisungen break undcontinue werden ebenfalls unterstützt. Das folgende Beispiel zeigt die Unterschiede:

int value = 2;
for (int i = 0; i < value; i++) {
    printf("%d\n", i);
}
while (value > 0) {
    printf("%d\n", value);
    value--;
}
do {
    printf("%d\n", value);
    value--;
} while (value > 0);

Dadurch wird Folgendes auf das Terminal gedruckt:

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 C können ähnlich wie Java deklariert werden, erfordern jedoch weniger Boilerplate, da sie nicht Teil von Klassen oder Objekten sein müssen. Hier ist ein minimales Beispiel für eine Funktion:

#include<stdio.h>

int addNumbers(int numberOne, int numberTwo) {
    return numberOne + numberTwo;
}

int main() {
    printf("%d\n", addNumbers(3, 4));
}

Syntax

C erfordert die Verwendung von geschweiften Klammern ({}), um Codeblöcke in Bedingungen, Schleifen, Funktionen usw.; Außerdem sind am Ende der Anweisungen Semikolons erforderlich. Dies kann zwar zu lästigen Syntaxfehlern führen, bedeutet jedoch auch, dass die Verwendung von Leerzeichen für die bevorzugte Formatierung (z. B. Einrücken von Codeteilen) den Code nicht beeinflusst. Beachten Sie, dass die Syntax von C Java sehr ähnlich ist. Die Syntax von Java und viele andere Sprachen, die nach C kamen und / oder von C abgeleitet wurden, kopieren viele Aspekte seiner Syntax.

Fortgeschrittenes Wissen zu C

C wurde erstmals 1972 veröffentlicht, ist statisch typisiert und wurde mit verschiedenen Implementierungen auf viele Plattformen portiert (eine davon ist GCC, die in diesem Artikel vorgestellt wurde). Für weitere Informationen hat C einen großartigen Artikel Wikipedia.

Andere Algorithmen in C:

Alle Algorithmen in C