Discussion :

[azev]

hello à tous,
je vais expliquer mon problème par un exemple

j'ai une liste d'objets incompatibles c'est à dire
si j'ai
o1 incompatible avec o2 et o1 incompatible avec o3
o2 incompatible avec o1 et o2 incompatible avec o3
o3 incompatible avec o1
alors je crée un groupe o1 incompatible total avec o2
et un groupe 01 incompatible total avec o3

par contre si j'ai
o1 incompatible avec o2 et o1 incompatible avec o3
o2 incompatible avec o1 et o2 incompatible avec o3
o3 incompatible avec o1 et o3 incompatible avec o2
alors je ne crée qu'un groupe o1 incompatible total avec o2 et o3

mon but est de trouver un algo qui me permette de trouver tous ces groupes d'incompatibilité maximum sachant que j'ai environ 70 objets et que chacun d'eux est incompatible avec une 15aine

j'espere que ce sera assez clair

Merci pour votre aide!

[Matthieu Brucher]

Rien compris.

[azev]

qu'est ce qui n'est pas clair?

[FrancisSourd]

Si j'ai bien compris, il faut regarder le problème comme un problème de graphe. On construit ainsi le graphe dont les sommets sont les objets et deux objets sont reliés par une arête si ils sont réciproquement incompatibles.

Une incompatibilité totale correspond à une clique (sous-graphe où tous les sommets sont reliés entre eux).

Le problème revient donc à chercher toutes les cliques du graphe (ou peut être une couverture du graphe par un nombre minimal de cliques), ce qui est malheureusement un problème difficile (NP-complet). Il faut donc soit avoir recours à des algorithmes énumératifs, soit à des heuristiques qui donnent des résultats approchés...

[azev]

ouep merci FrancisSourd, c'est bien ça mon problème
mais qu'entends tu par algorithmes énumératifs?

[FrancisSourd]

mais qu'entends tu par algorithmes énumératifs?

Il s'agit d'algorithmes de complexité exponentielle qui énumèrent toutes les solutions possibles, c'est-à-dire toutes les cliques. Pour cela, on peut d'abord énumérer toutes les cliques de taille 2 (facile, ce sont les arêtes). Puis les cliques de taille 3 en prenant les cliques de taille 2 et en essayant de rajouter un sommet puis ainsi de suite: on obtient les cliques de taille n en essayant de rajouter à chaque clique C de taille n-1 un sommet relié à tous les sommets de C.

En général, ces algos ne sont pas efficaces. On peut les rendre plus rapides par le branch-and-boud ou séparation et évaluation
http://fr.wikipedia.org/wiki/Branch_and_bound
D'autres méthodes proches sont la programmation linéaire en nombres entiers ou la programmation par contraintes.

[azev]

merci
je vais essayer de creuser un peu ça

[cboun94]

Bonjour,

j'ai peut etre mal compris, mais il me semble que ce pb n'est pas si compexe que cela...

Reprenons la très bonne idée du graphe.
Chaque sommet est un objet.
On crée un lien entre 2 ssi il y a incompatibilité "réciproque".

On cherche les groupes d'incomp de l'objet Oi.
Pour cela on établie la liste de tous les Oj liés à Oi.
On utilise ensuite un simple parcours des Oj avec étiquetage pour trouver les groupes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
groupes = {}
CreerGroupes(Oi)
 
CreerGroupes(Oi)
Begin
  etiquette = 0
  Pour chaque Oj lié à Oi
    Si Oj.eti = 0 Alors
      etiquette++
      PorpageEtiquette(Oj, etiquette, Oi)
    Fin si
  Fin pour
End
 
PorpageEtiquette(Oi, etiquette, Origine)
begin
  groupes[etiquette].add(Oi)
  Oi.eti = et
  Pour chaque Oj lié à Oi et à Origine
    Si Oj.eti = 0 Alors
      PorpageEtiquette(Oj, etiquette, Origine)
    Fin si
end

On n'oublira pas d'initialiser les Oi.eti=0

En espérant ne pas m'etre trompé.

[Jedai]

Ben non... Parce que là tu te contente de trouver la composante connexe de Oi, pas de trouver les cliques auxquelles il appartient.

--
Jedaï

[cboun94]

Arf, c pas faux ...

Petite question :
si O1--O2, O1--O3, O1--O4, O2--O3, O2--04, sachant qu'on a pas O3--04, on fait quoi ?

Moyenne question :
si O1--O2, O1--O3, O1--O4, O1--O5, O2--O3, O2--04, O3--O4, O2--O5, ca donne quoi ?

PS : "--" = "Incompatibilité réciproque"

[benratti]

Tiens, c'est marrant, j'aurais plutot penser a une probleme de coloration de graphe... qui est certes equivalent a la recherche de cliques mais qui semblent plus proche du probleme. Mais bon, le probleme reste le meme et la solution donnee et tres bien.

[azev]

Arf, c pas faux ...

Petite question :
si O1--O2, O1--O3, O1--O4, O2--O3, O2--04, sachant qu'on a pas O3--04, on fait quoi ?

Moyenne question :
si O1--O2, O1--O3, O1--O4, O1--O5, O2--O3, O2--04, O3--O4, O2--O5, ca donne quoi ?

PS : "--" = "Incompatibilité réciproque"

le 1er ça donne un groupe O1,O2,O3, un autre groupe O1,O4 et un dernier O2,O4

le 2ieme ça donne gpe O1,O2,O3,O4; 1gpe O1,O5 et le dernier O2,O5

[FrancisSourd]

Petite question :
si O1--O2, O1--O3, O1--O4, O2--O3, O2--04, sachant qu'on a pas O3--04, on fait quoi ?

Moyenne question :
si O1--O2, O1--O3, O1--O4, O1--O5, O2--O3, O2--04, O3--O4, O2--O5, ca donne quoi ?

PS : "--" = "Incompatibilité réciproque"

C'était effectivement une question que je me posais à la lecture du problème... On peut effectivement chercher une couverture des arêtes par des cliques, ou couverture des sommets par des cliques, ou encore toutes les cliques maximales (au sens de l'inclusion).

[FrancisSourd]

Arf, c pas faux ...

Petite question :
si O1--O2, O1--O3, O1--O4, O2--O3, O2--04, sachant qu'on a pas O3--04, on fait quoi ?

Moyenne question :
si O1--O2, O1--O3, O1--O4, O1--O5, O2--O3, O2--04, O3--O4, O2--O5, ca donne quoi ?

PS : "--" = "Incompatibilité réciproque"

le 1er ça donne un groupe O1,O2,O3, un autre groupe O1,O4 et un dernier O2,O4

le 2ieme ça donne gpe O1,O2,O3,O4; 1gpe O1,O5 et le dernier O2,O5

C'est donc une partition des arêtes en un nombre minimal de cliques!
(chaque arête dans une seule clique)

[cboun94]

Donc on est d'accord ? C'est pas NP ?

[FrancisSourd]

Donc on est d'accord ? C'est pas NP ?

Si si, je pense bien que c'est NP-complet. Je n'ai pas de réf sous la main mais au moins la partition des sommets est NP-complet:
http://www.nada.kth.se/~viggo/wwwcompendium/node25.html

[random]

si je construis trois matrices carrées de booléens
dans la première je gère la compatibilité 1 2
dans la seconde je gère la compatibilité transitive 2 1
dans la troisième je fais un et logique
j'obtiens une matrice de comatibilté totale dans la troisième
en parcourant cettre matrice pour chaque valeur de la liste
je crées une liste ordonnée des incomptabilités totales
je regroupe les listes semblables
je reprends depuis le début en remplacant le et par un ou