[eclipse-clp-users] Minimizing a parameter that depends on global state

From: Sergey Dymchenko <kit1980_at_gmail.com>
Date: Sat, 1 Oct 2011 22:11:33 +0300
Hello!

I have the following problem:

There is a system. There is an array of queries to the system - array
of integers :: 1..S, probably with repetitions, one integer for each
step.
On each step the system can have an integer state :: 1..S, and state
must not be equal to the query for this step.
We need to find a list of feasible states, such as number of switches
of the system states is minimal.

For example, if S = 2, and Queries = [1, 2, 1], the answer is States =
[2, 1, 2], number of switches is 2 (from 2 to 1 and from 1 to 2).
If S = 3 and Queries = [1, 2, 1], the answer is States = [3, 3, 3],
number of switches is 0.

I know a simple algorithmic solution for the problem, but I want to
solve it with CLP.

I wrote a program, which works perfectly for small inputs but it takes
forever on large inputs when length on Queries is around 100 or more
(because number of possible solutions is huge and there is almost no
pruning).

Any ideas how to speed it up?

:- lib(ic).
:- lib(branch_and_bound).

% From the 2nd state:
% if the current state is not equal to the previous one -
% increment switches count
switches(States, Switches_count) :-
    dim(States, [Q]),
    ( count(I, 2, Q), fromto(0, C_previous, C_current, C), param(States) do
        C_current = (States[I] =\= States[I - 1]) + C_previous ),
    Switches_count #= eval(C).

model(S, Queries, States) :-
    dim(Queries, [Q]),
    dim(States, [Q]),
    States :: 1..S,
    ( count(I, 1, Q), param(Queries, States) do
        Queries[I] #\= States[I] ).

find(States) :-
    switches(States, S),
    bb_min(
        search(States, 0, occurrence, indomain_split, complete, []),
        S, bb_options{strategy: restart}).

% solve(2, [](1, 2, 1), S).
% solve(3, [](1, 2, 1), S).
solve(S, Queries, States) :-
    model(S, Queries, States),
    find(States).
Received on Sat Oct 01 2011 - 19:11:39 CEST

This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET