Obsah:
- Definícia - Čo znamená nedeterministický algoritmus?
- Techopedia vysvetľuje nedeterministický algoritmus
Definícia - Čo znamená nedeterministický algoritmus?
Neurčitý algoritmus môže poskytnúť rôzne výstupy pre ten istý vstup pri rôznych vykonaniach. Na rozdiel od deterministického algoritmu, ktorý produkuje iba jediný výstup pre ten istý vstup aj pri rôznych pokusoch, nedeterministický algoritmus cestuje rôznymi cestami, aby dospel k rôznym výsledkom.
Nedeterministické algoritmy sú užitočné pri hľadaní približných riešení, keď je ťažké zistiť presné riešenie pomocou deterministického algoritmu.
Techopedia vysvetľuje nedeterministický algoritmus
Jedným príkladom nedeterministického algoritmu je vykonanie súbežných algoritmov s rasovými podmienkami, ktoré môžu vykazovať rôzne výstupy pri rôznych pokusoch. Na rozdiel od deterministického algoritmu, ktorý cestuje po jednej ceste od vstupu k výstupu, nedeterministický algoritmus môže mať veľa ciest, pričom niektoré prichádzajú na rovnaké výstupy a iné prichádzajú na rôzne výstupy. Táto vlastnosť sa matematicky používa v nedeterministických výpočtových modeloch, ako je nedeterministický konečný automat.
Neurčitý algoritmus je schopný vykonať na deterministickom počítači, ktorý má neobmedzený počet paralelných procesorov. Neurčitý algoritmus má obvykle dve fázy a výstupné kroky. Prvou fázou je hádajúca fáza, ktorá využíva ľubovoľné znaky na spustenie problému.
Druhá fáza je overovacia fáza, ktorá vráti true alebo false pre zvolený reťazec. Existuje mnoho problémov, ktoré možno konceptualizovať pomocou nedeterministických algoritmov vrátane nevyriešeného problému P vs NP v teórii výpočtovej techniky.
Pri riešení problémov, ktoré umožňujú viacnásobné výsledky, sa používajú nedeterministické algoritmy. Každý výsledok, ktorý nedeterministický algoritmus vytvára, je platný bez ohľadu na výber algoritmu počas vykonávania.
