busqueda - ¿La complejidad del tiempo de Prolog es mejor que la fuerza bruta ingenua?
busqueda en anchura inteligencia artificial (5)
En mi humilde opinión, depende del problema. Si realmente se puede resolver solo por medio de la fuerza bruta y el rastreo, no creo que (incluso un " mejor " ideal) Prolog sería más rápido que, por ejemplo, un programa C bien escrito.
Por otro lado, si tiene ese tipo de problema para la solución del cual Prolog puede usar su base de datos y enfoque deductivo (por lo tanto, no necesariamente retroceder la fuerza bruta), podría tener un mejor rendimiento que otro programa de retroceso de fuerza bruta.
Al final, cada lenguaje de programación termina creando código máquina que se ejecuta en su CPU para (con suerte) resolver su problema. El mismo código de máquina también puede ser producido por otros idiomas o más o menos directamente por el programador. Entonces, en absoluto, Prolog es una buena manera de resolver algún tipo de problema, pero no tiene que ser la mejor / más rápida / única alternativa.
¿Es la complejidad del tiempo para resolver algo en (el mejor) Prólogo mejor que una implementación ingenua de retroceso de fuerza bruta?
Digo el lenguaje Prolog en general ... Me pregunto si hay algún algoritmo bien conocido para esto, por ejemplo, que hacer ''hacer Prólogo'' usando call / cc backtracking en Scheme sea una mala elección.
EDITAR: al "resolver cualquier cosa" me refiero a todos los programas de Prolog. La "pregunta en una pregunta": me pregunto sobre el diseño del lenguaje: si las continuaciones completas tienen alguna utilidad práctica sobre las continuas parciales (las ventajas principales son Prolog-esque, pero que no son graves si no pueden competir en complejidad de tiempo) con Prolog), y también si otro lenguaje podría absorber completamente Prolog o si hay optimizaciones posibles mediante la restricción de programas a un formulario Prolog (análogo a la optimización posible en Fortran sobre C).
EDITAR: por complejidad de tiempo quise decir gran O, es decir, poda que no sería posible emulando Prolog ingenuamente en un lenguaje general.
La pregunta dentro de su pregunta parece ser, si escribo un código similar a Prolog en Scheme, ¿funcionará peor que si escribo Prolog en Prolog?
No hay una respuesta directa. La verdad es que la parte de tu problema que se correlaciona muy bien con Prolog probablemente funcionará peor de lo que sería en Prolog. ¿Por qué? Debido a que los intrínsecos de Prolog están escritos en Prolog, donde sus intrínsecos están escritos en Scheme. Como señala @CommuSoft con append/3 , la implementación de Prolog de las funciones intrínsecas puede aprovechar las fortalezas de Prolog. Vas a estar luchando una batalla cuesta arriba en estas partes. Además, las implementaciones de Prolog que tenemos son lo suficientemente antiguas como para haber pasado décadas trabajando para mejorar el rendimiento de la unificación, porque ese es el área interesante aquí.
Al mismo tiempo, la mayoría de los programas de Prolog terminan con algunos bits de procedimiento. Esos bits probablemente no sean competitivos con C o Scheme, porque no son tan divertidos de optimizar y cualquier investigación que haya que hacer sobre esto estaba sucediendo en Scheme y ML en su lugar. Entonces ganarás en esas áreas.
Como usuario de Scheme, creo que le resultaría más rentable escribir programas en el estilo Scheme: funcional, con una pizca de macros para darle una sensación declarativa. Si tiene un problema embarazosamente bueno para Prolog, siempre puede lanzar miniKanren , pero manténgalo acordonado del resto de su programa. Deje que su lenguaje sea su idioma.
No estoy de acuerdo con @ahuemmer sobre C versus Prolog solo porque el trabajo es limitado y los programas tienen muchos aspectos además del rendimiento. Los costos de autoría de C son mucho más altos, por lo que te comprometerás más con las estrategias más pobres y terminarás con un código menos flexible. Incluso si limita su espacio problemático a algo pequeño y bien definido, el programador Prolog tendrá más tiempo para experimentar y descubrir una mejor solución, posiblemente con una mejor complejidad de tiempo. Si estamos hablando de cantidades ilimitadas de mano de obra, la versión C probablemente superará a la primera versión de Prolog. Pero debes considerar todas las dimensiones.
En general, creo que es más importante adaptar el programador al idioma que el idioma del problema.
Pure Prolog (sin el operador de "corte", o características imperativas) sobresale en un aspecto: para una cierta clase de problemas, es un "procedimiento de refutación completa". Si el problema no tiene solución, el programa Prolog terminará y anunciará la ausencia de soluciones. Por otro lado, si el problema tiene soluciones, el programa puede encontrar ninguna o algunas o todas, y no puede terminar.
Si usa funciones o cortes imperativos, todas las apuestas están desactivadas.
Prolog a veces puede manejar problemas con infinitas respuestas, si las respuestas tienen el tipo correcto de patrón.
Una búsqueda ingenua de fuerza bruta seguirá siendo una búsqueda ingenua de fuerza bruta cuando se traduzca literalmente a Prolog.
Está bien: Plain Prolog es muy adecuado para describir y ejecutar búsquedas de fuerza bruta. Sin embargo, es probable que no pueda vencer una versión de bajo nivel optimizada a mano de cualquier búsqueda de fuerza bruta con una búsqueda de fuerza bruta escrita en Prolog. Por otro lado, Prolog es tan fácil y conveniente de escribir que es probable que pronto encuentre mejores estrategias de búsqueda con un poco de creación de prototipos, y estas otras estrategias a menudo superan fácilmente cualquier implementación de fuerza bruta por un amplio margen. E incluso cuando se lo traduce ingenuamente, Prolog es bastante bueno para rastrear y lo hace de manera eficiente dentro de algunos (más pequeños o más grandes, dependiendo de la implementación de Prolog que uses) factor de código de nivel inferior.
Sin embargo, la ventaja clave que Prolog tiene sobre muchos otros lenguajes al describir los problemas de búsqueda son las limitaciones : debido a la llamada propagación de restricciones, el espacio de búsqueda a menudo se puede eliminar de manera significativa y automática . No son necesarias disposiciones especiales de su parte: el solucionador de restricciones lo hará por usted.
La promesa de restricciones, y esa promesa se ha convertido en realidad en gran medida, es que (1) usted declara los requisitos y (2) el motor de Prolog encuentra la solución para usted. Consulte clpfd para ver una instancia muy importante de este esquema.
Por lo tanto, sugiero la pregunta: ¿ en cualquier idioma, qué tan fácil es convertir una búsqueda ingenua de fuerza bruta en una estrategia de búsqueda más informada? Después de todo, así es como las mejoras realmente significativas suelen ser posibles.
En Prolog, la respuesta es a menudo: Muy fácil . En la mayoría de los otros idiomas, no tanto.
Dado que preguntas para resolver cualquier cosa , definitivamente hay problemas que Prolog resuelve en tiempo lineal. Por ejemplo, el siguiente predicado append/3 :
append([H|A],B,[H|R]) :-
append(A,B,R).
append([],L,L).
Ahora, dado que en cada paso, solo hay un predicado candidato, no hay ramificación, por lo tanto, no hay una complejidad de tiempo exponencial. El predicado se ejecuta de forma lineal en la longitud de la primera lista.
Además, uno puede permitir la presentación en Prolog que puede dar lugar a algún tipo de programación dinámica que puede convertir la fuerza bruta en algoritmos de retroceso a veces en algoritmos rápidos.