Definición - ¿Qué significa algoritmo no determinista?
Un algoritmo no determinista puede proporcionar diferentes salidas para la misma entrada en diferentes ejecuciones. A diferencia de un algoritmo determinista que produce una única salida para la misma entrada incluso en diferentes ejecuciones, un algoritmo no determinista viaja en varias rutas para llegar a los diferentes resultados.
Los algoritmos no deterministas son útiles para encontrar soluciones aproximadas, cuando una solución exacta es difícil o costosa de derivar usando un algoritmo determinista.
Techinfo explica el algoritmo no determinista
Un ejemplo de algoritmo no determinista es la ejecución de algoritmos concurrentes con condiciones de carrera, que pueden exhibir diferentes salidas en diferentes ejecuciones. A diferencia de un algoritmo determinista que viaja por una única ruta desde la entrada a la salida, un algoritmo no determinista puede tomar muchas rutas, algunas llegan a las mismas salidas y otras llegan a diferentes salidas. Esta característica se utiliza matemáticamente en modelos de cálculo no deterministas como autómatas finitos no deterministas.
Un algoritmo no determinista puede ejecutarse en una computadora determinista que tiene un número ilimitado de procesadores en paralelo. Un algoritmo no determinista suele tener dos fases y pasos de salida. La primera fase es la fase de adivinanzas, que utiliza caracteres arbitrarios para ejecutar el problema.
La segunda fase es la fase de verificación, que devuelve verdadero o falso para la cadena elegida. Hay muchos problemas que pueden conceptualizarse con la ayuda de algoritmos no deterministas, incluido el problema no resuelto de P vs NP en la teoría de la computación.
Los algoritmos no deterministas se utilizan para resolver problemas que permiten múltiples resultados. Todos los resultados que produce el algoritmo no determinista son válidos, independientemente de las elecciones realizadas por el algoritmo durante la ejecución.