Re: Is Prolog a good language for generating semi-random, constrained solutions?

On 16/03/2014 08:30, Bob Minors wrote:

> I've thought some more about your second set of requirements and I think it
can still be done.

Hi Bob,

Thanks very much for your thoughts on this. Greatly appreciated. I spent a
couple of days last week trying out your approach and experimenting with
various aspects of it. I particularly like the elegance of the any_of/2
predicate for combining randomness of solution order with backtracking (and
the potential for a comprehensive solution set). For some reason it had not
occurred to me to try that before. Also showed me that you can use the
unification mechanism to approximate function pointers or polymorphism by
having arguments that are there specifically to ensure unification can only
occur with the intended clause of a predicate, as with the next_element/3
clauses in your program with their promote/destroy/create variants as the
first parameter. Nice. I feel like I'm always learning with Prolog.

My experiments suggested that in my particular problem domain, backtracking
ends up being too expensive to use on average, and that a largely random
search that locks in successful sub-solutions and backtracks at a larger
granularity does seem to deliver results more reliably. This was
disappointing but perhaps not surprising given the size of the state space
I am using (which is quite a bit larger and more complex than the
scaled-down version I used in my examples to explain the principle). For
the toy problem I presented, your solution is definitely more efficient,
but I suppose that is in part because it is more or less insisting that
certain list elements appear at certain locations: if you haven't had an a
in the first three elements, I insist that element 4 is an a.  If you
haven't had two As in the first four elements, I insist that element 5 is
an a. This definitely meets the requirements, and backtracking is
controlled so tightly at these points that we don't wander off into massive
combinatorial explosion searches of state space. The downside is that we're
pretty much telling Prolog what to put in those slots. Of course, with
backtracking we could in fact find all solutions (as you pointed out), but
we will tend to be skewed towards solutions with A in the 4th and 5th slots
near the start of the set of all solutions that could be delivered through
backtracking, and those first-encountered solutions are the ones which will
get used in practice.

It was a very interesting few days of experimentation, though. When I
allowed backtracking into my search I got a better clustering of best-case
scenarios, but the worst case scenarios were catastrophically bad, and the
average time taken to find the first satisfactory solution was clearly
higher. I suppose the key problem is that PL spends too much time (through
backtracking) tinkering at the edges of many solutions that are miles away
from being useful. It can't fail early enough without an approach like
yours, but if you use that approach it ends up being too prescriptive and
skews the results. I found my mind drifting towards genetic algorithms at
one point.

The process of playing around with different approaches also hammered home
to me the fact that backtracking may not only occur in the places where you
*intended* it to occur. When I was trying to turn off all backtracking in
my "generate, then test" program, I was locked into thinking that
backtracking would only occur in the generation part, but it can of course
occur in the testing as well, and if you are interleaving generation and
testing in a recursion, you can find that you still end up with a huge
number of solutions being created and tested even if there is no
backtracking in the generation part. In other words, if my test can succeed
in one of five ways, that branch of the search is going to end up with five
different "generate" child nodes in the search.


KJ
-------------- next part --------------
HTML attachment scrubbed and removed