algorithm - porque - determinista estadistica
¿Por qué retroceder hace que un algoritmo no sea determinista? (9)
Considere un algoritmo para colorear un mapa del mundo. No se puede usar color en países adyacentes. El algoritmo comienza arbitrariamente en un país y lo colorea de un color arbitrario. Así que se mueve, coloreando países, cambiando el color en cada paso hasta que "oh, oh", dos países adyacentes tienen el mismo color. Bueno, ahora tenemos que dar marcha atrás y hacer una nueva elección de color. Ahora no estamos haciendo una elección como lo haría un algoritmo no determinista, eso no es posible para nuestras computadoras deterministas. En cambio, estamos simulando el algoritmo no determinista con retroceso. Un algoritmo no determinista habría hecho la elección correcta para cada país.
Así que he tenido al menos dos profesores mencionando que retroceder hace que un algoritmo no sea determinista sin dar demasiada explicación de por qué es así. Creo que entiendo cómo sucede esto, pero me cuesta ponerlo en palabras. ¿Podría alguien darme una explicación concisa de la razón de esto?
Experimento mental:
1) Oculto a la vista hay una distribución de cargas eléctricas de la cual se siente una fuerza y se mide el campo potencial que crean. Dime exactamente las posiciones de todos los cargos.
2) Tome algunos cargos y organícelos. Dime exactamente el campo potencial que crean.
Solo la segunda pregunta tiene una respuesta única. Esta es la no exclusividad de los campos vectoriales . Esta situación puede ser en analogía con algunos algoritmos no deterministas que está considerando. Considere además los límites matemáticos que no existen porque tienen diferentes respuestas según la dirección desde la que se aproxima a una discontinuidad.
Las máquinas Turing no deterministas (NDTM) podrían tomar múltiples ramas en un solo paso. Los DTM, por otro lado, siguen un proceso de prueba y error.
Puede pensar en DTM como computadoras comunes. Por el contrario, las computadoras cuánticas son parecidas a las NDTM y pueden resolver problemas no determinísticos mucho más fácilmente (por ejemplo, ver su aplicación en la criptografía de última hora). Así que retroceder sería en realidad un proceso lineal para ellos.
No es tanto el caso que retroceder hace que un algoritmo no sea determinista.
Por el contrario, generalmente necesita retroceder para procesar un algoritmo no determinista, ya que (por la definición de no determinista) usted no sabe qué camino tomar en un momento particular en su procesamiento, pero en su lugar debe probar varios.
Si permite retroceder, permite un bucle infinito en su programa, lo que lo hace no determinista ya que la ruta real tomada siempre puede incluir un bucle más.
Solo citaré wikipedia:
Un lenguaje de programación no determinista es un lenguaje que puede especificar, en ciertos puntos del programa (llamados "puntos de elección"), varias alternativas para el flujo del programa. A diferencia de una instrucción if-then, el programador no especifica directamente el método de elección entre estas alternativas; el programa debe decidir en tiempo de ejecución entre las alternativas, a través de algún método general aplicado a todos los puntos de elección. Un programador especifica un número limitado de alternativas, pero luego el programa debe elegir entre ellas. ("Elegir" es, de hecho, un nombre típico para el operador no determinista). Se puede formar una jerarquía de puntos de elección, con opciones de nivel superior que conducen a ramas que contienen opciones de nivel inferior dentro de ellas.
Un método de elección está incorporado en los sistemas de retroceso, en los que algunas alternativas pueden "fallar", haciendo que el programa retroceda y pruebe otras alternativas. Si todas las alternativas fallan en un punto de elección particular, entonces una rama completa falla, y el programa retrocederá más, a un punto de elección más antiguo. Una complicación es que, como cualquier elección es tentativa y puede rehacerse, el sistema debe ser capaz de restaurar los estados del programa anterior anulando los efectos secundarios causados por la ejecución parcial de una rama que finalmente falló.
Fuera del artículo Programación no determinista .
El tiempo de ejecución de retroceso en una computadora determinista es factorial, es decir, está en O (n!).
Cuando una computadora no determinista puede adivinar de forma instantánea correctamente en cada paso, una computadora determinista debe probar todas las combinaciones posibles de opciones.
Como es imposible construir una computadora no determinista, lo que su profesor probablemente quiso decir es lo siguiente:
Un problema comprobadamente difícil en la clase de complejidad NP (todos los problemas que una computadora no determinista puede resolver de manera eficiente al adivinar siempre correctamente) no puede resolverse de manera más eficiente en computadoras reales que retrocediendo.
La afirmación anterior es verdadera, si las clases de complejidad P (todos los problemas que una computadora determinista puede resolver de manera eficiente) y NP no son lo mismo. Este es el famoso problema P vs. NP. El Clay Mathematics Institute ha ofrecido un premio de $ 1 millón para su solución, pero el problema ha resistido las pruebas durante muchos años. Sin embargo, la mayoría de los investigadores creen que P no es igual a NP.
Una manera simple de resumirlo sería: Los problemas más interesantes que una computadora no determinista podría resolver de manera eficiente al adivinar correctamente, son tan difíciles que una computadora determinista probablemente tendría que probar todas las combinaciones posibles de opciones, es decir, utilizar el rastreo.
Escribí un corredor de laberintos que utiliza el rastreo (por supuesto), que usaré como ejemplo.
Caminas por el laberinto. Cuando llegas a un cruce, das la vuelta a una moneda para decidir qué ruta seguir. Si elige un callejón sin salida, vuelva al cruce y tome otra ruta. Si los probó todos, regrese a la unión anterior. Este algoritmo no es determinista, no por el retroceso, sino por el lanzamiento de monedas.
Ahora cambie el algoritmo: cuando llegue a un cruce, siempre intente primero con la ruta más a la izquierda que aún no haya probado. Si eso lleva a un callejón sin salida, regresa al cruce y nuevamente prueba la ruta más a la izquierda que aún no has probado. Este algoritmo es determinista. No hay ninguna posibilidad involucrada, es predecible: siempre seguirás la misma ruta en el mismo laberinto.
Me gusta la analogía del laberinto. Pensemos en el laberinto, por simplicidad, como un árbol binario, en el que solo hay un camino.
Ahora desea probar una primera búsqueda en profundidad para encontrar la salida correcta del laberinto.
Una computadora no determinista, en cada punto de ramificación, duplicaría / clonaría y ejecutaría cada uno de los cálculos adicionales en paralelo. Es como si la persona en el laberinto se duplicara / clonara (como en la película Prestigio) en cada punto de ramificación y enviara una copia de él mismo a la subárraga izquierda del árbol y la otra copia de él mismo a la sub-rama derecha de el árbol.
Las computadoras / personas que terminan en un callejón sin salida mueren (terminan sin respuesta).
Solo una computadora sobrevivirá (finalizará con una respuesta), la que salga del laberinto.
La diferencia entre retroceder y no determinar es la siguiente.
En el caso de retroceder solo hay una computadora viva en un momento dado, él hace el truco tradicional de laberinto, simplemente marca su camino con una tiza y cuando llega a un punto muerto simplemente retrocede a un punto de ramificación cuyas ramas secundarias él todavía no exploró completamente, al igual que en una primera búsqueda en profundidad.
A DIFERENCIA DE :
Una computadora no deteminista puede clonarse a sí misma en cada punto de ramificación y verificar la salida ejecutando búsquedas paralelas en las ramificaciones secundarias.
Entonces, el algoritmo de retroceso simula / emula la capacidad de clonación de la computadora no determinista en una computadora secuencial / no paralela / determinista.