Tartalomjegyzék:
- Meghatározás - Mit jelent a nem determinisztikus algoritmus?
- A Techopedia magyarázza a nem determinisztikus algoritmust
Meghatározás - Mit jelent a nem determinisztikus algoritmus?
A nem determinisztikus algoritmus különböző kimeneteket biztosíthat ugyanazon bemenethez különböző végrehajtásokon. Ellentétben a determinisztikus algoritmussal, amely ugyanazon bemenethez csak egyetlen kimenetet állít elő, még különböző futtatások esetén is, a nem determinisztikus algoritmus különböző útvonalakon halad, hogy elérje a különböző eredményeket.
A nem determinisztikus algoritmusok hasznosak hozzávetőleges megoldások megtalálásához, ha egy pontos megoldást nehéz vagy költséges meghatározni egy determinisztikus algoritmussal.
A Techopedia magyarázza a nem determinisztikus algoritmust
A nem determinisztikus algoritmus egyik példája egyidejű algoritmusok végrehajtása versenyfeltételekkel, amelyek különböző kimeneteket mutathatnak különböző futásokon. Ellentétben a determinisztikus algoritmussal, amely egyetlen utat hajt be a bemenetről a kimenetre, a nemdeterinisztikus algoritmus számos útvonalat vehet fel, néhányuk ugyanabba a kimenetbe érkezik, mások pedig más kimenetekbe. Ezt a tulajdonságot matematikailag használják nem determinisztikus számítási modellekben, mint például a nem determinisztikus véges automata.
Egy nem determinisztikus algoritmus végrehajtható egy determinisztikus számítógépen, amely korlátlan számú párhuzamos processzorral rendelkezik. A nem determinisztikus algoritmusnak általában két fázisa és kimeneti lépése van. Az első szakasz a találgatás, amely tetszőleges karaktereket használ a probléma futtatásához.
A második fázis az ellenőrző fázis, amely igaz vagy hamis eredményt ad a kiválasztott karakterlánc számára. Számos probléma fogalmazható meg nem determinisztikus algoritmusok segítségével, ideértve a P vs NP megoldatlan problémáját a számításelméletben.
Nem determinisztikus algoritmusokat használunk a több eredményt lehetővé tevő problémák megoldására. A nem determinisztikus algoritmus minden eredménye érvényes, függetlenül attól, hogy az algoritmus a végrehajtás során milyen döntéseket hozott.
