Algorytm niedeterministyczny - Nondeterministic algorithm
W programowaniu komputerowym , wykorzystując algorytm niedeterministyczny jest algorytm , który, nawet dla tego samego wejścia, mogą wykazywać różne zachowania w różnych seriach, w przeciwieństwie do algorytmu deterministycznego . Istnieje kilka sposobów, w jakie algorytm może zachowywać się inaczej w zależności od uruchomienia. Współbieżne algorytm może działać inaczej w różnych seriach powodu wyścigu . Zachowanie algorytmu probabilistycznego zależy od generatora liczb losowych . Algorytm rozwiązujący problem w niedeterministycznym czasie wielomianowym może działać w czasie wielomianowym lub 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 byłoby zbyt kosztowne przy użyciu rozwiązania deterministycznego.
Pojęcie to zostało wprowadzone przez Roberta W. Floyda w 1967 roku.
Posługiwać się
Często w teorii obliczeń termin „algorytm” odnosi się do algorytmu deterministycznego . Niedeterministyczny algorytm różni się od swojego bardziej znanego deterministycznego odpowiednika zdolnością do uzyskiwania wyników różnymi drogami. Jeśli deterministyczny algorytm reprezentuje pojedynczą ścieżkę od wejścia do wyniku, niedeterministyczny algorytm reprezentuje pojedynczą ścieżkę prowadzącą do wielu ścieżek, z których niektóre mogą prowadzić do tego samego wyjścia, a niektóre z nich mogą prowadzić do unikalnych wyników. Ta właściwość jest ujęta 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 pozwala na wiele wyników (lub gdy istnieje pojedynczy wynik z wieloma ścieżkami, którymi można je odkryć, z których każdy jest równie preferowany). Co najważniejsze, każdy wynik uzyskany przez niedeterministyczny algorytm jest ważny, niezależnie od wyborów dokonanych przez algorytm podczas pracy.
W teorii złożoności obliczeniowej algorytmy niedeterministyczne to takie, które na każdym możliwym kroku mogą pozwolić na wielokrotne kontynuacje (wyobraź sobie osobę idącą ścieżką w lesie i za każdym razem, gdy zrobią krok dalej, muszą wybrać, które rozwidlenie drogi chcą brać). Te algorytmy nie prowadzą do rozwiązania dla każdej możliwej ścieżki obliczeniowej; jednakże mają gwarancję, że dotrą do właściwego rozwiązania dla jakiejś ścieżki (np. osoba idąca przez las może znaleźć swoją chatę tylko wtedy, gdy wybierze jakąś kombinację „prawidłowych” ścieżek). Wybory można interpretować jako domysły w procesie wyszukiwania .
Wiele problemów można konceptualizować za pomocą niedeterministycznych algorytmów, w tym najsłynniejszego nierozwiązanego pytania w teorii obliczeń, P vs NP .
Implementacja algorytmów niedeterministycznych z algorytmami deterministycznymi
Jednym ze sposobów, aby symulować niedeterministycznych algorytm N używając deterministycznego algorytmu D jest w leczeniu stanów zestawów N jak stany D . Oznacza to, że D jednocześnie śledzi wszystkie możliwe ścieżki wykonania N (zobacz konstrukcję PowerSet dla tej techniki używanej w automatach 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ż
Bibliografia
Dalsza lektura
- Cormen, Thomas H. (2009). Wprowadzenie do algorytmów (3rd ed.). MIT Press. ISBN 978-0-262-03384-8 .
- „Niedeterministyczny algorytm” . Narodowy Instytut Standardów i Technologii . Źródło 7 lipca 2013 r .
- „Algorytmy niedeterministyczne” . Informatyka Uniwersytetu Nowojorskiego . Źródło 7 lipca 2013 r .