Algo (mal de crane)

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!

Rien compris.

qu'est ce qui n'est pas clair?

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...

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

Citation:

---

Envoyé par azev

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.

merci
je vais essayer de creuser un peu ça

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:

---

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 :lol:

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

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

--
Jedaï

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 :wink: :
si O1--O2, O1--O3, O1--O4, O1--O5, O2--O3, O2--04, O3--O4, O2--O5, ca donne quoi ?

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

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.

Citation:

---

Envoyé par 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 :wink: :
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

Citation:

---

Envoyé par cboun94

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 :wink: :
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).

Citation:

---

Envoyé par azev

Citation:

---

Envoyé par 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 :wink: :
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)

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

Citation:

---

Envoyé par cboun94

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

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