Discussion :

[cyberkamikaz]

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 )

[Invité]

Bonjour,

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

[cyberkamikaz]

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.

[Invité]

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 ?

[cyberkamikaz]

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.


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 :

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

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

[Invité]

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 :



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 ?