algorithm question

Michael Wohlwend
 Diego Olivier Fernandez Pons
 Brian Hurt
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20060226 (20:48) 
From:  Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...> 
Subject:  Re: [Camllist] algorithm question 
Bonjour, > I want to implement the dancing link algorithm as described here: > http://wwwcsfaculty.stanford.edu/~knuth/papers/dancingcolor.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 NPproblem 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