Cuprins:
Definiție - Ce înseamnă Algoritmul Neterministic?
Un algoritm non-determinist poate furniza ieșiri diferite pentru aceeași intrare la execuții diferite. Spre deosebire de un algoritm determinist care produce o singură ieșire pentru aceeași intrare chiar și pe diferite rulări, un algoritm non-determinist călătorește pe diverse rute pentru a ajunge la rezultatele diferite.
Algoritmii nedeterministi sunt utili pentru a găsi soluții aproximative, atunci când o soluție exactă este dificilă sau costisitoare pentru a obține folosind un algoritm determinist.
Techopedia explică algoritmul nedeterminist
Un exemplu de algoritm nedeterminist este execuția algoritmilor concurenti cu condiții de cursă, care pot prezenta ieșiri diferite pe diferite rulări. Spre deosebire de un algoritm determinist care parcurge o singură cale de la intrare la ieșire, un algoritm non-determinist poate lua multe căi, unele ajungând la aceleași ieșiri, iar altele ajung la ieșiri diferite. Această caracteristică este utilizată matematic în modele de calcul nedeterministe, cum ar fi automatul finit nedeterminist.
Un algoritm nedeterminist este capabil să execute pe un computer determinist care are un număr nelimitat de procesoare paralele. Un algoritm nedeterminist are de obicei două faze și pași de ieșire. Prima fază este faza de ghicire, care folosește caractere arbitrare pentru a rula problema.
A doua fază este faza de verificare, care returnează adevărat sau fals pentru șirul ales. Există multe probleme care pot fi conceptualizate cu ajutorul algoritmilor nedeterministi, incluzând problema nerezolvată a P vs NP în teoria computerelor.
Algoritmii nedeterministi sunt folosiți în rezolvarea problemelor care permit rezultate multiple. Fiecare rezultat pe care îl produce algoritmul nedeterminist este valabil, indiferent de alegerile luate de algoritm în timpul execuției.
