nondeterministic algorithm

nondeterministic algorithm (tsz. nondeterministic algorithms)

1. (informatika, mesterséges intelligencia) nemdeterminisztikus algoritmus

A nemdeterminisztikus algoritmus (angolul: nondeterministic algorithm) egy olyan elméleti számítási modell, amely nem egyetlen végrehajtási úton halad, hanem párhuzamosan több lehetőséget is kipróbál, mintha “varázsütésre” mindig a helyes választásra lépne. Ez nem azt jelenti, hogy véletlenszerű, hanem hogy több lehetséges döntés közül mindig a megfelelő kerül kiválasztásra – ha létezik.

Ez a fogalom elsősorban elméleti számítástudományban, különösen a komplexitáselméletben használatos, például az NP (nondeterministic polynomial time) osztály meghatározásakor.

Képzeld el, hogy ki akarsz jutni egy labirintusból:

• Deterministic algoritmus: módszeresen haladsz, pl. mindig jobbra fordulsz, majd balra, visszafordulsz, stb.
• Nondeterministic algoritmus: minden elágazásnál varázsütésszerűen azonnal a helyes irányba fordulsz – mintha minden lehetőséget párhuzamosan kipróbálnál, és azonnal a célhoz jutnál, ha létezik út.

• NP problémák vizsgálatakor: Egy probléma NP osztályba tartozik, ha létezik egy nemdeterminisztikus algoritmus, amely polinomiális idő alatt megoldja.
• Algoritmustervezési elméletben: Egyes algoritmusokat úgy írunk le, mintha „kitalálnák” a jó megoldást – ezek nem reálisak, de segítenek bizonyítani, hogy egy probléma megoldható bizonyos időn belül, ha lenne ilyen képesség.

Adott egy gráf. Létezik-e olyan körút, amely minden csúcsot pontosan egyszer érint?

• Megpróbálsz minden lehetséges csúcslátogatási sorrendet.
• Ez n-faktoriális időigényű (robusztus, de nagyon lassú).

• “Kitalálod” a jó sorrendet.
• Egy lépésben mindig azt az élt választod, amely biztosan célra vezet.
• A nemdeterminisztikus gép így polinomiális idő alatt találja meg a megoldást (ha van).

function NonDeterministicSubsetSum(S, T):
    nondeterministically choose subset A ⊆ S
    if sum(A) == T:
        accept
    else:
        reject

🟢 Ha létezik olyan részhalmaz, amely összege T, akkor a gép „ki tudja találni” ezt a részhalmazt azonnal.

A nemdeterminisztikus algoritmusokat nemdeterminisztikus Turing-gépeken értelmezzük:

• Egy adott állapotból több különböző átmenet is lehet.
• A gép „párhuzamos valóságokban” kipróbálja mindet.
• Akkor fogad el egy bemenetet, ha legalább egy végrehajtási útvonal eljut az elfogadó állapotba.

• Lehetővé teszik a polinomiális igazolhatóság fogalmát (NP osztály).
• Segítenek elválasztani, hogy mi az, ami gyorsan ellenőrizhető, de nem feltétlenül gyorsan megoldható.
• Használhatók algoritmusok tervezésének kiindulási modelljeiként.

• Nem implementálhatók a klasszikus számítógépeken – hiszen nincs „varázs-szétválás”.
• Elméleti konstrukciók – nem valódi algoritmusok, hanem modellek.
• A determinisztikus megfelelőik gyakran exponenciális idejűek.

• nondeterministic algorithm - Szótár.net (en-hu)
• nondeterministic algorithm - Sztaki (en-hu)
• nondeterministic algorithm - Merriam–Webster
• nondeterministic algorithm - Cambridge
• nondeterministic algorithm - WordNet
• nondeterministic algorithm - Яндекс (en-ru)
• nondeterministic algorithm - Google (en-hu)
• nondeterministic algorithm - Wikidata
• nondeterministic algorithm - Wikipédia (angol)