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