From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 6ADB4BBBB for ; Sun, 26 Feb 2006 21:48:03 +0100 (CET) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k1QKm24o028153 for ; Sun, 26 Feb 2006 21:48:02 +0100 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.13.5/jtpda-5.4) with ESMTP id k1QKm1aT061155 ; Sun, 26 Feb 2006 21:48:01 +0100 (CET) X-Ids: 168 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id VAA318186 ; Sun, 26 Feb 2006 21:43:23 +0100 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id VAA1208536 ; Sun, 26 Feb 2006 21:48:08 +0100 Date: Sun, 26 Feb 2006 21:48:08 +0100 (NFT) From: Diego Olivier Fernandez Pons To: Michael Wohlwend Cc: OCaml Mailing List Subject: Re: [Caml-list] algorithm question In-Reply-To: <200602262121.52645.micha-1@fantasymail.de> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.7.2 (shiva.jussieu.fr [134.157.0.168]); Sun, 26 Feb 2006 21:48:02 +0100 (CET) X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Miltered: at nez-perce with ID 44021402.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 44021401.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 caml-list:01 knuth:01 knuth:01 backtracking:01 node:01 orthogonal:01 node:01 nodes:01 enumeration:01 dancing:98 dancing:98 integer:01 algorithm:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 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