Hi all, well, now there is no need to improve further, however another lesson in CP is try to use the available global constraints. ECLiPSe has the interesting ordered_sum constraint, so one can join the symmetry breaking with the sum constraint. I checked this model with the old labeling (as with the smart search suggested by Thorsten I could not even measure the computing time), and it went from 9.22 seconds to 2.78 on my machine. Cheers, Marco On 13/09/11 08:42, Thorsten Winterer wrote: > Hi, > > just for completeness I would use #=</2 instead of #</2 for the symmetry > breaking (although #</2 of course gives the same solution). > > But for search/6, I think there are better choices than 'largest' and > 'indomain_split' available. > > With 'largest' and 'indomain_split', I need 0.52 sec to find the > solution on my machine instead of 67.81 sec. > > With 'first_fail' and 'indomain_reverse_split', I need only 0.04 sec. > > > Cheers, > Thorsten > > > Am 13.09.2011 06:56, schrieb Hakan Kjellerstrand: >> Hi, >> >> another improvement is adding explicit symmetry breaking: >> >> A #< B, >> B #< C, >> C #< D, >> >> as well as using another labeling >> >> search(Prices ,0,largest,indomain_split,complete,[]), >> >> This solves the problem in 0.22 seconds instead of the original >> about 45 seconds on my machine. >> >> In larger problems I would probably also have used the >> explicit domain declaration >> >> Prices :: [1..711] >> >> though in this case it doesn't improve times or the number of >> backtracks. >> >> Here's the full model: >> >> %%%%%%%% >> :- lib(ic). >> >> solve :- >> Sum = 711, >> Product = 711, >> Prices = [A, B, C, D], >> % A #> 0, B #> 0, C #> 0, D #> 0, >> Prices :: [1..711], >> A + B + C + D #= Sum, >> A * B * C * D #= Product * 1000000, >> >> A #< B, >> B #< C, >> C #< D, >> search(Prices ,0,largest,indomain_split,complete,[backtrack(Backtracks)]), >> >> % labeling(Prices), >> >> writeln(Prices), >> writeln(backtracks:Backtracks). >> >> %%%%%%%%% >> >> >> Best, >> >> Hakan >> >> >> On Tue, Sep 13, 2011 at 02:00:28AM +0200, Joachim Schimpf wrote: >>> Sergey Dymchenko wrote: >>>> Hi! >>>> >>>> I'm trying to solve this puzzle: http://programmingpraxis.com/2009/11/27/7-11/ >>>> >>>> Here is my very straightforward code: >>>> >>>> :- lib(ic). >>>> solve :- >>>> Sum = 711, >>>> Product = 711, >>>> Prices = [A, B, C, D], >>>> A #> 0, B #> 0, C #> 0, D #> 0, >>>> A + B + C + D #= Sum, >>>> A * B * C * D #= Product * 1000000, >>>> labeling(Prices), >>>> writeln(Prices). >>>> >>>> It works, but it's too slow. >>>> Is there any way to speed it up without being too clever and >>>> explicitly say to ECLiPSe that the prices of the four items must come >>>> from the list of divisors of 711? >>> It is much faster (1.8 instead of 63 seconds on my machine) if you use >>> domain splitting during search, i.e. replace labeling(Prices) with >>> >>> search(Prices, 0, input_order, indomain_split, complete, []) >>> >>> This is probably always a good idea with relatively large domains >>> and convex constraints. >>> >>> Other improvements? >>> >>> >>> Cheers, >>> Joachim >>> >>> ------------------------------------------------------------------------------ >>> BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA >>> Learn about the latest advances in developing for the >>> BlackBerry® mobile platform with sessions, labs& more. >>> See new tools and technologies. Register for BlackBerry® DevCon today! >>> http://p.sf.net/sfu/rim-devcon-copy1 >>> _______________________________________________ >>> ECLiPSe-CLP-Users mailing list >>> ECLiPSe-CLP-Users_at_lists.sourceforge.net >>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users > > > ------------------------------------------------------------------------------ > BlackBerry® DevCon Americas, Oct. 18-20, San Francisco, CA > Learn about the latest advances in developing for the > BlackBerry® mobile platform with sessions, labs& more. > See new tools and technologies. Register for BlackBerry® DevCon today! > http://p.sf.net/sfu/rim-devcon-copy1 > _______________________________________________ > ECLiPSe-CLP-Users mailing list > ECLiPSe-CLP-Users_at_lists.sourceforge.net > https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users > > -- 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/Received on Tue Sep 13 2011 - 09:45:28 CEST
This archive was generated by hypermail 2.3.0 : Tue Apr 16 2024 - 09:13:20 CEST