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:

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.

Java ™ ist eine kompilierte Sprache, die für viele Zwecke verwendet wird, von eingebetteten Systemen über UI-Anwendungen bis hin zu Webservern.

“Hello World” in Java

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

1. Laden Sie die neueste Version von Java von [java.com] herunter und installieren Sie sie (https://www.java.com/en/download/). Sie können auch eine frühere Version herunterladen, wenn Ihr Anwendungsfall dies erfordert.

2. Öffnen Sie ein Terminal, stellen Sie sicher, dass die Befehle “javac” und “javac” funktionieren und dass sich der Befehl, den Sie verwenden werden, auf die Version bezieht, die Sie gerade installiert haben, indem Sie “java -version” ausführen. 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:

   • Windows
   • Mac
   • Linux

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

   class HelloWorld {
   public static void main(String[] args) {
       // Paste any following code snippets here.
       System.out.println("Hello World");
   }
   }

4. Ändern Sie das Verzeichnis, indem Sie “cd path / to / HelloWorld” eingeben, dann “javac HelloWorld.java” ausführen, um die Datei zu kompilieren (die den Bytecode erstellt), und dann “java HelloWorld” ausführen (* ohne die .java-Endung *). Dies sollte “Hello World” auf Ihrem Terminal drucken.

Das ist es! Beachten Sie, dass die Eintrittsbarriere bei Java etwas höher ist als bei z. Python - aber Java ist viel schneller und weist meiner Erfahrung nach aufgrund starker Typisierung und anderer Faktoren weniger Fehler in großen Projekten auf.

Fundamentals in Java

Um in Java implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen. Jedes der folgenden Snippets sollte vom Boilerplate-Code des Hello World-Beispiels umgeben sein und mit den oben genannten Befehlen kompiliert und ausgeführt werden.

Variables and Arithmetic

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

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

Arrays

Arrays in Java sind echte 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 Java effizienter sind als in Python.

int[] integers = new int[5];
integers[3] = 12; // Assigning values to positions in the array
// integers[4] is 0, integers[6] would give IndexOutOfBoundsException
String[] strings = {"Hello", "World"}; // Array initialization with initial values
System.out.println(strings[0] + integers[3]); // Prints "Hello12"

Conditions

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

int value = 5;
if(value == 5){
    System.out.println("Value is 5");
} else if(value < 5){
    System.out.println("Value is less than 5");
} else {
    System.out.println("Value is something else");
}

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

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

Schleifen

Java 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++) {
    System.out.println(i);
}
while (value > 0) {
    System.out.println(value);
    value--;
}
do {
    System.out.println(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 Java können Teil einer Klasse oder eines Objekts einer Klasse sein. Für weitere Informationen zur objektorientierten Programmierung empfehle ich den w3schools-Kurs. Hier ist ein minimales Beispiel für eine Funktion als Teil einer Klasse (auch als statische Funktion bezeichnet):

class HelloWorld {
    public static void main(String[] args) {
        System.out.println(addNumbers(3, 4));
    }

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

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

class HelloWorld {
    public static void main(String[] args) {
        System.out.println(new HelloWorld().addNumbers(3, 4));
    }

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

Beachten Sie, wie im ersten Beispiel das Schlüsselwort static verwendet wird und im zweiten Beispiel das Objekt der Klasse instanziiert werden muss, bevor in die Funktion dieses Objekts aufrufen kann. Dies sind einige der Unterschiede bei Klassenmethoden und Objektfunktionen.

Syntax

Java 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.

Fortgeschrittenes Wissen in Java

Java wurde erstmals 1995 veröffentlicht und ist ein Multi-Paradigma. Das heißt, es ist in erster Linie objektorientiert, hat aber auch funktionale und reflektierende Elemente. Es ist statisch typisiert, bietet jedoch in neueren Versionen ein gewisses Maß an dynamischer Typisierung. Für weitere Informationen hat Java einen großartigen Artikel Wikipedia.