Théorie des graphes

Salut tout le monde,
J'ai besoin d'aide pour faire un algorithme qui va faire la chose suivante :

Donc j'ai une matrice qui est pleine de 0 et de 1 je dois lier tous les 0 consecutifs horizontalement ou verticalement sans toucher les 1 et avec un nombre minimum de lignes.

Par exemple :

0 1 0 1
1 0 0 0    
0 0 0 1
1 1 0 1


(|) 1  (|) 1 
 1 (-)(-|)(-)
(-)(-)(-|) 1 
 1  1  (|) 1 

on va faire les lignes:
en verticale :
ligne 0 colone 0
ligne 0 colone 2 + ligne 1 colone 2 + ligne 2 colone 2 + ligne 3 colone 2
en horizontale :
ligne 1 colone 1 + ligne 1 colone 2 + ligne 1 colone 3
ligne 2 colone 0 + ligne 2 colone 1 + ligne 2 colone 2

Comme vous pouvez le voir les lignes peuvent s'intersecter (les cellules [2][2] et [1][2]) .
qui resulte un nombre de 4 lignes.

Ca doit se resoudre avec quelque chose des graphes.
(Desole j' ai pas pu trouve de sujet pour mon post si quelqu'un peut m'aider )

Bonjour,

A ton avis, quels vont être les noeuds, et quels vont être les arêtes du graphe, dans ton exemple ?

Citation:

---

Envoyé par hellfoust

Bonjour,

A ton avis, quels vont être les noeuds, et quels vont être les arêtes du graphe, dans ton exemple ?

---

Bonjour,

Je crois que les arettes seront les liasons entre tous les 0 et les noeuds seront les 0.

Et tu dois trouver la solution optimale obligatoirement ?

As tu une indication sur la complexité maximale de l'algorithme que tu dois trouver ? (en général, ça aide beaucoup de savoir ça)

---------------------------------------
Sinon ton exemple n'est pas terrible, car on trouve la solution optimale immédiatement en construisant le graphe comme tu l'as dit.

Cet exemple est plus utile car on ne trouve pas la solution optimale directement :

0 1 0 1
1 0 0 0
0 0 0 0
1 1 0 1

Quelle est la solution optimale sur cet exemple ?

Une fois que tu as ton graphe de créé comme tu l'as dit, qu'est-ce qu'il faut faire pour avoir la solution optimale sur cet exemple ?

Non la solution doit etre correcte mais pas dans un temps optimale juste un temps resonnable .Non on nous a pas donne une indication sur la complexite.

Je viens de voire la deuxieme partie de post
Voici une image qui peux etre un peux plus claire.
http://i53.tinypic.com/2jd5rm1.jpg`

pour l'exemple que vous m'aviez donne :
le resultat sera 4 on utilise 4 lignes pour traverser tous les 0 sans toucher les 1
Donc
0 1 0 1
1 0 0 0
0 0 0 0
1 1 0 1

=>

Code:

---

1 2 3 4 5

| 1 | 1 1 - -| - - - -| - 1 1 | 1

---

Pour les lignes je ne me refere pas aux petite lignes mais a toute la ligne compose de petits trait successive

Oups, j'ai dit une bêtise. En fait, dans l'exemple du tout premier post de cette discussion, on ne trouve pas le résultat optimal directement. Voici le graphe construit selon ta règle :

http://pix.isalo.org/upload/original/1304626620.png

Là on voit bien que la solution construite selon ton algorithme actuel (la règle que tu as dite), ne renvoit pas la solution optimale (tu utilises 5 lignes).

Et sur mon exemple, ton algo utilise 6 lignes.

Comment pourrais-tu améliorer ton algo pour diminuer le nombre de lignes utilisées ?

les lignes de quelle je parle sont colorie en rouge et il y'a 4 le numero minime
http://i52.tinypic.com/13yfhwi.png

Je ne sais pas comment proceder j'ai acune idee je suis meme pas sur que les 0 sont les noeuds et les arretes sont les liaisons entre eux.
Et je crois que me suis mal exprime :(

Donc comme dans la derniere photo que j'ai mis .
la ligne avec la coulere
violet represente la premiere ligne 1
bleu la deuxieme
rouge la troisieme
vert la quatrieme

Voici une solution qui est incorrecte car elle utilise 5 lignes
http://i55.tinypic.com/2m82qyu.png

Bonjour,

Si, mettre les noeuds sur les zéros et les arêtes aux mêmes endroits que les liaisons entre les zéros est une bonne idée.

Seulement, ça ne donne pas le résultat optimal tout de suite. Après avoir fait ça, il y a une étape de rafinement à faire.

Avec l'exemple du premier post, si tu ne fais pas de rafinement, voici la solution que tu obtiens (automatiquement) :

http://img839.imageshack.us/img839/5383/2m82qyu.png

Une fois que tu as construit ton graphe, la solution que tu as trouvé se déduit simplement :

• si un noeud est isolé, alors il utilise une ligne (il n'y a pas vraiment le choix). Donc ajouter +1 au nombre de lignes. Dans l'exemple il n'y a qu'un seul noeud isolé : le noeud 1.
  
• ensuite pour chaque ligne noire tu rajoutes +1 au nombre de lignes utilisées. Pour l'instant ton algo de création de graphe créé 4 lignes noires (2-4-8-9 . . . 3-4-5 . . . 6-7-8 . . . 3-7).
  
• tu fais la somme du nombre de noeuds isolés et du nombre de lignes noires pour connaître la solution que tu as obtenue. Dans l'exemple 4 + 1 = 5.
  

En fait, ce qu'il faut faire, c'est construire le bon graphe. Une fois que c'est fait, la solution optimale se déduit simplement de ce graphe.

Question :

Quel est le graphe optimal pour ton exemple ? (Fais un dessin qui ressemble à celui que j'ai fait deux posts plus haut)

Pourquoi ne pas simplement

1. Parcourir la matrice par lignes & colonnes croissantes
2. Pour chaque Xij=0, compter le nombre L de 0 adjacents en ligne et le nombre C de 0 adjacents en colonne (contenant Xij)
3. Prendre la partie de ligne ou de colonne si L>C ou inversement, SAUF si cette partie est déjà contenue dans un segment déjà construit
4. Garder donc dans une liste le nouveau segment éventuellement crée.

C'est itératif sur i*j et c'est simple! Plutôt que de garder un liste de segments crée, on peut avoir une matrice booléenne où on flagge les éléments i*j déja traités...

Oui il faut cette etape de rafinement ou je dois enlever les arettes petite entre les noeuds qui appartiennennt a des lignes plus importante (qui couvre d'autres noeuds)
(l'arrete 3-7 ne dois plus exister)
Le graphe correct est : http://i53.tinypic.com/14nzm0l.png
Quand j'avait dit que les noeuds seront les 0 et les arretes seront toutes les liasonns entre 0 ca ne represente pas la solution juste une maniere pour poser le probleme dans la memoire .

Citation:

---

Envoyé par Nemerle

Pourquoi ne pas simplement

1. Parcourir la matrice par lignes & colonnes croissantes
2. Pour chaque Xij=0, compter le nombre L de 0 adjacents en ligne et le nombre C de 0 adjacents en colonne (contenant Xij)
3. Prendre la partie de ligne ou de colonne si L>C ou inversement, SAUF si cette partie est déjà contenue dans un segment déjà construit
4. Garder donc dans une liste le nouveau segment éventuellement crée.

C'est itératif sur i*j et c'est simple! Plutôt que de garder un liste de segments crée, on peut avoir une matrice booléenne où on flagge les éléments i*j déja traités...

---

Je crois que ca marche mais je suis pas sur si c'est dans tous les cas.
Je vais essayer et vous repindre ecaxtement.

Citation:

---

Envoyé par cyberkamikaz

Oui il faut cette etape de rafinement ou je dois enlever les arettes petite entre les noeuds qui appartiennennt a des lignes plus importante (qui couvre d'autres noeuds)

---

Quoi ? Tu parles d'utiliser une version modifiée d'un algorithme qui trouve un arbre couvrant ?

------------------------------------------------------------------------

EDIT : en fait, l'idée de chercher un arbre couvrant n'est pas bonne. La solution optimale n'est pas obligatoirement connexe :

http://pix.isalo.org/upload/original/1304884145.png

D'ailleurs on voit bien avec cette exemple qu'un algorithme glouton qui consiste à sélectionner les lignes qui couvrent le plus de noeuds ne marche pas (dans cet exemple, il ne faut pas sélectionner la grande ligne verticale).

Si on considère qu'il n'y a pas de noeuds isolés, un noeud peut être dans deux configurations possibles :
- il peut être couvert par deux lignes différente (verticale et horizontale)
- il ne peut être couvert que par une seule ligne (verticale ou horizontale)

Si un noeud est dans la deuxième configuration, alors il faut utiliser la seule ligne qui passe par lui, et la rendre la plus longue possible. Il faut marquer les noeuds couverts par cette ligne avec un booléen.

Ensuite un noeud qui n'est pas encore couvert peut être dans trois états possibles :
- il est le seul à ne pas être couvert dans sa rangée et dans sa colonne
- il y a un autre noeud qui n'est pas couvert dans sa rangée ou dans sa colonne
- il y a un autre noeud qui n'est pas couvert dans sa rangée et dans sa colonne

Dans le premier cas, on utilise la rangée ou la colonne qui passe par le noeud, ça ne change rien.

Dans le deuxième cas, on doit utiliser la ligne qui passe par le noeud qui couvre d'autres noeuds.

Dans le troisième cas, on ne sait pas quoi faire.

Tu sélectionnes des lignes ainsi jusqu'à ce que tout les noeuds du graphes soient couverts, ou jusqu'à ce qu'ils soient tous dans le troisième état. A ce moment là, tu peux tenter une approche gloutonne comme celle proposée par Nemerle (à savoir utiliser en premier la ligne qui couvre le plus de noeuds encore non couverts).

Mais je ne sais pas si la stratégie gloutonne renverra la solution optimale.

J'avait implementé la methode dont m'a donné Nemerle et comme vous l'avez montré ca marche pas dans tous les cas . 13 passé 3 raté.
Je vais voir votre dernierre solution hellfoust mais dans l' apres midi. Maintenant je dois partir. Je vais vous répondre ce soir .

Je pense que ton problème peut être vu comme un problème de set cover dans lequel chaque ensemble correspond à une ligne possible (les éléments sont donc les cases). Le nombre d'ensemble à considérer doit être raisonnable (au plus il doit y avoir n*m lignes, soit le nombre de cases) mais ça reste un problème difficile. Cette formulation devrait te permettre de trouver pas mal d'info.

Citation:

---

Envoyé par hellfoust

http://pix.isalo.org/upload/original/1304884145.png

---

Bon exemple, effectivement ma proposition n'est pas ok. Si l'on enleve le noeud No 3 par exemple, la ligne verticale + les 3 noeuds isolés fournit aussi une solution acceptable (4 segments). Donc bien évidement, il n'y a pas unicité.

En fait, on peut ajouter une règle supplémentaire pour améliorer l'algo:


1. Parcourir la matrice par lignes & colonnes croissantes
2. Pour chaque Xij=0, compter le nombre L de 0 adjacents en ligne et le nombre C de 0 adjacents en colonne (contenant Xij)
3. Prendre la partie de ligne ou de colonne si L>C ou inversement, SAUF si cette partie est déjà contenue dans un segment déjà construit

4. Si le segment est en L (resp. en C), à chaque élément Xij du segment on associe 0 ou 1 en fonction de ce que Xij a au moins un voisin direct "vertical" (resp. "horizontal"): donc 1 si Xi(j-1)=0 ou Xi(j+1)=0 (resp. si X(i-1)j=0 ou X(i+1)j=0). Sommer alors ces valeurs, donnant une valeur finale V comprise entre 0 et le nombre de noeuds du segments. Si ce nombre V égal le nombre de noeuds, alors le segment est ko, on ne l'utilise pas.

5. Garder donc dans une liste le nouveau segment éventuellement crée.


Voila. Il faudra éventuellement parser plus d'une fois la matrice; on peut ajouter aussi une règle 4': si dans 4 le segment S est ko, on teste les 2 segments obtenus en enlevant une des 2 extrémités...

Variante (inverse) de l'approche de Nemerle :

1. calculer le degré de chaque sommet
2. prendre le 1er sommet "S" non-rayé ayant le degré le plus faible
3. rayer le plus grand nombre de sommets a partir de S
4. retour au 2

Si j'ai bien compris vos algo, ce cas devrait les embeter :

http://pix.isalo.org/upload/original/1304947781.jpg

Citation:

---

Envoyé par Acrim

Si j'ai bien compris vos algo, ce cas devrait les embeter ...

---

Oui, ça montre que ma règle ajoutée à la va-vite est débile :aie:

Par contre, Pseudo a commencé à me le corriger: il faut en effet prendre un noeud ayant le minimum de voisins, puis le segment de taille maximale.

Il faut par contre ajouter à ces règles la suivante : aux 2 segments Ligne ou Colonne qu'on peut construire à partir du noeud, on calcule le nombre de lignes Horizontales ou Verticales qui recouvrent ce qui reste --> ça fait 2*2 calculs, et on prend alors le segment L ou C qui minimise ce nb de lignes...

Et avec cet algo, tous les cas ci-avant fonctionnent.

Un nouvel exemple qui devrait mettre la nouvelle règle en défaut :
http://pix.isalo.org/upload/original/1304954830.jpg


Le problème provient du fait que les conséquences d'un choix (ligne ou colonne ?) fait pour une case sont découvertes bien plus tard. Il faudrait donc soit pouvoir identifier les droites critiques (la longueur de la droite et le degré des nœuds ne semblent pas suffisant) et les fixer en premières, soit utiliser une approche qui peut remettre en cause les choix déjà fait. Ce n'est que mon avis :).

Je vois que ca ce complique de plus en plus.
On m'a dit que sa ce resoud avec les graphes (flux ou ...)
+la resolution avec une methode greedy n' est pas si bien accepte(penalite de -50% ).