Nicht deterministischer Algorithmus

Definition - Was bedeutet nicht deterministischer Algorithmus?

Ein nicht deterministischer Algorithmus kann bei verschiedenen Ausführungen unterschiedliche Ausgaben für dieselbe Eingabe bereitstellen. Im Gegensatz zu einem deterministischen Algorithmus, der selbst bei verschiedenen Läufen nur eine einzige Ausgabe für dieselbe Eingabe erzeugt, bewegt sich ein nicht deterministischer Algorithmus auf verschiedenen Wegen, um zu den unterschiedlichen Ergebnissen zu gelangen.

Nicht deterministische Algorithmen sind nützlich, um ungefähre Lösungen zu finden, wenn es schwierig oder teuer ist, eine genaue Lösung unter Verwendung eines deterministischen Algorithmus abzuleiten.

Technische.me erklärt den nicht deterministischen Algorithmus

Ein Beispiel für einen nicht deterministischen Algorithmus ist die Ausführung von gleichzeitigen Algorithmen mit Rennbedingungen, die bei verschiedenen Läufen unterschiedliche Ausgaben aufweisen können. Im Gegensatz zu einem deterministischen Algorithmus, der einen einzelnen Pfad von der Eingabe zur Ausgabe zurücklegt, kann ein nicht deterministischer Algorithmus viele Pfade nehmen, wobei einige zu denselben Ausgaben und andere zu unterschiedlichen Ausgaben gelangen. Diese Funktion wird mathematisch in nicht deterministischen Berechnungsmodellen wie nicht deterministischen endlichen Automaten verwendet.

Ein nicht deterministischer Algorithmus kann auf einem deterministischen Computer ausgeführt werden, der eine unbegrenzte Anzahl paralleler Prozessoren aufweist. Ein nicht deterministischer Algorithmus besteht normalerweise aus zwei Phasen und Ausgabeschritten. Die erste Phase ist die Vermutungsphase, in der beliebige Zeichen verwendet werden, um das Problem auszuführen.

Die zweite Phase ist die Überprüfungsphase, die für die ausgewählte Zeichenfolge true oder false zurückgibt. Es gibt viele Probleme, die mit Hilfe nicht deterministischer Algorithmen konzeptualisiert werden können, einschließlich des ungelösten Problems von P gegen NP in der Computertheorie.

Nicht deterministische Algorithmen werden zur Lösung von Problemen verwendet, die mehrere Ergebnisse ermöglichen. Jedes Ergebnis, das der nicht deterministische Algorithmus erzeugt, ist gültig, unabhängig von den Entscheidungen, die der Algorithmus während der Ausführung getroffen hat.