Comparison of methods

From: Edmunds family <edmunds_at_pacifier.com>
Date: Sat 11 Mar 2000 04:58:51 PM GMT
Message-ID: <001101bf8b7b$2e23ce40$d2e291c6@edmunds>
In the documentation (Finite Domain library),
there is a solution for the classic Lewis Carroll zebra puzzle
which applies:
    "labeling(List)."
 to generate the solution.

In the lib/propia directory there is an alternate design 
for solving this puzzle, which uses 
  " subset(Constraints,Houses)."
where subset/2 is defined thusly:
  subset([],_).
  subset([H|T],List) :-
     member(H,List),
     subset(T,List).

Which method would be expected to have
better performance and resource use,
labeling/1 or subset/2?

Doug Edmunds
11 March 2000
edmunds@pacifier.com


[
Moderator's note:

The main difference between the two programs is that they use completely
different models of the problem: in the fd program there are 25 variables
ranging over (house) numbers, in the propia program there are 5 variables
ranging over (house descriptors which are) compound terms.

The search component in the fd case uses labeling (which is a pre-defined
enumeration procedure for finite-domain variables), but it could as well
use member(X,[1,2,3,4,5]) on each variable. That difference would be minor.
The more significant aspect of the search procedure is the order in which
alternative possibilities are explored, ie the search heuristic. For
difficult problems you will usually not get away with calling labeling/1,
you'll normally have to program a particular heuristic search order.
The "Turorial on Search Methods" discusses all this in more detail.
]
Received on Mon Mar 13 11:35:32 2000

This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:05 PM GMT GMT