- 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: Mon, 20 Feb 2023 19:28:15 +0200

Date: Mon, 20 Feb 2023 19:28:15 +0200

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 >Received on Mon Feb 20 2023 - 18:00:22 CET

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