Sisällysluettelo:
- Määritelmä - mitä ei-deterministinen algoritmi tarkoittaa?
- Techopedia selittää ei-deterministisen algoritmin
Määritelmä - mitä ei-deterministinen algoritmi tarkoittaa?
Ei-deterministinen algoritmi voi tarjota erilaisia lähtöjä samalle tulolle eri suorituksissa. Toisin kuin deterministinen algoritmi, joka tuottaa vain yhden ulostulon samalle tulolle jopa eri ajoilla, ei-deterministinen algoritmi kulkee eri reiteillä saavuttaakseen eri tulokset.
Ei-deterministiset algoritmit ovat hyödyllisiä etsittäessä likimääräisiä ratkaisuja, kun tarkkaa ratkaisua on vaikea tai kallis saada johdettua determinististä algoritmia käyttämällä.
Techopedia selittää ei-deterministisen algoritmin
Yksi esimerkki epädeterministisestä algoritmista on samanaikaisten algoritmien suorittaminen rotuolosuhteiden kanssa, jotka voivat näyttää erilaisia lähtöjä eri ajoilla. Toisin kuin deterministinen algoritmi, joka kulkee yhden polun tulosta ulostuloon, ei-deterministinen algoritmi voi kulkea monta polkua, joissa jotkut saapuvat samoihin lähtöihin ja toiset saapuvat eri lähtöihin. Tätä ominaisuutta käytetään matemaattisesti ei-deterministisissä laskentamalleissa, kuten ei-deterministisissä äärellisissä automaateissa.
Ei-deterministinen algoritmi kykenee suorittamaan deterministisellä tietokoneella, jolla on rajaton määrä rinnakkaisprosessoreita. Ei-deterministisellä algoritmilla on yleensä kaksi vaihetta ja lähtövaihetta. Ensimmäinen vaihe on arvailu, joka käyttää mielivaltaisia merkkejä ongelman suorittamiseen.
Toinen vaihe on varmennusvaihe, joka palauttaa valitulle merkkijonolle tosi tai epätosi. On monia ongelmia, jotka voidaan käsitellä epädeterministisillä algoritmeilla, mukaan lukien P vs NP: n ratkaisematon ongelma laskentateoriassa.
Ei-deterministisiä algoritmeja käytetään ratkaisemaan useita tuloksia mahdollistavia ongelmia. Jokainen lopputulos, jonka epädeterministinen algoritmi tuottaa, on pätevä, riippumatta algoritmin suorittamista valinnoista.
