algorithm question

algorithm question

[Michael Wohlwend]

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

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...

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

thanks
 Michael

Re: [Caml-list] algorithm question

[Diego Olivier Fernandez Pons]

    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

Re: [Caml-list] algorithm question

[Brian Hurt]

On Sun, 26 Feb 2006, Michael Wohlwend wrote:

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

It's solving a problem that doesn't show up in functional programming.

Basically, he's trying to avoid having to duplicate an entire data 
structure in order to preserve a snapshot of the data structure to support 
undoing operations.  With a purely functional (aka applicative aka 
immutable) data structure, modifications are not destructive.  After you 
add a new element into a map, for example, the old map is still valid and 
not changed.  So you can support undoing operations by just keeping 
references to the old copy of the data structure around, and dropping the 
new (modified) data structure and returning to the old one.

Also, he's skating a fine edge.  Operation (2) implicitly assumes that 
L[x] and R[x] have not been modified before the reinsertion happens.  If 
they have been modified, the results depend upon exactly how they've been 
modified, but can easily lead to corrupt data structures.  If you're 
precisely backtracking, it'll be OK, other than that...

Brian

Re: [Caml-list] algorithm question

[Diego Olivier Fernandez Pons]

    Bonjour,

> It's solving a problem that doesn't show up in functional programming.

It is orthogonal : FaCiLe is written in Caml and handles backtrack by
trailing (in other words it keeps only one copy of each object and
restores its state when needed).

On the other hand Gecode implements (partially) node sharing and is
written in C++

        Diego Olivier

Re: [Caml-list] algorithm question

[Michael Wohlwend]

On Sunday 26 February 2006 21:48, Diego Olivier Fernandez Pons wrote:
> The modern approach separates the problem in several orthogonal
> components: 
> ... 

thanks, quite interresting.


 Michael

Re: [Caml-list] algorithm question

[Jean-Christophe Filliatre]

 > > I want to implement the dancing link algorithm as described here:
 > > http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz
 > >
 > > has someone an idea if there is an equally fast way to implent
 > > this more functional? 
 > [...]
 > With a purely functional (aka applicative aka 
 > immutable) data structure, modifications are not destructive.  After you 
 > add a new element into a map, for example, the old map is still valid and 
 > not changed.  So you can support undoing operations by just keeping 
 > references to the old copy of the data structure around, and dropping the 
 > new (modified) data structure and returning to the old one.

For the little story, I heard  this ``dancing links'' talk by Knuth at
Stanford,  which was simply  delightful, and  at the  end I  asked him
about  the   use  of   persistent  data  structures   in  backtracking
algorithms. I had to give a  few explainations about what I meant, and
when  I mentioned  ML, Knuth  simply replied:  ``oh, the  stuff  by Mc
Carthy? I've never been convinced about it...''

Though it was not very surprising, I still was a bit disappointed :-)

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

Re: [Caml-list] algorithm question

[Diego Olivier Fernandez Pons]

    Bonjour,

> when I mentioned ML, Knuth simply replied:  ``oh, the stuff by Mc
> Carthy? I've never been convinced about it...''

I remember having laugh very loud when some one told me that Knuth was
looking for volunteers to port his CISC assembly examples of "The Art of
computer programming" to a more modern language. And when I went to his
homepage to see what modern language he had chosen I discovered it was
... RISC assembly.

        Diego Olivier

Re: [Caml-list] algorithm question

[Brian Hurt]

On Mon, 27 Feb 2006, Jean-Christophe Filliatre wrote:

>
> > > I want to implement the dancing link algorithm as described here:
> > > http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz
> > >
> > > has someone an idea if there is an equally fast way to implent
> > > this more functional?
> > [...]
> > With a purely functional (aka applicative aka
> > immutable) data structure, modifications are not destructive.  After you
> > add a new element into a map, for example, the old map is still valid and
> > not changed.  So you can support undoing operations by just keeping
> > references to the old copy of the data structure around, and dropping the
> > new (modified) data structure and returning to the old one.
>
> For the little story, I heard  this ``dancing links'' talk by Knuth at
> Stanford,  which was simply  delightful, and  at the  end I  asked him
> about  the   use  of   persistent  data  structures   in  backtracking
> algorithms. I had to give a  few explainations about what I meant, and
> when  I mentioned  ML, Knuth  simply replied:  ``oh, the  stuff  by Mc
> Carthy? I've never been convinced about it...''

Which is something I find vaguely humorous.  When he wrote the first 
version of AoCP, he wrote all the examples in assembler, because he wanted 
to use a language that wouldn't go out of date in 50 years.  Of course, 
what happened was the architecture design changed so radically over the 
next couple of decades that he needed to rewrite the books in a new 
assembly.

On the other hand, a core, simplified Lisp was relevent thirty years ago, 
is relevent today, and is the most likely language to still be relevent 
thirty years from now.

Brian