- Mail actions: [ respond to this message ] [ mail a new topic ]
- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Panagiotis Stamatopoulos <takis_at_...90...>

Date: Tue, 21 Feb 2023 14:01:54 +0200

Date: Tue, 21 Feb 2023 14:01:54 +0200

Dear Marco, I tried both approaches you suggested. The alldifferent_matrix one didn't work well. It was very inefficient. Maybe because the grid representation is a list of lists, which I transformed to a matrix, in order to post the alldifferent constraint, while the rest of the program deals with lists? I don't know. But the second approach, with the lists of the maxima, the ordered constraint and the gfd nvalues one worked incredibly. It gave a speedup of almost an order of magnitude (x10) compared to my previous approach, based on the query of my first message. Thank you very much! Best Regards, Panagiotis On 20-Feb-23 11:40 PM, Marco Gavanelli wrote: > Dear Panagiotis, > > of course Propia is for rapid prototyping, if you want a fast > implementation of the constraint you can implement it with suspensions. > > However, after seeing the whole problem, I think that in order to have a > better speedup you should try and use global constraints as much as > possible. > > A simple one is alldifferent_matrix. > > Another idea could be the following: > for each row [X1,X2,...] you have a further list of variables > [M1,M2,...] where (foreach i), Mi = max([X1,...,Xi]). > > Now, the list [M1,M2,...] is sorted, so you can impose the ordered > constraint on it. > Also, the number of distinct elements in [M1,M2,...] is exactly the > number of skyscrapers you see, so you might use the nvalues constraint > (available in gfd). > > I haven't tried these, though. > > Best, > Marco > > > On 20/02/2023 18:28, Panagiotis Stamatopoulos wrote: >> Thank you very much, Marco. I tried your suggestion and it works >> as you describe, as far as the constraint propagation is concerned. >> >> However, my original problem was to implement an ic-based (or >> gfd-based) solution for the puzzle here: >> https://www.puzzle-skyscrapers.com/ >> >> I got a solution, quite easily, which works well for small and medium >> size instances, but is very inefficient for larger ones (N > 7). When >> I injected your propia-based suggestion, the program was even more >> inefficient. My assumption is - might be wrong, though - that propia >> introduces an overhead which does not pay off, despite the fact that >> we have more propagation. I 'll try some more alternatives that I >> have in mind and see if things get better. As far as the heuristics >> in the search is concerned, it seems that most_constrained/indomain__max >> is the best combination for variable/value selection. >> >> Anyway, thank you very much again for your time. If there is any >> suggestion on a way to express more efficiently, compared to the >> approach that can be inferred from the query in my previouw message, >> the constraints of the problem above that refer to the numbers of >> visible skyscrapers from the side points, I would be glad to hear it. >> >> Best Regards, >> Panagiotis >> >> On 20-Feb-23 1:54 PM, Marco Gavanelli wrote: >>> Hi, >>> >>> On 20/02/2023 11:27, Panagiotis Stamatopoulos wrote: >>>> Hello Everybody, >>>> >>>> After having loaded libraries ic and ic_global, we give the query: >>>> >>>> ?- N = 4, Count = 0, length(L, N), L #:: 1..N, >>>> ic_global:alldifferent(L), L = [X1,X2,X3,X4], (X2 #> X1) + (X3 #> >>>> max([X1,X2])) + (X4 #> max([X1,X2,X3])) #= Count. >>>> >>>> N = 4 >>>> Count = 0 >>>> L = [X1{1 .. 4}, X2{1 .. 4}, X3{1 .. 4}, X4{1 .. 4}] >>>> X1 = X1{1 .. 4} >>>> X2 = X2{1 .. 4} >>>> X3 = X3{1 .. 4} >>>> X4 = X4{1 .. 4} >>>> There are 6 delayed goals. >>>> Yes (0.00s cpu) >>>> >>>> As we may see, from the query we can infer that X1 = 4. Is there >>>> any alternative way to pose the query in order to get this result? >>>> Note that Count might be anything between 0 and 3 (if we assign it >>>> the value 3, we get the answer X1 = 1, X2 = 2, X3 = 3, X4 = 4, >>>> as we might expect). But what if Count is less than 3? How could >>>> we get the most propagation possible? >>> >>> With Count=0 the solver infers that >>> (X2 #> X1) #= 0 >>> i.e. >>> X2 #=< X1 >>> >>> I guess you would like to combine that information with the >>> alldifferent constraint, and obtain the stronger constraint >>> >>> X2 #< X1. >>> >>> One way to achieve this propagation could be to use, instead of the >>> #< /3 constraint, a constraint that excludes the possibility of >>> having X2 = X1 (i.e., either X1 < X2 or X2 > X1). For example: >>> >>> :- lib(propia). >>> mygt(X,Y,B):- mygt1(X,Y,B) infers most. >>> mygt1(A,B,1):- A #> B. >>> mygt1(A,B,0):- A #< B. >>> >>> Now this constraint can be used instead of #< /3 : >>> >>> ?- N=4, Count=0, L = [X1,X2,X3,X4], length(L, N), L #:: 1..N, >>> ic_global:alldifferent(L), mygt(X2,X1,B1), M12 #= max([X1,X2]), >>> mygt(X3,M12,B2), M123 #= max([X1,X2,X3]), mygt(X4,M123,B3), >>> sumlist([B1,B2,B3]) #= Count. >>> >>> N = 4 >>> Count = 0 >>> L = [4, X2{1 .. 3}, X3{1 .. 3}, X4{1 .. 3}] >>> X1 = 4 >>> X2 = X2{1 .. 3} >>> X3 = X3{1 .. 3} >>> X4 = X4{1 .. 3} >>> B1 = 0 >>> M12 = 4 >>> B2 = 0 >>> M123 = 4 >>> B3 = 0 >>> >>> >>> Delayed goals: >>> mygt1(X2{1 .. 3}, 4, 0) infers most >>> mygt1(X3{1 .. 3}, 4, 0) infers most >>> mygt1(X4{1 .. 3}, 4, 0) infers most >>> alldifferent([X2{1 .. 3}, X3{1 .. 3}, X4{1 .. 3}], 1) >>> Yes (0.00s cpu) >>> >>> Cheers, >>> Marco >>> >> >> >> _______________________________________________ >> ECLiPSe-CLP-Users mailing list >> ECLiPSe-CLP-Users_at_lists.sourceforge.net >> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users >Received on Tue Feb 21 2023 - 12:02:16 CET

*
This archive was generated by hypermail 2.3.0
: Wed Sep 25 2024 - 15:13:21 CEST
*