Un problème de partage en Prolog.

Cet article est le premier d'un ensemble de deux articles relatif au partage d'un bidon de 24 L de liquide à l'aide de trois bidons de 5, 11 et 13 L.
La première partie porte sur la recherche de la solution la plus rapide à ce problème, en parcourant en largeur l'arbre des possibilités.
La seconde partie montre comment faire une animation graphique en Prolog à l'aide de XPCE. Elle illustre les transferts de liquide entre les bidons.

Article lu   fois.

Les deux auteurs

Profil Pro

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Une petite histoire

On raconte qu'au Moyen Age, trois voleurs dérobèrent un tonneau de 24 L d'excellent vin.
Malheureusement, ils n'avaient pour se le partager que 3 bidons de 5, 11 et 13 L.
Ils n'arrivèrent jamais à faire un partage équitable et décidèrent de tout boire ensemble d'un seul coup.
Mal leur en pris. Trop ivres pour prêter attention aux bruits, ils n'entendirent pas la maréchaussée arriver et ils finirent dans un cul de basse fosse.
Ah, s'ils avaient connus Prolog, ils auraient pu profiter en toute tranquillité de leur larcin :

Image non disponible

Image non disponible

L'affichage de la solution sous forme d'animation, écrite à l'aide de XPCE, sera traitée dans un second article.
On peut la visionner ici.

II. Le programme de partage.

II-A. Organisation du programme.

Pour réaliser ce partage, on va partir de la situation initiale, un bidon plein de 24 L de vin, 3 bidons vides de 5, 11 et 13 L, et on va construire tous les enchaînements de répartitions possibles de liquide avec un transfert, puis avec deux transferts, puis trois, etc, jusqu'à trouver la situation recherchée (un bidon vide de 5L et trois bidons contenant 8 L de vin). Pour faciliter la compréhension du programme, il paraît plus simple de séparer

  • ce qui est spécifique à la construction des listes de répartitions possibles.
  • ce qui dépend du problème traité, la situation initiale, la situation recherchée et les transferts de liquide entre bidons.
  • l'affichage de la solution, ici sous forme d'une animation écrite en XPCE.


Le programme Prolog comprendra trois fichiers :

  • 'probleme.pl', le module principal qui construit l'arbre des possibilités.
  • 'vin.pl' le module gérant les échanges entre bidons et définissant les états de départ et recherché.
  • 'anime_vin.pl' qui gère l'affichage de la solution.



Cette organisation se traduit en Prolog par l'ajout dans le module principal, en tête de fichier, de prédicats use_module/1, un pour chaque module nécessaire.

Prolog
Sélectionnez
% Entete du fichier probleme.pl
% predicats de chargement des modules necessaires au programme
:- use_module('vin.pl').
:- use_module('anime_vin.pl').

A la première compilation du module principal 'probleme.pl', les modules 'vin.pl' et 'anime_vin.pl' seront chargés et compilés.

Il paraît intéressant de se concentrer d'abord sur les problèmes spécifiques au partage du liquide, d'étudier les situations initiales et finales et les mécanismes de transfert de liquide. Ensuite on étudiera la construction de la solution en créant tous les enchaînements de répartitions possibles de liquide par la construction d'un arbre des possibilités, niveau par niveau.

II-B. 'vin.pl', le module associé au problème du partage du liquide.

Ce module va détailler les prédicats relatifs au partage de 24 litres de liquide en utilisant quatre bidons de 5, 11, 13 et 24 L.
Le module définit trois prédicats, etat_initial/1,etat_final/1,etats_suivants/2 devant être "exportés", c'est-à-dire que le module principal pourra les appeler et seulement ceux-la, les autres prédicats définis dans 'vin.pl' seront "invisibles" de l'extérieur du module. Son entête est

Prolog
Sélectionnez
% Entête du module 'vin.pl'
% Déclarations des prédicats exportés : nom/arité
:- module('vin.pl',[etat_initial/1,etat_final/1,etats_suivants/2]).

II-B-1. Les faits.

Les deux prédicats etat_initial/1 et etat_final/1 sont simples, ils décrivent la situation de départ, à savoir, 3 bidons de 5, 11, 13 L vides et un bidon plein de 24 L, et la situation recherchée à l'arrivée, un bidon vide, celui de 5 L et les autres remplis de 8 L de liquide.
Pour décrire ces situations, on utilise un terme structuré, bidon(Capacite, Volume) ou Capacite est le volume maximal que peut recevoir le bidon et Volume, le volume courant de liquide dans le bidon. On verra plus loin l'intérêt de mettre en premier la capacité du bidon.
On aura pour ces deux prédicats :

Prolog
Sélectionnez
% initialisation de la recherche
etat_initial([bidon(5,0), bidon(11,0), bidon(13,0), bidon(24,24)]).

% etat de réussite
etat_final([bidon(5,0), bidon(11,8), bidon(13,8), bidon(24,8)]).

II-B-2. Les règles.

Le prédicat transfert(+Bidon1, +Bidon2, -Bidon3, -Bidon4) effectue le transfert de liquide de Bidon1 vers Bidon2. Bidon3 et Bidon4 décrivent la situation après le transfert.
Pour pouvoir transférer du liquide de Bidon1 vers Bidon2 il faut que le volume du premier soit plus grand que zéro et que le second bidon ne soit pas plein.
Après le transfert, le premier bidon sera vide et/ou le second bidon sera plein. La quantité de liquide transvasée est le minimum de la quantité de liquide du premier bidon et de ce qui manque dans le second bidon pour qu'il soit plein.

 
Sélectionnez
% Prédicat transfert(+bidon(CX, VX), +bidon(CY, VY), -bidon(CX,VX1),-bidon(CY,VY1))
transfert(bidon(CX, VX), bidon(CY, VY), bidon(CX,VX1),bidon(CY,VY1)) :-
	VX > 0,
	VY < CY,
	DeltaV is CY-VY,
	Verse is min(DeltaV, VX),
	VX1 is VX - Verse,
	VY1 is VY + Verse.

II-B-3. La recherche des états suivants d'un état donné.

Il s'agit ici de trouver tous les transferts possibles de liquide à partir d'une répartition de liquide donnée dans les bidons.
Cette recherche se décompose en deux prédicats, un prédicat qui explique comment on trouve un transfert de liquide et un second prédicat qui collecte tous les transferts possibles à partir du prédicat précédent.

II-B-3-a. La recherche d'un état suivant d'un état donné

La recherche d'un transfert possible est effectuée par le prédicat un_etat_suivant/2. Il sélectionne deux bidons quelconques de la liste, regarde si le transfert est réalisable, dans ce cas il l'effectue et réinsère les bidons dans la liste ordonnée des bidons.

Prolog
Sélectionnez
% prédicat un_etat_suivant(+N, -NN)
% N est un noeud dont on veut calculer un voisin
% NN est un noeud voisin de N 
un_etat_suivant(N, NN) :-
	select(B1, N, N1),
	select(B2, N1, N2),
	transfert(B1, B2,B3,B4),
	sort([B3,B4|N2], NN).

select/3 est détaillé ici.

II-B-3-a-i. Le prédicat sort/2.

Le fait d'avoir mis la capacité des bidons en premier argument du terme structuré bidon permet de maintenir simplement l'ordre des bidons dans la liste. Le prédicat sort/2 est en effet très puissant, il est capable de trier des nombres, des atomes, des chaînes de caractères, mais aussi des termes structurés en respectant "l'ordre naturel" :

Prompt Prolog
Sélectionnez
?- sort([5,2,1,7,6,8], N).
N = [1, 2, 5, 6, 7, 8] 
Yes
?-  sort([bouteille, bidon, verre, bouteilles], N).
N = [bidon, bouteille, bouteilles, verre] 
Yes
?- sort([bidon(5,0), bouteille(3), bidon(7,2), bidon(5,3)], N).
N = [bidon(5, 0), bidon(5, 3), bidon(7, 2), bouteille(3)] 
Yes

sort/2 est détaillé ici.

II-B-3-b. La recherche de tous les états suivants d'un état donné

La collecte de tous les transferts possibles est effectuée par le prédicat etats_suivants/2. Pour celà, on utilise le prédicat setof/3 détaillé ici, qui permet de regrouper tous les buts possibles d'un prédicat.

Prolog
Sélectionnez
% Prédicat etat_suivant(+N, -LN)
% N est le noeud dont on veut connaître "les voisins"
% LN est la liste des états voisins au noeud N
etats_suivants(N, LN) :-
      setof(NN, un_etat_suivant(N, NN), LN).

II-C. 'probleme.pl' : le module de parcours d'un arbre en largeur.

On parle ici de parcours d'un arbre en largeur, ou aussi de construction de l'arbre des possibilités.
Le principe consiste à partir de la racine de l'arbre, à savoir un état initial, dans notre problème, la répartition initiale de liquide dans les 4 bidons.
A partir de cet état initial, on va chercher toutes les configurations possibles pouvant être obtenues en une recherche, puis en deux recherches etc, jusqu'à obtenir l'état recherché, l'état final, dans notre cas le bidon de 5L vide et les trois autres contenant 8 L de vin.
On construit ainsi des listes d'états, de configurations, appelées chemins.
A chaque tour de boucle on ajoute à tous les chemins déjà existants, les états atteints à partir du dernier état rencontré du chemin en cours, à condition qu'ils n'aient pas déjà été visités par ce chemin. Le terme visité signifie que l'état ne figure pas déjà dans le chemin.
Pour le graphe ci-dessous

Image non disponible

Le programme produit

  • Initialisation : [[A]]
  • Premier tour : [[D,A], [C,A], [B,A]]
  • Deuxième tour : [[I, D, A],[H, C,A], [G,C,A], [F, C, A], [F, B, A], [E,B,A]].

Les parcours sont construits à l'envers. Pour une étude plus approfondie des parcours de graphes, on pourra consulter ce lien.

II-C-1. La boucle de construction de l'arbre des possibilités.

Le lancement du programme se fait par le prédicat probleme/0.

Prolog
Sélectionnez
probleme :-
	% Le prédicat etat_initial/1 est fourni par le module 'vin.pl'
	etat_initial(Init),
	etape_suivante([[Init]], S),
	% le prédicat affiche_resultat/1 est fourni par le module 'anime_vin.pl'
	affiche_resultat(S).

Le prédicat etat_initial/1 dépend du problème traité et est fourni par le module associé au problème.
Le prédicat affiche_resultat/1 dépend de la méthode de visualisation choisie, c'est lui qui affichera l'animation.
Le prédicat etape_suivante/2 construit la liste des chemins.

Prolog
Sélectionnez
% Prédicat etape_suivante(+X, -S)
% X est la liste des chemins déjà parcourus
% Y est a liste des nouveaux chemins après une recherche d'un niveau supplémentaire de profondeur
etape_suivante(X, S) :-
	calcule_etape_suivante(X, Y) ,
	(   (   recherche_terminee(Y, R), reverse(R, S))
	    ;
	       etape_suivante(Y, S)
	).

Le prédicat recherche_terminee/2 teste si on a atteint l'état final. Y contient la liste des chemins parcourus, R contient le bon chemin si le prédicat réussit. Comme il a été construit, à l'envers, il faut évidemment le remettre dans le bon ordre.
Le prédicat reverse/2 est détaillé ici.

II-C-2. Le test de terminaison des parcours.

Voyons le prédicat recherche_terminee/2.
Il parcourt la liste des chemins obtenus pour chercher le noeud terminal, qui est le premier du chemin considéré.

II-C-2-a. Recherche_terminee version 1.

Une première approche serait celle-ci : le parcours de la liste, chemin par chemin, en testant le premier élément de la liste.

 
Sélectionnez
% prédicat recherche_terminee(+Y, -R)
% Y est a liste de chemins et on veut savoir si l'un deux est "terminal"
% R est un chemin terminal. R n'est renseigné que si le prédicat réussit.

% Si la liste est vide, on n'a rien trouvé, échec.
recherche_terminee([], _) :- fail.

% Si le premier noeud est le noeud terminal, on a gagné
recherche_terminee([H |_ ], H) :-
	etat_final(Final),
	nth0(0, H, Final), !.

% Sinon, on passe au noeud suivant.
recherche_terminee([_|T], X) :-
      recherche_terminee(T, X).

Le prédicat nth0/3 est défini ici.
Le prédicat etat_final/1 dépend du problème traité et est décrit dans le fichier 'vin.pl'.

II-C-2-b. Recherche_terminee version 2.

Une approche, plus "Prolog", consiste à définir le prédicat noeud_terminal_atteint/1 qui réussit si le premier élément de la liste passée en argument est le noeud recherché. Ensuite, la recherche des chemins terminaux se fait en utilisant le prédicat sublist/3, détaillé ici, qui unifie son dernier argument avec la liste des éléments de la liste passée en second argument qui réussissent au prédicat passé en premier argument ! Si sublist/3 réussit, on ne garde que le premier chemin de la liste obtenue.

Prolog
Sélectionnez
recherche_terminee(Y,R) :-
	sublist(noeud_terminal_atteint, Y, [R |_]).

% Prédicat noeud_terminal_atteint(+Chemin)	
% Chemin est une liste d'etats et on regarde le premier pour savoir 
% s'il est "terminal"
noeud_terminal_atteint([Final|_]):-
	etat_final(Final).

II-C-3. Le calcul d'un niveau supplémentaire de parcours.

Voyons maintenant le prédicat calcule_etape_suivante/2.
On travaille chemin déjà créé par chemin déjà créé, la liste est construite en sortie de récursivité.

Prolog
Sélectionnez
% prédicat calcule_etape_suivante(+X, -Y)
% X est la liste des chemins déjà parcoururs
% Y est la nouvelle liste de chemins obtenue à partir de X en 
% ajoutant un niveau supplémentaire

% Lorsque la liste est vide, on unifie le resultat avec la liste vide
% (construction en retour de récursivité)
calcule_etape_suivante([], []).

% On calcule ici la liste des nouveaux chemins issus du premier chemin de la liste
calcule_etape_suivante([H|T], X) :-
	% etape 1 : on calcule la liste des nouveaux chemins pour la liste restante
	% (on a oté le premier chemin)
	calcule_etape_suivante(T, X1),
	% On calcule la liste des nouveaux chemins issus de H
	etape_suivante_un_chemin(H, X2),
	% On concatène la liste des nouveaux chemins issus de X avec ceux déjà obtenus
	% par les appels précédents à calcule_etape_suivante
	append(X2,X1,X).

Le prédicat append/3 est détaillé ici.
Le prédicat etape_suivante_un_chemin/2, calcule tous les noeuds pouvant être atteints à partir du premier (puisque le chemin est à l'envers) noeud du chemin fourni, puis à les ajouter un par un en tête de ce chemin s'ils n'ont pas été déjà visités.

Prolog
Sélectionnez
% Prédicat etape_suivante_un_chemin(+T, -X)
% T est un chemin déjà parcouru, on ne s'intéresse qu'à son premier noeud
% X est la liste de tous les chemins obtenus à partir de T en ajoutant à chaque
% fois un noeud adjacent au premier noeud de T.
etape_suivante_un_chemin([N | L] , X) :-
	etats_suivants(N, LN),
	ajoute(LN,[N| L], X).

Le prédicat etats_suivants/2 dépend du problème et est décrit dans le module 'vin.pl'. Voyons le prédicat ajoute/3

Prolog
Sélectionnez
% Prédicat ajoute(+LN, +C, -X)
% LN est la liste des noeuds ajacents au premier noeud de C
% C est un chemin 
% X est la liste des chemins obtenus en ajoutant un élément de LN en tête de C
% on ajoute les nouveaux noeuds au chemin
% dont ils sont issus, à condition qu'ils n'y figurent pas déjà.
ajoute([], _, []).

ajoute([H|T], L, [[H | L] | X]) :-
	\+memberchk(H, L), !,
	ajoute(T, L, X).

ajoute([_|T], L, X) :-
	ajoute(T, L, X).

Le prédicat memberchk/2 est détaillé ici.
Il permet le test d'appartenance du noeud au chemin considéré, on ne continue que si memberchk/2 échoue, le \+ transformant cet échec en réussite, nécessaire à l'insertion du noeud en tête de chemin. Le ! permet de supprimer les points de choix. Voir l'article sur la programmation dirigée de pcaboche

II-D. Sources Prolog.

Les sources Prolog, avec un simple affichage de la liste des transferts au lieu de l'animation, sont téléchargeables ici.

III. L'animation

L'animation, écrite à l'aide de XPCE, sera détaillée dans un prochain article.
Elle est visible ici.

IV. Remerciements

Je tiens à remercier Eusebius, pcaboche pour leurs conseils et remarques avisés et millie et lokapour leurs relectures attentives.

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

Ce document est issu de http://www.developpez.com et reste la propriété exclusive de son auteur. La copie, modification et/ou distribution par quelque moyen que ce soit est soumise à l'obtention préalable de l'autorisation de l'auteur.