[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
question on fd_minimize and if fd var bindings are created on disjunctio
From: |
Adam Russell |
Subject: |
question on fd_minimize and if fd var bindings are created on disjunctions |
Date: |
Fri, 17 Dec 2021 19:22:57 -0500 |
User-agent: |
Mozilla/5.0 (Windows NT 10.0; WOW64; rv:68.0) Gecko/20100101 Firefox/68.0 SeaMonkey/2.53.10.1 |
In one of the 2021 Advent of Code puzzles the requirement is to find the
lowest cost traversal of a maze. The actual problem statement is at
https://adventofcode.com/2021/day/15
Rather than just, say, implement A* I thought I'd try something a little
different. My thought was to represent the indices of the grid as fd
vars and the movements within the grid as constraints. The code to do
this is http://paste.debian.net/hidden/70acfece/ which is to act on the
input http://paste.debian.net/hidden/ce112fda/
This works for this 10x10 test input. I get the answer 40 which is the
minimal cost path. Trying it out on a larger input and gprolog crashes.
Since I have access to a system with considerable memory I figured I
could just increase CSTRSZ to some large limit, but gprolog will not
accept too large a value for CSTRSZ without just crashing at the start.
Is there an internal hard coded limit to how high this may be set?
I figured since this approach seems to work OK, besides the limit on
CSTRSZ I would just re-implement the constraints using SWI-Prolog's
clpfd since SWI seems happier about allowing the user to set arbitrarily
high memory allocation sizes. I did that but then found SWI would not
yield a correct answer!
I posted a question on this to the SWI forums and one possible
explanation given there is that for this part of the code which
restricts the possible movements through the maze
(M #= A rem LS, M #\= 1, B #= A - 1); %LEFT
(M #= A rem LS, M #> 0, B #= A + 1); %RIGHT
(A #> LS, B #= A - LS); %UP
(A #=< MaxN, B #= A + LS) %DOWN
that gprolog is (correctly! in my opinion) creating an fd var binding
for each part of the disjunction but SWI's clpfd is not.
I suppose that would explain why gprolog yields an optimally minimal
answer but blasts through the CSTRSZ limitations, and SWI does not yield
a minimal answer at all.
That all seems plausible, but is that in fact true? Or is there
something else at work here?
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- question on fd_minimize and if fd var bindings are created on disjunctions,
Adam Russell <=