Iterative Tiefensuche in R

Gepostet: , Zuletzt aktualisiert:

bottom_reached = FALSE  # Variable to keep track if we have reached the bottom of the tree

iterative_deepening_dfs <- function(start, target){
  #' 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.
  
  # 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
  depth = 1
  while(!bottom_reached){
    bottom_reached <<- TRUE # One of the "end nodes" of the search with this depth has to still have children and set this to false again
    # One of the "end nodes" of the search with this depth has to still have children and set this to FALSE again
    result = iterative_deepening_dfs_rec(start, target, 0, depth)
    if(!is.null(result)){
      # 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 = depth * 2
    cat("Increasing depth to ", depth, "\n")
    print(bottom_reached)
  }
  # 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)
}

iterative_deepening_dfs_rec <- function(node, target, current_depth, max_depth) {
  cat("Visiting Node ", node$value, "\n")
  
  if(node$value == target){
    # We have found the goal node we we're searching for
    print("Found the node we're looking for!")
    return (node)
  }
  
  if(current_depth == max_depth) {
    print("Current maximum depth reached, returning...")
    # We have reached the end for this depth...
    if(length(node$children) > 0){
      # ...but we have not yet reached the bottom of the tree
      bottom_reached <<- FALSE
    }
    return (NULL)
  }
  
  # Recurse with all children
  for (i in seq_along(node$children)){
    result = iterative_deepening_dfs_rec(node$children[[i]], target, current_depth + 1, max_depth)
    if(!is.null(result)){
      # 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)
}

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

R

The R Logo

R ist eine interpretierte Sprache, die erstmals 1993 veröffentlicht wurde und in den letzten Jahren erheblich an Popularität gewonnen hat. Es wird hauptsächlich für Data Mining und -science sowie für Statistiken verwendet und ist eine beliebte Sprache in Disziplinen außerhalb der Informatik, die von Biologie bis Physik reichen. R ist dynamisch typisiert und verfügt über eine der vielfältigsten Bibliotheken für Statistik, maschinelles Lernen, Data Mining usw.

<! - Ende des Auszugs ->

Anreise zu “Hello World” in R.

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

  1. Laden Sie die neueste Version von R von r-project.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, stellen Sie sicher, dass der Befehl R funktioniert und dass der Befehl, den Sie verwenden werden, sich auf die Version bezieht, die Sie gerade installiert haben, indem SieR --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 Windows, Mac und Linux .
  3. Sobald dies funktioniert, können Sie das folgende Snippet ausführen: print (" Hello World "). Sie haben zwei Möglichkeiten, dies auszuführen: 3.1 Führen Sie “R” in der Befehlszeile aus, fügen Sie einfach das Code-Snippet ein und drücken Sie die Eingabetaste (Drücken Sie “STRG + D” und geben Sie “n” gefolgt von der Eingabetaste ein, um das Menü zu verlassen). 3.2 Speichern Sie das Snippet in einer Datei und nennen Sie es etwas, das mit “.R” endet, z. hello_world.R und führen SieRscript hello_world.R aus. Tipp: Verwenden Sie den Befehl ls (dir in Windows), um herauszufinden, welche Dateien sich in dem Ordner befinden, in dem sich Ihre Befehlszeile gerade befindet.

Das ist es! Beachten Sie, dass das Drucken von etwas auf die Konsole nur eine einzige Zeile in R ist - diese niedrige Eintrittsbarriere und das Fehlen des erforderlichen Boilerplate-Codes machen einen großen Teil der Attraktivität von R aus.

Grundlagen in R.

Um in R implementierte Algorithmen und Technologien zu verstehen, muss man zunächst verstehen, wie grundlegende Programmierkonzepte in dieser bestimmten Sprache aussehen.

Variablen und Arithmetik

Variablen in R sind wirklich einfach. Sie müssen weder einen Datentyp deklarieren noch deklarieren, dass Sie eine Variable definieren. R weiß das implizit. R ist auch in der Lage, Objekte und ihre Eigenschaften auf verschiedene Arten einfach zu definieren.

some_value = 10
my_object <- list(my_value = 4)
attr(my_object, 'other_value') <- 3

print((some_value + my_object$my_value + attr(my_object, 'other_value'))) # Prints 17

Arrays

Das Arbeiten mit Arrays ist in R ähnlich einfach:

# Create 2 vectors of length 3
vector1 <- c(1,2,3)
vector2 <- c(4,5,6)

# Create names for rows and columns (optional)
column.names <- c("column_1","column_2","column_3")
row.names <- c("row_1","row_2")

# Concatenate the vectors (as rows) to form an array, providing dimensions and row/column names
result <- array(c(vector1,vector2), dim = c(2,3), dimnames = list(row.names, column.names))

print(result)
# Prints:
#       column_1 column_2 column_3
# row_1        1        3        5
# row_2        2        4        6

Wie diejenigen unter Ihnen, die mit anderen Programmiersprachen wie Java vertraut sind, möglicherweise bereits bemerkt haben, handelt es sich nicht um native Arrays, sondern um Listen, die wie Arrays gekleidet sind. Dies bedeutet, dass Arrays in R erheblich langsamer sind als in Programmiersprachen niedrigerer Ebene. Dies ist ein Kompromiss, den R zugunsten der Einfachheit eingeht. Es gibt jedoch Pakete, die echte Arrays implementieren, die erheblich schneller sind.

Bedingungen

Wie die meisten Programmiersprachen kann R “if-else” -Anweisungen ausführen:

value = 1
if(value==1){
   print("Value is 1")
} else if(value==2){
     print("Value is 2")
} else {
     print("Value is something else")
}

R kann auch switch-Anweisungen ausführen, obwohl sie im Gegensatz zu anderen Sprachen wie Java als Funktion implementiert sind:

x <- switch(
   1,
   "Value is 1",
   "Value is 2",
   "Value is 3"
)

print(x)

Beachten Sie, dass diese Funktion ziemlich nutzlos ist, es jedoch andere Funktionen für komplexere Anwendungsfälle gibt.

Schleifen

R unterstützt sowohl for- als auch while-Schleifen sowie break- und next-Anweisungen (vergleichbar mit continue in anderen Sprachen). Zusätzlich unterstützt R “Wiederholungsschleifen”, die mit “while (true)” - Schleifen in anderen Sprachen vergleichbar sind, aber den Code ein wenig vereinfachen.

value <- 0
repeat {
  value <- value + 1
  if(value > 10) {
    break
  }
}
print(value)

value <- 0
while (value <= 10) {
  value = value + 1
}
print(value)

value <- c("Hello","World","!")
for ( i in value) {
  print(i)
}

for(i in 1:10){
  print(i)
}

Funktionen

Funktionen in R sind einfach zu definieren und erfordern zum Guten oder Schlechten keine Angabe von Rückgabe- oder Argumenttypen. Optional kann ein Standardwert für Argumente angegeben werden:

my_func <- function (
  a = "World"
) {
  print(a)
  return("!")
}

my_func("Hello")
print(my_func())

(Dies druckt “Hallo”, “Welt” und dann ”!“)

Syntax

R erfordert die Verwendung von geschweiften Klammern ({}), um Codeblöcke in Bedingungen, Schleifen, Funktionen usw.; 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 R

Für weitere Informationen hat R einen großartigen Artikel Wikipedia. Die offizielle Website ist r-project.org.