Démo Prolog: Recherche appartement dans un catalogue

Dans cette démonstration, à partir d'un catalogue d'appartement qui indique le prix, le nombre de pièces et l'orientation, on effectue une recherche pour trouver l'objet optimal pour les critères donnés.

Recherche appartement en Prolog

Afficher la liste des appartements

D'abord on fait entrer le catalogue en mémoire, et on ajoute un programme qui permet d'afficher la liste des produits qu'il contient.

app(appart1, sud, 3, 60).
app(appart2, nord, 5, 80).
app(appart3, sud, 4, 70).
app(appart4, sud, 6, 90).
app(appart5, sud, 4, 100).
app(appart6, ouest, 8, 50).
catalogue :-
   write('Catalogue...\n'),
   forall(app(X,O,T,P), format("Code ~a orientation ~a T~D prix ~D.000 ~n", [X, O, T, P])).

La fonction forall de prolog est une fonction d'unification. Le premier terme est la condition, cette condition est confrontée avec chaque prédicat de type "app" en mémoire. Le second terme est l'action, elle est exécutée pour chaque occurence qui remplit la condiiton.
Comme les valeurs du prédicat ne sont pas attribuées, la condition se vérifie pour tous les prédicats de la base. Si on avait donné "sud" comme seconde valeur, la condition n'aurait été vérifiée que pour les appartements avec l'orientation "sud".

On utilise donc cette condition sans valeur prédéfinie pour afficher la liste de tous les appartements, quelle que soit leur orientation.

Choisir des appartements répondant à des critères

On veut sélectionner les appartements avec une orientation donnée et un prix maximum donné.
S'il ne s'agissait que de trouver les appartement avec une orientation et un prix donné, ce serait simple, on utiliserait la règle catalogue précédente avec deux paramètres:

catalogue(O,P) :-
write('Catalogue...\n'),
forall(app(X,O,T,P), format("Code ~a T~D ~n", [X, T])).

Et on ferait une requète telle que par exemple celle-ci:

catalogue(sud, 70).

Mais on doit comparer les prix avec une valeur plafond, et le code sera donc un peu plus compliqué.

La fonction findall de prolog permet de créer une liste d'éléments qui répondent à une condition.

findall(element, condition impliquant l'élément, liste) 

La condition dans notre cas est d'avoir une orientation égale à la valeur O donnée, et un prix P inférieur au prix PMax donné.

candidats(O, PMax) :-
findall(X, (app(X,O,_,P), P =< PMax), L),
write('\nCandidats au catalogue:\n'),
dispList(L).

Nous regroupons entre parenthèse app(X,O,_,P) et la comparaison de prix P =< PMax, pour former une condition en un seul paramètre.

Ce code retourne la liste L de tous les éléments X qui satisfont la condition. Voyons comment afficher cette liste.

Afficher une liste en Prolog

Un argument de forme [A|B] désigne le premier élément d'une liste suivi de l'ensemble des autres éléments. On appelle une règle avec une liste L en paramètre et prolog dissocie cette liste en deux parties.

C'est pratique pour énumérer le contenu d'une liste par une récursion. Il suffit de remplacer le paramètre [A|B] par B quand la règle s'invoque elle-même.

dispList([A|B]) :-
(app(X,_,T,P), X = A),format('~w T~D ~D.000 euros ~n', [X, T, P]),
dispList(B).

La règle dispList de façon récursive s'invoque elle même en remplaçant chaque fois la liste par la seconde partie B qui ne comprend pas le premier élément. Le premier élément A lui est traité dans la règle.

Notre règle unifie l'élément A avec le prédicat app dont cet élément A est une des valeurs. La fonction format affiche les valeurs du prédicat qui est trouvé.

Trouver l'appartement le plus grand qui répond aux critères

On cherche l'appartement X avec un nombre de pièces T. On veut que le nombre de pièces soit le plus grand possible. D'autres conditions sont ajoutées.

L'opérateur non prouvable \+ retourne vrai si son argument n'est pas prouvable, et faux s'il est prouvé.

\+ (terme)

L'intérêt ici est d'obtenir l'unification de valeurs successives en assignant la valeur maximale à T.

Les variables X et T ne sont pas assignées quand on invoque la règle, contrairement à ORT et PMax. Elle sont assignées chaque fois que dans un prédicat app une valeur T2 est supérieure à T et que les deux autres critères sont respectés.

plusGrand(X, ORT, PMax) :-
   app(X, _, T, _), 
   \+ (app(_, O, T2, P), (T2 > T, O = ORT, P =< PMax)).

La formule non prouvable cherche un prédicat app ou la valeur O est égale à une valeur ORT donnée, la valeur P est inférieure ou égale à une valeur PMax donnée, et la valeur T2 est supérieure à la valeur T de l'appartement déjà trouvé.
Tant qu'il existe une valeur T2 supérieure à T, la formule est prouvée, il y a échec et l'unification continue en quête de résolution.
Dès que T2 atteint la valeur maximale, il y a succès, la résolution est obtenue et on revient au point d'invocation de la règle avec les variables X et T assignées. L'appartement correspondant aux critères est trouvé.

Recherche appartement, la démo complète

app(appart1, sud, 3, 60).
app(appart2, nord, 5, 80).
app(appart3, sud, 4, 70).
app(appart4, sud, 6, 90).
app(appart5, sud, 4, 100).
app(appart6, ouest, 8, 50).

catalogue :-
    write('Catalogue...\n'),
    forall(app(X,O,T,P), format("Code ~a orientation ~a T~D prix ~D.000 ~n", [X, O, T, P])).

dispList([]).
dispList([A|B]) :-
  (app(X,_,T,P), X = A),format('~w T~D ~D.000 euros ~n', [X, T, P]),
  dispList(B).


plusGrand(X, ORT, PMax) :-
    app(X, _, T, _), 
    \+ (app(_, O, T2, P), (T2 > T, O = ORT, P =< PMax)).

meilleur(O,P) :- 
    plusGrand(X, O, P),
    write('\nPlus grand: '),
    write(X).

candidats(O, PMax) :-
    findall(X, (app(X,O,_,P), P =< PMax), L),
    write('\nCandidats au catalogue:\n'),
    dispList(L).

recherche(O, P):-  
    meilleur(O, P);
    write('Rien au catalogue.').

test1 :- candidats(sud, 80).

test2 :- recherche(sud, 80).

Pour utiliser ce programme, utilisez la commande consult de la console prolog. Puis tapez:

catalog.
test1.
test2.

Pour respectivement, afficher la liste de tous les appartements, la liste des appartements orientés sud et de prix inférieur à 80, enfin le plus grand parmi ceux qui respectent ces critères.

Vous pouvez aussi donner vos propres critères, comme dans cet exemple:

recherche(nord, 100).

Vous pouvez télécharger le code source.

  1. Le langage Prolog.
  2. Tutoriel Prolog: On enregistre un ensemble de faits.
  3. Tutoriel Prolog: On énonce un problème sous forme de règles.
  4. Démo Prolog: Recherche appartement.