Taula de continguts:
Definició: què significa l'algoritme no determinat?
Un algorisme no determinista pot proporcionar sortides diferents per a la mateixa entrada de diferents execucions. A diferència d’un algorisme determinista que produeix una única sortida per a la mateixa entrada, fins i tot en diferents tirades, un algorisme no determinista viatja en diverses rutes per arribar als diferents resultats.
Els algorismes no deterministes són útils per trobar solucions aproximades, quan una solució exacta és difícil o costosa derivar mitjançant un algorisme determinista.
Techopedia explica l'algoritme no determinat
Un exemple d'algorisme no determinista és l'execució d'algorismes concurrents amb condicions de cursa, que poden presentar diferents sortides en diferents tirades. A diferència d’un algorisme determinista que recorre un únic camí des d’entrada a sortida, un algorisme no determinista pot agafar molts camins, alguns arribant a les mateixes sortides, i d’altres arribant a sortides diferents. Aquesta característica s'utilitza matemàticament en models de càlcul no determinista com l'autòmat finit no determinista.
Un algorisme no determinista és capaç d'executar en un equip determinista que té un nombre il·limitat de processadors paral·lels. Un algorisme no determinista sol tenir dues fases i passos de sortida. La primera fase és la fase d’endevinar, que fa ús de caràcters arbitraris per a executar el problema.
La segona fase és la fase de verificació, que retorna cert o fals per a la cadena escollida. Hi ha molts problemes que poden ser conceptualitzats mitjançant l'ajut d'algorismes no deterministes, incloent el problema no resolt de P vs NP en la teoria de la computació.
Els algorismes no deterministes s’utilitzen per resoldre problemes que permeten resultats múltiples. Tots els resultats que produeix l'algorisme no determinista són vàlids, independentment de les opcions preses per l'algorisme durant l'execució.
