Voilà des semaines qu'on en parle et qu'il préoccuppe en sourdine un petit coin de notre matière grise : le KHP.
Le Kata Harry Potter :
Je vends des livres; mes livres coûtent 8 euros pièces, mais je fais des réductions sur la série Harry Potter : pour 2 volumes (différents) la réduction est de 5%. Pour 3 volumes (idem) elle est de 10 %, pour 4 elle est de 20%, pour 5 de 25%. Afin d'éviter les maux de tête lors du paiement à la caisse, il me faudrait un programme qui, étant donnée une liste de volumes identifiés par leur numéro, en calcule le prix en appliquant la meilleure réduction possible. Quelques exemples :
- un volume quelconque : 8,00
- deux volumes identiques : 16,00
- les volumes 1,2 : 15,20
- les volumes 1,1,2 : 23,20
- les volumes 1,2,3,4,5 : 30,00
- les volumes 1,1,2,2,3,3,4,5 : 51,20 (et non 51,60)
Face à ce problème, il y a eu autant de réactions différentes que de participants au Dojo. En caricaturant légèrement (pardon d'avance à ceux qui se reconnaîtront :-) je peux relater trois d'entre elles:
Zeppo : Ah, ok. C'est un problème de partitionnement de listes. Prendre toutes les partitions possibles de la liste de livres; calculer le prix total de chaque partition; renvoyer la partition la moins chère. Bien sûr, cette solution est inutilisable au delà de 8 livres, mais bon voilà..
Harpo : Il doit y avoir une façon de créer les lots de livres en tenant compte simplement des caractéristiques de la table des réductions. Qu'est-ce qu'elle nous dit cette table ? Si on peut étudier les tarifs et trouver une loi de progression, alors on n'a pas besoin de créer toutes ces partitions.
Zeppo : Il faudrait pouvoir limiter le nombre de partitions créées; des tas de combinaisons sont en fait sans intérêt pour le problème donné.
Harpo : Même avec des facteurs limitants, on reste dans un problème bigrement trop complexe pour des temps de réponse acceptables.
Zeppo : Etudier la liste des réductions, OK. Mais cette liste peut être amenée à changer, et là le programme ne marcherait plus..
Groucho : Les gars, si on faisait le boulot qui nous est demandé ? Faire deux lots de 4 plutôt qu'un lot de 5 et un lot de 3: j'ai l'intuition que c'est la seule et unique règle d'optimisation à prendre en compte. Hop : on n'a qu'à remplir des paniers, pas deux fois le même livre dans le même panier. Ensuite on optimise : s'il y a des paniers de 5 et de 3, j'en fais des paniers de 4. Et l'affaire est dans le sac.
Zeppo, Harpo : ...
C'est un problème de génie logiciel. Est-ce un problème d'Ingénieur ou de Mathématicien ? Le Mathématicien réfléchit au temps qu'il faudrait pour trouver la réponse dans un cadre général : "soit r,s,t,u les réductions associées à l'achat de 2,3,4 ou 5 livres... etc.". L'Ingénieur entend le Mathématicien, mais il réfléchit aussi au temps qu'il reste pour écrire un programme utilisable par le client pour son problème donné : précisément 5, 10, 20 puis 25%. Le Mathématicien trouve une solution universelle et éternelle, ou pas de solution. L'Ingénieur trouve un répit jusqu'à demain, car tout programme utile est amené à changer.
Posted by Christophe at April 19, 2005 06:56 PM