semantica - reglas en prolog

Cómo evitar que Prolog retroceda donde no debería

Question

Estoy intentando resolver un CSP en el que necesito distribuir cócteles sobre los camareros para que cada camarero tenga como máximo un cóctel y todos los cócteles se entregan a un barman. Lo resolví creando una lista de variables clpfd, primero dándoles el dominio completo de todos los cantineros y luego eliminando a todos los cantineros que no saben cómo preparar ese cóctel.
Mi código funciona, pero hay un problema: es demasiado lento. Si miro en el generador de perfiles, remove_domain se llama 2000 veces (para la entrada que estoy dando a mi programa), mientras que la estadística Redo es> 100 000. ¿Qué necesito cambiar en una de estas funciones (o ambas) para que Prolog no necesita retroceder?

produce_domains(_,_,[],[]) :- !.
produce_domains(Bartenders,NBartenders,[Cocktail|Cocktails],[Var|Vars]) :-
    Var in 1..NBartenders,
    remove_domain(Bartenders,NBartenders,Cocktail,Var),!,
    produce_domains(Bartenders,NBartenders,Cocktails,Vars),!.

remove_domain([],0,_,_) :- !.
remove_domain([Bartender|Bartenders],NBartenders,Cocktail,Var) :-
    (/+ member(Cocktail,Bartender) -> Var #/= NBartenders;!),!,
    NNBartenders is NBartenders - 1,
    remove_domain(Bartenders,NNBartenders,Cocktail,Var),!.

Ya he leído esta pregunta relacionada , pero estoy usando la última versión de Windows de SWI-Prolog (5.10.5), por lo que ese no debería ser el problema aquí.

Answer 1

¡No necesitas tantos !/0 : Prolog a menudo puede decir que tus predicados son deterministas.

Permítanme ofrecer primero la siguiente versión de su código. Utiliza nombres que son más relacionales, no contiene !/0 y usa predicados de orden superior para acortar el código.

:- use_module(library(clpfd)).

bartenders_cocktails_variables(Bs, Cs, Vs) :-
        length(Bs, LBs),
        maplist(bartenders_cocktail_variable(Bs, LBs), Cs, Vs).

bartenders_cocktail_variable(Bs, N, C, V) :-
        V in 1..N,
        foldl(compatible_bartender(C,V), Bs, 1, _).

compatible_bartender(C, V, Cs, N0, N1) :-
        (   member(C, Cs) -> true
        ;   V #/= N0
        ),
        N1 #= N0 + 1.

Tenga en cuenta que estoy contando hacia arriba en lugar de hacia abajo para enumerar a los camareros (que son solo listas de cócteles que pueden mezclar), ya que esto parece más natural. También pude omitir un (/+)/1 simplemente cambiando las ramas del if-then-else.

Consulta de ejemplo, que muestra que el predicado es determinista en este caso de uso:

?- bartenders_cocktails_variables([[a,b],[a,b],[x,y]], [x,a,b], Vars).
Vars = [3, _G1098, _G1101],
_G1098 in 1..2,
_G1101 in 1..2.

Vemos: Cocktail x debe ser mezclado por el tercer camarero, etc.

Creo que esta parte de su programa puede no ser responsable del lento rendimiento que está describiendo. ¿Tal vez otras partes de tu programa (involuntariamente) no son deterministas? Tal vez intente diferentes estrategias de etiquetado u otras limitaciones? Es posible que podamos ayudarlo más si publica más contexto.