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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 01415D176 for ; Sun, 31 Jul 2005 13:46:52 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6VBkpFx023797 for ; Sun, 31 Jul 2005 13:46:51 +0200 Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA18685 for ; Sun, 31 Jul 2005 13:46:51 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j6VBkowI023792 for ; Sun, 31 Jul 2005 13:46:50 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id j6VBkkhl052975 ; Sun, 31 Jul 2005 13:46:46 +0200 (CEST) X-Ids: 166 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 NAA59452 ; Sun, 31 Jul 2005 13:42:57 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id NAA1310898 ; Sun, 31 Jul 2005 13:46:16 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Sun, 31 Jul 2005 13:46:15 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: caml-list@inria.fr Cc: damien.guichard@wanadoo.fr Subject: =?iso-8859-1?Q?Re=3A_Probl=E8me=5Fde=5Fl'achat=5Fpar=5Flots?= Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-1.7.2 (shiva.jussieu.fr [134.157.0.166]); Sun, 31 Jul 2005 13:46:46 +0200 (CEST) X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Miltered: at concorde with ID 42ECBA2B.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42ECBA2A.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 42ECBA26.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; pons:01 pons:01 damien:01 manquantes:01 tombe:01 vois:01 resoudre:01 implementer:01 minimiser:01 lineaire:01 entiers:01 enumeration:01 implicite:01 implementer:01 flottants: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, Damien a =E9crit : > Soit un inventaire recherch=E9 par un achateur, et soit une liste de > lots-inventaires en vente. L'acheteur veut maximiser son > investissement, c'est-=E0-dire avoir le moins de pi=E8ces manquantes > possible et le moins de pi=E8ces supperflues possible. Comment trouver > la (les) combinaison(s) de lots la (les) plus avantageuse(s) ? D=E9sol=E9 de ne r=E9pondre que maintenant, j'ai n'ai pas vu le message initial passer, ce n'est qu'en fouillant dans les archives que je suis tomb=E9 dessus. > Je ne vois pas bien comment il faut aborder le probl=E8me: > * est-ce un "backpack problem" ? > * est-ce un "union-find problem" ? > * est-ce un "genetic-oriented problem" ? > * sinon qu'est-ce que c'est ? Il y a deux probl=E8mes dans votre question : i) le permier est un probl=E8me d'optimisation (quel est le probl=E8me a r=E9soudre ? avec quel type de m=E9thode ?) ii) le second est un probl=E8me d'implantation (comment impl=E9menter en Caml la m=E9thode choisie en i) i. Le probl=E8me d'optimisation Votre probl=E8me est en gros un probl=E8me de "covering". Dans un probl=E8m= e de covering on cherche =E0 minimiser le co=FBt total d'achat sachant qu'on veut satisfaire (couvrir) la demande. Dans votre probl=E8me on ne cherche pas =E0 satisfaire toute la demande, mais une sorte de distance (somme de exc=E9dents et des d=E9ficits) et on divise par le co=FBt. plusieurs m=E9thodes : - programmation lin=E9aire en nombres entiers (PLNE) - =E9num=E9ration implicite, programmation par contraintes (PPC) Si vous n'=EAtes pas familier avec la PLNE, il vaut mieux ne pas choisir cette m=E9thode, surtout si vous voulez impl=E9menter ensuite en Caml (c'est compliqu=E9 et =E7a utilise plein de flottants). ii. Impl=E9mentation en Caml d'une m=E9thode d'=E9num=E9ration implicite Il =E9num=E9rer intelligement toutes les combinaisons possibles. Pour cela, il faut un m=E9canisme de r=E9versibilit=E9 qui s'obtient facilement en Caml par - des appels de fonctions r=E9cursives - des structures de donn=E9es persistantes (librairie standard) - des exceptions J'avais donn=E9 un exemple pour le subset sum (trouver un sous-ensemble d'=E9l=E9ments ayant une somme fixe S) dans comp.lang.functional (Backtracking in Haskell), code =E0 la fin du message. la proc=E9dure de base est simple : - on prend le premier lot - on essaye en l'ajoutant au panier (appel r=E9cursif fonction) - on essaye en l'interdisant dans le panier (appel r=E9cursif fonction) Dans chaque sous-cas on fait des calculs pour =E9liminer le plus de lots dont l'ajout au panier ne sert =E0 rien (par exemple touts les demandes ont =E9t=E9 satifaites) ou ajouter ceux qui sont n=E9cessaires. Quand on aboutit =E0 une impasse, on l=E8ve une exception. Le code risque d'=EAtre un peu plus complexe que pour le subset-sum mais les principes sont les m=EAmes. (* Code pour le subsetsum problem *) exception Fail let rec subsetsum =3D fun remaining candidates -> match remaining with | 0 -> [] | _ -> match candidates with | v :: tail when v <=3D remaining -> (try v :: subsetsum (remaining - v) tail with Fail -> subsetsum remaining tail ) | _ -> raise Fail # subsetsum 40 [3;8;9;13;12;15;17;19];; - : int list =3D [3; 8; 14; 15] Diego Olivier