Hi, On 01/10/11 21:11, Sergey Dymchenko 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? This particular problem is probably solved faster with an integer programming model. *With IC:* [eclipse 5]: solve(3, [](1, 2, 1,1,2,1,3,3,2,3,1,2,1,2,3,1,3,2,1,3,1,2,3,3,1,1,2,1,3,1,2,3,1,2,3,1,2,3), S). Found a solution with cost 25 Found a solution with cost 24 ... Found a solution with cost 12 Found no solution with cost 0.0 .. 11.0 S = [](3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 3, 3, 3, 3, 2, 2, 1, 1, 2, 2, 2, 1, 1, 1, 3, 3, 3, 2, 2, 2, 1, 1, 3, 3, 2, 2, 1, 1) Yes (52.06s cpu) *With Eplex:* [eclipse 16]: solve(3, [](1, 2, 1,1,2,1,3,3,2,3,1,2,1,2,3,1,3,2,1,3,1,2,3,3,1,1,2,1,3,1,2,3,1,2,3,1,2,3), S). S = [](_864{1.0 .. 3.0 _at_ 3.0}, _881{1.0 .. 3.0 @ 3.0000000000000009}, _898{1.0 .. 3.0 _at_ 3.0}, _915{1.0 .. 3.0 @ 3.0}, _932{1.0 .. 3.0 @ 3.0000000000000009}, _949{1.0 .. 3.0 _at_ 2.9999999999999991}, _966{1.0 .. 3.0 _at_ 1.0}, _983{1.0 .. 3.0 @ 1.0}, _1000{1.0 .. 3.0 @ 1.0}, _1017{1.0 .. 3.0 _at_ 1.0}, _1034{1.0 .. 3.0 @ 3.0}, _1051{1.0 .. 3.0 @ 3.0000000000000009}, _1068{1.0 .. 3.0 _at_ 3.0}, _1085{1.0 .. 3.0 @ 3.0000000000000009}, _1102{1.0 .. 3.0 _at_ 2.0}, _1119{1.0 .. 3.0 @ 2.0}, _1136{1.0 .. 3.0 _at_ 2.0}, _1153{1.0 .. 3.0 @ 3.0000000000000009}, _1170{1.0 .. 3.0 _at_ 2.0}, _1187{1.0 .. 3.0 @ 2.0}, _1204{1.0 .. 3.0 @ 2.0}, _1221{1.0 .. 3.0 _at_ 1.0}, _1238{1.0 .. 3.0 @ 1.0}, _1255{1.0 .. 3.0 _at_ 1.0}, _1272{1.0 .. 3.0 @ 3.0}, _1289{1.0 .. 3.0 @ 3.0}, _1306{1.0 .. 3.0 _at_ 3.0000000000000009}, _1323{1.0 .. 3.0 @ 3.0}, _1340{1.0 .. 3.0 @ 2.0}, _1357{1.0 .. 3.0 _at_ 2.0}, _1374{1.0 .. 3.0 @ 1.0}, _1391{1.0 .. 3.0 _at_ 0.99999999999999989}, _1408{1.0 .. 3.0 @ 3.0}, _1425{1.0 .. 3.0 @ 3.0000000000000009}, _1442{1.0 .. 3.0 _at_ 2.0}, _1459{1.0 .. 3.0 @ 2.0}, _1476{1.0 .. 3.0 _at_ 1.0}, _1493{1.0 .. 3.0 @ 1.0}) Yes (0.05s cpu) Cheers, Marco -- Marco Gavanelli, Ph.D. in Computer Science Dept of Engineering University of Ferrara Tel/Fax +39-0532-97-4833 http://www.ing.unife.it/docenti/MarcoGavanelli/
This archive was generated by hypermail 2.3.0 : Tue Jun 04 2024 - 18:13:21 CEST