Algorytm niedeterministyczny
W programowaniu komputerowym algorytm niedeterministyczny to algorytm , który nawet dla tego samego wejścia może wykazywać różne zachowania w różnych przebiegach, w przeciwieństwie do algorytmu deterministycznego . Istnieje kilka sposobów, w jakie algorytm może zachowywać się inaczej w zależności od uruchomienia. Algorytm współbieżny może działać inaczej w różnych przebiegach ze względu na warunki wyścigu . Zachowanie algorytmu probabilistycznego zależy od generatora liczb losowych . Algorytm rozwiązujący problem w niedeterministyczny czas wielomianowy może przebiegać w czasie wielomianowym lub czasie wykładniczym, w zależności od wyborów dokonanych podczas wykonywania. Algorytmy niedeterministyczne są często używane do znalezienia przybliżenia rozwiązania, gdy uzyskanie dokładnego rozwiązania przy użyciu algorytmu deterministycznego byłoby zbyt kosztowne.
Pojęcie zostało wprowadzone przez Roberta W. Floyda w 1967 roku.
Używać
Często w teorii obliczeniowej termin „algorytm” odnosi się do algorytmu deterministycznego . Algorytm niedeterministyczny różni się od swojego bardziej znanego deterministycznego odpowiednika zdolnością do uzyskiwania wyników przy użyciu różnych dróg. Jeśli algorytm deterministyczny reprezentuje pojedynczą ścieżkę od wejścia do wyniku, algorytm niedeterministyczny reprezentuje pojedynczą ścieżkę wynikającą z wielu ścieżek, z których niektóre mogą dotrzeć do tego samego wyjścia, a niektóre mogą dotrzeć do unikalnych wyjść. Ta właściwość jest ujmowana matematycznie w „niedeterministycznych” modelach obliczeniowych, takich jak niedeterministyczny automat skończony . W niektórych scenariuszach wszystkie możliwe ścieżki mogą działać jednocześnie.
W projektowaniu algorytmów algorytmy niedeterministyczne są często używane, gdy problem rozwiązany przez algorytm z natury dopuszcza wiele wyników (lub gdy istnieje jeden wynik z wieloma ścieżkami, którymi można odkryć wynik, z których każda jest jednakowo preferowana). Co najważniejsze, każdy wynik wygenerowany przez algorytm niedeterministyczny jest ważny, niezależnie od wyborów, jakich algorytm dokonuje podczas działania.
W teorii złożoności obliczeniowej algorytmy niedeterministyczne to takie, które na każdym możliwym kroku mogą dopuszczać wiele kontynuacji (wyobraź sobie osobę idącą ścieżką w lesie i za każdym razem, gdy robi krok dalej, musi wybrać rozwidlenie drogi, które chce brać). Algorytmy te nie zapewniają rozwiązania dla każdej możliwej ścieżki obliczeniowej; jednak mają gwarancję, że dotrą do właściwego rozwiązania dla jakiejś ścieżki (tj. osoba idąca przez las może znaleźć swoją chatę tylko wtedy, gdy wybierze jakąś kombinację „właściwych” ścieżek). Wybory mogą być interpretowane jako domysły w wyszukiwania .
Za pomocą algorytmów niedeterministycznych można konceptualizować wiele problemów, w tym najsłynniejsze nierozwiązane pytanie w teorii komputerów, P vs NP .
Implementacja algorytmów niedeterministycznych z algorytmami deterministycznymi
Jednym ze sposobów symulacji niedeterministycznego algorytmu N przy użyciu algorytmu deterministycznego D jest traktowanie zbiorów stanów N jako stanów D . Oznacza to, że D jednocześnie śledzi wszystkie możliwe ścieżki wykonania N (patrz konstrukcja powerset dla tej techniki używanej dla automatów skończonych ).
Innym jest randomizacja , która polega na tym, że wszystkie wybory są określane przez generator liczb losowych . Wynik nazywany jest probabilistycznym algorytmem deterministycznym.
Zobacz też
Dalsza lektura
- Cormen, Thomas H. (2009). Wprowadzenie do algorytmów (wyd. 3). MIT Press. ISBN 978-0-262-03384-8 .
- „Algorytm niedeterministyczny” . Narodowy Instytut Norm i Technologii . Źródło 7 lipca 2013 r .
- „Algorytmy niedeterministyczne” . Informatyka Uniwersytetu Nowojorskiego . Źródło 7 lipca 2013 r .