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

From: Sergey Dymchenko <kit1980_at_gmail.com>
Date: Tue, 4 Oct 2011 04:54:20 +0300
Sorry, but do anyone has ideas how to improve (probably change the
model) for the problem?

On Sat, Oct 1, 2011 at 10:11 PM, Sergey Dymchenko <kit1980_at_gmail.com> wrote:
> 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 Tue Oct 04 2011 - 01:54:26 CEST

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