¿Por qué esta restricción de solución de CLP(FD) se está ejecutando lentamente y cómo puedo depurarlo?
Estoy aprendiendo Prolog al hacer los desafíos de Advent of Code.
Advertencia de spoilers para el día 7 de Advent of Code 2021:
El objetivo es: dada una lista de números naturales “n_1,…, n_k”, encontrar:
min_(x\in \N) \sum_i=0^k |x – n_i|
En el código a continuación, “norm1” calcula el sumando, “cost” calcula la suma para un determinado “x” y “lowest_cost” calcula el mínimo de todos los “x”.
norm1(X, Y, N) :- N #= abs(X - Y).
cost(Nums, X, Cost) :-
max_list(Nums, MaxX),
min_list(Nums, MinX),
X in MinX..MaxX,
maplist(norm1(X), Nums, Costs),
sum(Costs, #=, Cost).
lowest_cost(Nums, Cost) :-
cost(Nums, X, Cost),
once(labeling([min(Cost)], [X, Cost])).
Algunas consultas de ejemplo:
?- lowest_cost([10,11,12], Cost).
Cost = 2.
?- cost([2,4,6,8], 4, Cost).
Cost = 8.
?- cost([2,4,6,8], 5, Cost).
Cost = 8.
?- cost([2,4,6,8], 8, Cost).
Cost = 12.
?- lowest_cost([2,4,6,8], Cost).
Cost = 8.
Con listas cortas, esto resuelve correctamente y rápidamente, pero cuando lo intento con la entrada de longitud completa de 1,000, se ejecuta indefinidamente.
La forma en que imagino que esto se resolvería es simplemente probando todos los “X” en el dominio, calculando el costo para cada uno y tomando el menor. Sin embargo, esto no parece ser el caso; el tiempo parece escalar de manera superlineal con la longitud de la lista y no en absoluto con el rango de los números en la lista.
- ¿Cómo puedo indicarle a CLP(FD) que busque de la manera que describí, o de otra manera eficiente?
- ¿Cómo puedo entender mejor lo que el solucionador está tratando de hacer? “trace” es bastante desordenado y no estoy seguro de cómo obtener alguna idea de él.
davy.ai
indomain_middleen lugar de la estrategia predeterminadaindomain. Esta estrategia comienza dividiendo el dominio por la mitad y explorando primero el valor medio, lo cual suele ser un buen punto de partida para encontrar la solución óptima. Para utilizar esta estrategia, puedes agregar la siguiente línea antes de llamar alabelingenlowest_cost:fd_statisticspara obtener información sobre el proceso de búsqueda. Por ejemplo, puedes agregar la siguiente línea antes de llamar alabelingenlowest_cost:Esto imprimirá el tiempo que tarda el solucionador, así como estadísticas como el número de nodos explorados y el número de fallos. Al comparar las estadísticas de diferentes estrategias, puedes tener una idea de cuáles son más eficientes para tu problema. Además, puedes utilizar el argumento
LabeledVarsdefd_statisticspara obtener una lista de variables y sus dominios después de la etiquetación, lo cual puede ayudarte a solucionar cualquier problema con la solución.