algorithm - listas - reglas en prolog

¿Complejidad en los programas de Prolog?

Question

En Prolog, los problemas se resuelven usando backtracking. Es un paradigma declarativo en lugar de imperativo (como en C, PHP o Python). En este tipo de idiomas, ¿vale la pena pensar en términos de complejidad?

La forma natural en que piensas que los problemas parecen ser O (N ^ 2) como alguien señaló en esta pregunta .

Answer 1

Definitivamente puede analizar la complejidad de los programas Prolog, al igual que cualquier otro idioma. Ese problema particular que vinculó podría ser O (n ^ 2). Pero no todos los programas Prolog tendrán esta complejidad. Por ejemplo, puede escribir fácilmente un solucionador de SAT en Prolog, y ese problema es NP-Completo.

Answer 2

Depende completamente del problema.

por ejemplo, sumar una lista de números es O (N), por lo que puedo decir.

sum([],0).
sum(List,Total) :-
   sum(List,0,Total).

sum([],Total,Total).
sum([Head|Rest],Accumulator,Total) :-
    SoFar is Head + Accumulator,
    sum(Rest,SoFar,Total).

Las únicas acciones son la suma ("es") y la llamada recursiva, que deberían valer 1 cada una. Ambos se realizarán ~ una vez por elemento en la lista, por lo que las acciones totales deberían ser ~ 2N, que es O (N).

Answer 3

Es importante analizar la Complejidad en cualquier idioma, ya sea prólogo o cualquier lenguaje imperativo. Sin embargo, puedo darte algunos consejos para acelerar tus programas de prólogo

1. Siempre Siempre intente hacer que sus programas sean recursivos. Esto asegurará que su programa no se quede sin stack.
2. Intente utilizar el corte y el fracaso en sus programas donde sabe que no necesita más respuestas.
3. Intenta usar accumalators.
4. Consulte CLPFD, ayuda a reducir drásticamente el espacio de búsqueda que acelera su programa. Básicamente, elimina la mala elección antes de que su programa pueda dar marcha atrás y perder el tiempo explorando esas opciones.
5. Siempre escriba la mejor regla de resultado primero. (Esto realmente depende del problema, pero generalmente la regla del mejor caso es lo primero).