From c7caf6b7a9cd6455ffd9b3367391636c0ef5686d Mon Sep 17 00:00:00 2001 From: Markus Triska Date: Mon, 25 Jul 2022 20:08:54 +0200 Subject: [PATCH] =?utf8?q?ENHANCED:=20CLP(=E2=84=A4):=20Reduce=20redundant?= =?utf8?q?=20propagator=20invocations=20during=20all=5Fdistinct/1=20filter?= =?utf8?q?ing?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit First, the current propagator is now logged and not re-triggered during filtering. Second, and more significantly, all neq_num/2 constraints are scheduled and processed before more global constraints are invoked. In this way, all the distilled information can be taken into account by subsequently invoked global constraints. These changes yield a 3-fold improvement in several Sudoku instances, and a significant runtime reduction in social golfer instance 8-4-9. --- src/lib/clpz.pl | 75 +++++++++++++++++++++++++++++++------------------ 1 file changed, 47 insertions(+), 28 deletions(-) diff --git a/src/lib/clpz.pl b/src/lib/clpz.pl index 94930932..6575a32d 100644 --- a/src/lib/clpz.pl +++ b/src/lib/clpz.pl @@ -123,6 +123,8 @@ :- use_module(library(si)). :- use_module(library(freeze)). :- use_module(library(arithmetic)). +:- use_module(library(debug)). +:- use_module(library(format)). % :- use_module(library(types)). @@ -2241,8 +2243,8 @@ all_distinct(Ls) :- fd_must_be_list(Ls, all_distinct(Ls)-1), maplist(fd_variable, Ls), make_propagator(pdistinct(Ls), Prop), - distinct_attach(Ls, Prop, []), - trigger_once(Prop). + new_queue(Q0), + phrase((distinct_attach(Ls, Prop, []),trigger_prop(Prop),do_queue), [Q0], _). %% nvalue(?N, +Vars). % @@ -4050,12 +4052,13 @@ trigger_props(fd_props(Gs,Bs,Os)) --> trigger_props_([]) --> []. trigger_props_([P|Ps]) --> trigger_prop(P), trigger_props_(Ps). -trigger_prop(_P) :- true. % TODO: What to do? +trigger_prop(P) :- trigger_once(P). trigger_prop(Propagator) --> { propagator_state(Propagator, State) }, ( { State == dead } -> [] ; { get_attr(State, clpz_aux, queued) } -> [] + ; { bb_get('$clpz_current_propagator', C), C == State } -> [] ; % passive %{ format("triggering: ~w\n", [Propagator]) }, { put_attr(State, clpz_aux, queued) }, @@ -4148,12 +4151,13 @@ no_reactivation(pgcc_single(_,_)). %no_reactivation(scalar_product(_,_,_,_)). activate_propagator(propagator(P,State)) --> + % { portray_clause(running(P)) }, ( State == dead -> [] ; { del_attr(State, clpz_aux) }, ( { no_reactivation(P) } -> - %b_setval('$clpz_current_propagator', State), TODO - run_propagator(P, State) - %b_setval('$clpz_current_propagator', []) + { bb_b_put('$clpz_current_propagator', State) }, + run_propagator(P, State), + { bb_b_put('$clpz_current_propagator', []) } ; run_propagator(P, State) ) ). @@ -4199,7 +4203,8 @@ queue_get_arg_(Queue, Which, Element) :- ). queue_enabled --> state(queue(_,_,_,Aux)), { \+ get_atts(Aux, +enabled(false)) }. - +disable_queue --> state(queue(_,_,_,Aux)), { put_atts(Aux, +enabled(false)) }. +enable_queue --> state(queue(_,_,_,Aux)), { put_atts(Aux, +enabled(true)) }. portray_propagator(propagator(P,_), F) :- functor(P, F, _). @@ -4394,14 +4399,14 @@ run_propagator(pdifferent(Left,Right,X,_), MState) --> run_propagator(pexclude(Left,Right,X), MState). run_propagator(pexclude(Left,Right,X), _) --> - { ( ground(X) -> - disable_queue, - exclude_fire(Left, Right, X), - enable_queue - ; true - ) }. + ( ground(X) -> + disable_queue, + exclude_fire(Left, Right, X), + enable_queue + ; true + ). -run_propagator(pdistinct(Ls), _MState) --> { distinct(Ls) }. +run_propagator(pdistinct(Ls), _MState) --> distinct(Ls). run_propagator(pnvalue(N, Vars), _MState) --> { propagate_nvalue(N, Vars) }. @@ -4435,8 +4440,8 @@ run_propagator(pgcc(Vs, _, Pairs), _) --> { gcc_global(Vs, Pairs) }. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% run_propagator(pcircuit(Vs), _MState) --> - { distinct(Vs), - propagate_circuit(Vs) }. + distinct(Vs), + { propagate_circuit(Vs) }. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -5933,12 +5938,12 @@ max_factor(L1, U1, L2, U2, Max) :- CSPs", AAAI-94, Seattle, WA, USA, pp 362--367, 1994 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ -distinct_attach([], _, _). -distinct_attach([X|Xs], Prop, Right) :- +distinct_attach([], _, _) --> []. +distinct_attach([X|Xs], Prop, Right) --> ( var(X) -> - init_propagator(X, Prop), - make_propagator(pexclude(Xs,Right,X), P1), - init_propagator(X, P1), + { init_propagator(X, Prop), + make_propagator(pexclude(Xs,Right,X), P1), + init_propagator(X, P1) }, trigger_prop(P1) ; exclude_fire(Xs, Right, X) ), @@ -6158,8 +6163,8 @@ with_local_attributes(Vars, Goal, Result) :- local_attributes(Result,Vars), true). -distinct(Vars) :- - with_local_attributes(Vars, +distinct(Vars) --> + { with_local_attributes(Vars, ( difference_arcs(Vars, FreeLeft, FreeRight0), length(FreeLeft, LFL), length(FreeRight0, LFR), @@ -6170,11 +6175,16 @@ distinct(Vars) :- maplist(g_g0, FreeLeft), scc(FreeLeft, g0_successors), maplist(dfs_used, FreeRight), - phrase(distinct_goals(FreeLeft), Gs)), Gs), + phrase(distinct_goals(FreeLeft), Gs)), Gs) }, disable_queue, - maplist(call, Gs), + neq_nums(Gs), enable_queue. +neq_nums([]) --> []. +neq_nums([neq_num(V,N)|VNs]) --> + % { portray_clause(neq_num(V, N)) }, + neq_num(V, N), neq_nums(VNs). + distinct_goals([]) --> []. distinct_goals([V|Vs]) --> { get_attr(V, edges, Es) }, @@ -6189,7 +6199,7 @@ distinct_goals_([flow_to(F,To)|Es], V) --> get_attr(To, lowlink, L2), L1 =\= L2 } -> { get_attr(To, value, N) }, - [clpz:neq_num(V, N)] + [neq_num(V, N)] ; [] ), distinct_goals_(Es, V). @@ -6381,6 +6391,10 @@ exclude_fire(Left, Right, E) :- all_neq(Left, E), all_neq(Right, E). +exclude_fire(Left, Right, E) --> + all_neq(Left, E), + all_neq(Right, E). + list_contains([X|Xs], Y) :- ( X == Y -> true ; list_contains(Xs, Y) @@ -6942,6 +6956,11 @@ vs_key_min_others([V|Vs], Key, Min0, Min, Others) :- ) ). +all_neq([], _) --> []. +all_neq([X|Xs], C) --> + neq_num(X, C), + all_neq(Xs, C). + all_neq([], _). all_neq([X|Xs], C) :- neq_num(X, C), @@ -6973,8 +6992,8 @@ circuit(Vs) :- ( L =:= 1 -> true ; neq_index(Vs, 1), make_propagator(pcircuit(Vs), Prop), - distinct_attach(Vs, Prop, []), - trigger_once(Prop) + new_queue(Q0), + phrase((distinct_attach(Vs, Prop, []),trigger_prop(Prop),do_queue), [Q0], _) ). neq_index([], _). -- 2.54.0