Le problème de couverture par sommets en Answer Set Programming avec Clingo
Dans le précédent poste, nous avions résolu le problème de la couverture minimale avec l’Integer Programming. Dans ce billet, nous poursuivons notre exploration de ce problème en implémentant un programme logique Answer Set Programming avec clingo.
Reprenons le meme exemple:
% On commence par définir le graphe non orienté
% L'ensemble des sommets
noeud(a;b;c;d;e).
% L'ensemble des aretes
arete(a,c).
arete(a,d).
arete(a,e).
arete(c,b).
arete(d,e).
% Comme le graphe est non orienté, dès lors qu'une arete u,v existe, l'arete v,u est prise en compte.
arete(U,V) :- arete(V,U).
% Ici commence les choses intéressantes:
% Définition d'une couverture valide
:- couverture(V), - noeud(V).
% la couverture est un sous-ensemble des sommets
1 { couverture(U); couverture(V) } 2 :-
arete(U, V).
cardinal(N) :- #count { V: couverture(V) } = N.
#minimize { N: cardinal(N) }.
#show couverture/1.
clingo version 5.8.0
Reading from /tmp/babel-lLz0Yh/clingo-zvg3tr
Solving...
Answer: 1 (Time: 0.001s)
couverture(c) couverture(d) couverture(e)
Optimization: 3
OPTIMUM FOUND
Models : 1
Optimum : yes
Optimization : 3
Calls : 1
Time : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time : 0.001s
Ce qui donne, en jaune sur le graphe ci-dessous, la couverture minimale:
