I. Une petite histoire▲
On raconte qu'au Moyen Âge, trois voleurs dérobèrent un tonneau de 24 L d'excellent vin.
Malheureusement, ils n'avaient pour se le partager que trois 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 prit. 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 connu Prolog, ils auraient pu profiter en toute tranquillité de leur larcin :
L'affichage de la solution sous forme d'animation, écrite à l'aide de XPCE, sera traité 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.
% Entete du fichier probleme.pl
% predicats de chargement des modules necessaires au programme
:- use_module('vin.pl').
:- use_module('anime_vin.pl').À 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-là, les autres prédicats définis dans 'vin.pl' seront « invisibles » de l'extérieur du module. Son entête est
% 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 :
% 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.
% 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.
% 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 » :
?- 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)]
Yessort/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 cela, on utilise le prédicat setof/3 détaillé ici, qui permet de regrouper tous les buts possibles d'un prédicat.
% 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.
À 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.
À 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
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.
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.
% 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 nœud 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.
% 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 nœud_terminal_atteint/1 qui réussit si le premier élément de la liste passée en argument est le nœud 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.
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é.
% prédicat calcule_etape_suivante(+X, -Y)
% X est la liste des chemins déjà parcourus
% 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 ôté 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 nœuds pouvant être atteints à partir du premier (puisque le chemin est à l'envers) nœud 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.
% 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
% 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 nœud au chemin considéré, on ne continue que si memberchk/2 échoue, le \+ transformant cet échec en réussite, nécessaire à l'insertion du nœud 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.