Re: [Caml-list] algorithm question

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    Bonjour,

> I want to implement the dancing link algorithm as described here:
> http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz

The "dancing link algorithm" explained by Knuth is not an algorithm. It is
a mix between an algorithm (or an algorithmic idea) and a data structure.
The algorithmic idea is the backtracking tree shaped exploration of the
set of solutions of a combinatorial problem. The data structure is the
reversible list of assignments that are still possible for a variable at a
given node of the search tree.

> has someone an idea if there is an equally fast way to implent this more
> functional ? The method in the paper seems pretty good, just adjusting a
> the linksfields of the structure...

The modern approach separates the problem in several orthogonal
components:

- reduction algorithms : how not to explore all the possible solutions of
an NP-problem using some mathematical/combinatorial properties like "the
solution cannot contain both x = 3 and y = 5"

- tree search implementation : can be done by node sharing (that is there
is a copy of every leaf of the tree) or node replaying (There is a virtual
tree and a single physical node. Every time you want to change of node in
the virtual tree you must resynchronize it with some data you kept about
the path that lead you there). The first one will lead to "reversible data
structure"  techniques while the second one to "persistent data structure"
techniques.

- the visiting heuristic : how do I jump from one node to another in the
tree, when do I open or close nodes, etc.

The modern name is "implicit enumeration algorithms" which split
themselves into multiple branches according to the way the branches in the
search tree are pruned : (integer) linear programming, constraint
programming, SAT, etc.

By the way, they have also been combined with ascending algorithms (not
tree like explorations of the search space) like dynamic programming,
resolution, etc.

> you can solve puzzle problems with this algorithm and shorter (execution
> time) is really better here :-)

The method which is the closest to the one described in Knuth's paper is
named Constraint Programming (CP). There are several libraries for that in
many languages including Caml (it's name is FaCiLe).

        Diego Olivier