Citation :
fb@alphalog: dans un graphe complet, n'importe quel sommet pri separemment est un dominating set
pour le reste , je seche
|
A partir de là, tout est devenu clair et limpide pour moi (concernant le graphe complet a 3 sommets)
Donc oublions les graphes complets ou ca ne sert pratiquement a rien de chercher un dominated set
Mon probleme principal (comme je l'ai dis dans le tout premier post) est de
trouver un critere greedy pour realiser un algo abstrait.
Recapitulons..
On a la formalisation suivante :
I (input) : G=(V,E) (ou V est l'ensemble des sommets et E l'ensemble des arretes)
S (la solution) : { V' inclus ou egal dans V / Pour tout u V-V' => v V' pour lequel (u,v) E }
f (fonction de mesure de la solution) : |V'| (cardinalité de V')
opt (critere d'optimisation) : MIN (on veux minimiser la solution)
En gros on veux trouver le plus petit sous-ensemble de V qu'on appele V' tel que V' soit un dominating set.
Grace a ce sous ensemble V' on pourras avoir tous les sommets du graphe, et de plus on pourras reconstituer le graphe original en tracant les "bonnes" arretes entre les sommets.
Ca peux servir a plein de choses (cryptographie, optimisation des reseaux etc..), c'est un probleme "MODELE" comme le voyageur de commerce, le subset-sum etc
Ce probleme est NP-dur ! Donc officielement il n'existe pas d'algorithme polynomial (dit en P) pour ce probleme.
Voici un algorithme generique :
L = tableau d'apparition des sommets ou les indices sont les numero des sommets
c'est un tableau de booleens en gros ou 1 sera present et 0 sera absent.
list_adj(i) = renvoi la liste d'adjacence du sommet i.
nextSE(L) = renvoi le sous-ensemble suivant de L
----------------> DSGenerique(L)
1. P?(L)==vrai => DSGenerique(L) = L
2. P?(L)==faux => DSGenerique(L) = DSGenerique(nextSE(L))
----------------> P?(L) = Dom(L, i, n)
1. (i<=n)&&(L[i]==1) => Dom(L, i ,n) = Dom(L, i+1, n)
2. (i<=n)&&(L[i]==0) => Dom(L, i ,n) = alpha(L, list_adj(i), n, i)
3. (i>n) => Dom(L, i ,n) = vrai
---------------> alpha(L, x*M, i, n) ; x est premier element de la liste M
1. L[x]==1 => alpha(L, x*M, i, n) = Dom(L, i+1, n)
2. L[x]==0 => alpha(L, x*M, i, n) = alpha(L, M, i, n)
3. M est vide => alpha(L, x*M, i, n) = faux
---------------------------------------------------------------------------
Bon je ne vai pas faire la trace car ce serai trop long, en tout cas on se rend compte que
au pire des cas on doit executer tout ca 2^|L| fois pur tomber sur un sous-ensemble qui nous satisfait.
Donc la complexité (sans rentrer dans les details) est clairement expo ( O(2^k) c'est pas genial comme approximation ) !
Donc mon probleme est de trouver une heuristique qui permetrait d'avoir une meilleure approximation, peut etre aussi expo mais dont l'algo serait un peu plus fut-fut que ca, car l'algorithme generique ne fait que "traduire" la solution.
On pourais peut etre jouer sur la degré des sommets...
Voilà le probleme
Message édité par Chronoklazm le 27-11-2004 à 13:57:30