Answer set programming

Coloration d'un graphe avec trois couleurs.

Le problème de coloration de graphe consiste à attribuer des couleurs à des sommets d'un graphe non orienté de façon que deux sommets reliés n'aient pas la même couleur. Le problème ASP suivant permet de savoir si un tel graphe est coloriable ou non et d'obtenir une coloration :

c(1..n).
1 {couleur(X,I) : c(I)} 1 :- sommet(X).
:-couleur(X,I), couleur(Y,I), relie(X,Y), c(I).

La première ligne définit les numéros ${\displaystyle 1,\dots ,n}$ comme les couleurs possibles. La ligne suivante attribue une couleur unique à chaque sommet ${\displaystyle X}$. La contrainte en ligne 3 interdit d'affecter la même couleur aux sommets ${\displaystyle X}$ et ${\displaystyle Y}$, si une arête les relie. Le programme dans cet exemple illustre l’organisation en « générer et tester » que l'on trouve souvent dans les programmes ASP simples. La règle de choix en ligne 2 décrit un ensemble de « solutions possibles ». Elle est suivie d’une contrainte, ici en ligne 3 qui élimine toutes les solutions possibles qui ne sont pas acceptables, ici qui ne sont pas des bons coloriages.

À cela, il faut ajouter une description du graphe comme par exemple :

sommet(1..10).
relie(1,2).
relie(2,3).
relie(3,4).
relie(4,5).
relie(6,8).
relie(6,9).
relie(7,9).
relie(8,10).
relie(1, 6).
relie(2, 7).
relie(3, 8).
relie(4, 9).
relie(5, 10).

Le programme smodels est exécuté sur celui-ci, avec la valeur numérique de ${\displaystyle n}$ spécifiée sur la ligne de commande, le programme donne des atomes de la forme ${\displaystyle couleur(\dots ,\dots )}$ qui représentent un coloriage du graphe avec ${\displaystyle n}$ couleurs.

Une clique de trois sommets.

Une clique dans un graphe est un ensemble de sommets reliés deux à deux. Le programme suivant de lparse trouve une clique de taille ${\displaystyle \geq n}$ dans un graphe donné, ou détermine s'il n’en n'existe pas :

n {dansclique(X) : sommet(X)}.
:-dansclique(X), dansclique(Y), sommet(X), sommet(Y), X ! = Y, not relie(X,Y), not relie(Y,X).

Il s’agit d’un autre exemple de l’organisation de générer-et-tester. La règle de choix en ligne 1 « génère » tous les ensembles de sommets avec ${\displaystyle n}$ sommets. La contrainte à la ligne 2 « supprime » les ensembles qui ne sont pas des cliques.

Un cycle hamiltonien dans un graphe orienté est un chemin qui passe exactement une et une seule fois par chaque sommet. Le programme Lparse suivant trouve un cycle hamiltonien dans un graphe donné, s’il existe. Nous supposons que 0 est l'un des sommets.

{dansChemin(X,Y)} :- relie(X,Y).
:- 2 {dansChemin(X,Y) : relie(X,Y)}, sommet(X).
:- 2 {dansChemin(X,Y) : relie(X,Y)}, sommet(Y).
atteignable(X) :- dansChemin(0,X), sommet(X).
atteignable(Y) :- dansChemin(X,Y), relie(X,Y).
:- not atteignable(X), sommet(X).

La règle de choix en ligne 1 « génère » tous les sous-ensembles composées d'arêtes du graphe. Les deux contraintes « éliminent » les sous-ensembles qui ne sont pas des chemins. Les deux lignes suivantes définissent le prédicat auxiliaire atteignable(X) (« X est accessible depuis le sommet 0 ») de manière récursive. Ce prédicat permet (dernière ligne) de vérifier que le chemin couvre tout le graphe.

Ce programme est un exemple de l’organisation plus générale de « générer, définir et tester » : il inclut la définition d’un prédicat auxiliaire qui nous permet d’éliminer toutes les solutions possibles mais « mauvaises ».