Nedeterministický algoritmus - Nondeterministic algorithm

Tento článek je o nedeterminismu v programování počítače . Pro nedeterminismus v teorii výpočetní složitosti viz nedeterministický model výpočtu .

V programování počítače , je nedeterministický algoritmus je algoritmus , že i pro stejný vstup, mohou vykazovat různé chování v různých testech, na rozdíl od deterministický algoritmus . Existuje několik způsobů, jak se může algoritmus chovat odlišně od běhu k běhu. Souběžné algoritmus se mohou chovat jinak na různých testech v důsledku spor . Pravděpodobnostní algoritmus to chování závisí na generátoru náhodných čísel . Algoritmus, který řeší problém v nedeterministickém polynomiálním čase, může běžet v polynomiálním čase nebo exponenciálním čase v závislosti na volbách, které provede během provádění. Nedeterministické algoritmy se často používají k nalezení aproximace řešení, kdy by přesné řešení bylo příliš nákladné na získání pomocí deterministického řešení.

Pojem představil Robert W. Floyd v roce 1967.

Použití

Ve výpočetní teorii se termín „algoritmus“ často vztahuje k deterministickému algoritmu . Nedeterministický algoritmus se liší od svého známějšího deterministického protějšku ve schopnosti dosáhnout výsledků pomocí různých cest. Pokud deterministický algoritmus představuje jednu cestu od vstupu k výsledku, nedeterministický algoritmus představuje jednu cestu, která vychází z mnoha cest, z nichž některé mohou přijít na stejný výstup a některé mohou přijít na jedinečné výstupy. Tato vlastnost je matematicky zachycena v „nedeterministických“ modelech výpočtu , jako je nedeterministický konečný automat . V některých scénářích mohou všechny možné cesty běžet současně.

V návrhu algoritmu se často používají nedeterministické algoritmy, když problém vyřešený algoritmem neodmyslitelně umožňuje více výsledků (nebo když existuje jediný výsledek s více cestami, kterými může být výsledek objeven, každý stejně výhodný). Klíčové je, že každý výsledek, který nedeterministický algoritmus vytvoří, je platný, bez ohledu na to, jaké volby algoritmus za běhu provede.

V teorii výpočetní složitosti jsou nedeterministické algoritmy takové, které na každém možném kroku umožňují více pokračování (představte si, jak člověk kráčí cestou v lese a pokaždé, když vykročí dál, musí si vybrat, kterou vidličku na cestě si přeje vzít). Tyto algoritmy nepřijdou k řešení pro každou možnou výpočetní cestu; je však zaručeno, že pro určitou cestu přijdou ke správnému řešení (tj. osoba, která kráčí lesem, může najít svoji chatku, pouze pokud zvolí kombinaci „správných“ cest). Možnosti lze interpretovat jako odhady v procesu vyhledávání .

Velké množství problémů lze konceptualizovat pomocí nedeterministických algoritmů, včetně nejslavnější nevyřešené otázky v teorii výpočetní techniky, P vs NP .

Implementace nedeterministických algoritmů s deterministickými

Jeden způsob, jak simulovat nedeterministický algoritmus N pomocí deterministický algoritmus D je k léčbě sad stavy N jako stavů D . To znamená, že D současně sleduje všechny možné cesty provádění N (viz konstrukci sady pohonných jednotek pro tuto techniku ​​používanou pro konečné automaty ).

Další je randomizace , která spočívá v tom, že necháme všechny volby určit generátorem náhodných čísel . Výsledek se nazývá pravděpodobnostní deterministický algoritmus.

Viz také

Reference

Další čtení