Der Breitensuchalgorithmus (Breadth-first-search, BFS) ist ein Algorithmus, der verwendet wird, um das Problem des kürzesten Pfades in einem Graphen ohne Kantengewichte zu lösen (d.h. ein Diagramm, in dem alle Knoten den gleichen “Abstand” voneinander haben und entweder verbunden sind oder nicht). Dies bedeutet, dass bei einer Anzahl von Knoten und den Kanten zwischen ihnen der Breitensuchalgorithmus den kürzesten Weg vom angegebenen Startknoten zu allen anderen Knoten findet.

Beschreibung des Algorithmus

Das Grundprinzip des Breitensuchalgorithmus besteht darin, den aktuellen Knoten (den Startknoten am Anfang) zu nehmen und dann alle seine Nachbarn, die wir noch nicht besucht haben, zu einer Warteschlange hinzuzufügen. Fahren Sie mit dem nächsten Knoten in der Warteschlange fort (in einer Warteschlange, die der “älteste” Knoten ist). Bevor wir der Warteschlange einen Knoten hinzufügen, setzen wir seinen Abstand auf den Abstand des aktuellen Knotens plus 1 (da alle Kanten gleich gewichtet sind), wobei der Abstand zum Startknoten 0 ist. Dies wird wiederholt, bis sich keine Knoten mehr in der Warteschlange befinden (alle Knoten werden besucht).

Im Einzelnen führt dies zu den folgenden Schritten:

1. Initialisieren Sie die Entfernung zum Startknoten als 0. Die Entfernungen zu allen anderen Knoten müssen nicht initialisiert werden, da jeder Knoten genau einmal besucht wird.
2. Setzen Sie alle Knoten auf “nicht besucht”.
3. Fügen Sie den ersten Knoten zur Warteschlange hinzu und kennzeichnen Sie ihn als besucht.

4. Während sich Knoten in der Warteschlange befinden:

   1. Nehmen Sie einen Knoten aus der Warteschlange
   2. Fügen Sie für alle Knoten daneben, die wir noch nicht besucht haben, sie der Warteschlange hinzu, stellen Sie ihre Entfernung auf die Entfernung zum aktuellen Knoten plus 1 ein und legen Sie sie als “besucht” fest.

Am Ende sind die Abstände zu allen Knoten korrekt.

Beispiel des Algorithmus

Betrachten Sie das folgende Diagramm:

Die Schritte, die der Algorithmus in diesem Diagramm ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:

1. Besuche Knoten 0

2. Besuchte Knoten: [wahr, falsch, falsch, falsch, falsch, falsch], Entfernungen: [0, 0, 0, 0, 0, 0]

   1. Knoten 0 aus der Warteschlange entfernen …
   2. Besuchen Sie Knoten 1, setzen Sie seinen Abstand auf 1 und fügen Sie ihn der Warteschlange hinzu
   3. Besuchen Sie Knoten 2, setzen Sie seinen Abstand auf 1 und fügen Sie ihn der Warteschlange hinzu

3. Besuchte Knoten: [wahr, wahr, wahr, falsch, falsch, falsch], Entfernungen: [0, 1, 1, 0, 0, 0]

   1. Entfernen von Knoten 1 aus der Warteschlange …
   2. Besuchen Sie Knoten 3, setzen Sie seinen Abstand auf 2 und fügen Sie ihn der Warteschlange hinzu
   3. Besuchen Sie Knoten 4, stellen Sie seinen Abstand auf 2 ein und fügen Sie ihn der Warteschlange hinzu

4. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, falsch], Entfernungen: [0, 1, 1, 2, 2, 0]

   1. Entfernen von Knoten 2 aus der Warteschlange …
   2. Keine benachbarten, nicht besuchten Knoten

5. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, falsch], Entfernungen: [0, 1, 1, 2, 2, 0]

   1. Entfernen von Knoten 3 aus der Warteschlange …
   2. Besuchen Sie Knoten 5, stellen Sie seinen Abstand auf 3 ein und fügen Sie ihn der Warteschlange hinzu

6. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, wahr], Entfernungen: [0, 1, 1, 2, 2, 3]

   1. Entfernen von Knoten 4 aus der Warteschlange …
   2. Keine benachbarten, nicht besuchten Knoten

7. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, wahr], Entfernungen: [0, 1, 1, 2, 2, 3]

   1. Entfernen von Knoten 5 aus der Warteschlange …
8. Keine Knoten mehr in der Warteschlange. Endabstände: [0, 1, 1, 2, 2, 3]

Laufzeitkomplexität des Algorithmus

Die Laufzeitkomplexität der Breitensuche beträgt O(|E| + |V|) (|V| = Anzahl der Knoten, |E| = Anzahl der Kanten), wenn Adjazenzlisten verwendet werden. Wenn wir einfach alle Knoten durchsuchen, um in jedem Schritt verbundene Knoten zu finden, und mithilfe einer Matrix nachsehen, ob zwei Knoten benachbart sind, steigt die Laufzeitkomplexität auf O(|V|^2).

Abhängig vom Diagramm spielt dies möglicherweise keine Rolle, da die Anzahl der Kanten bis zu |V|^2 betragen kann, wenn alle Knoten miteinander verbunden sind.

Speicherplatzkomplexität des Algorithmus

Die Speicherplatzkomplexität der Breitensuche hängt auch davon ab, wie sie implementiert ist, und entspricht der Laufzeitkomplexität.

R

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.