Discussion :

[emixam16]

Bonjour à tous,et désolé par avance pour la longueur de mon post, elle est due à mes dessins d'illustration.

Dans un algorithme j'obtiens des matrice d'ordre n (avec n pair). Ces matrices sont définies uniquement pour le triangle supérieur et ne peuvent contenir que des 0 et des 1.

Par exemple:

_ _ _ _ _ _
|0 1 0 0 0 1
|0 0 0 1 1 0
|0 0 0 0 1 0
|0 0 0 0 1 0
|0 0 0 0 0 0
|0 0 0 0 0 0

Ou dans un cas général avec x = 0 ou 1 et n = 8.

col 0 1 2 3 4 5 6 7
lin _ _ _ _ _ _ _ _
0 |0 X x x x x x x
1 |0 0 x x x x x x
2 |0 0 0 x x x x x
3 |0 0 0 0 x x x x
4 |0 0 0 0 0 x x x
5 |0 0 0 0 0 0 x x
6 |0 0 0 0 0 0 0 x
7 |0 0 0 0 0 0 0 0

On a le droit de changer DE LA MÊME MANIÈRE l'ordre des lignes et des colonnes.

Par exemple on peux avoir:
col 0 3 1 2
lin _ _ _ _
0|
3|
1|
2|

mais pas
col 0 1 3 2
lin _ _ _ _
0|
3|
1|
2|
(car les lignes font 0132 != colonnes 0312).


Enfin ce que j'apelle demi-diagonale (je ne connais pas le nom de ceci, si tenté que ça en ait un) est : aij tel que i = n/2+k et j = k avec k<n/2.
Si n = 8, elle est notée avec des x

col 0 1 2 3 4 5 6 7
lin _ _ _ _ _ _ _ _
0 |0 0 0 0 x 0 0 0
1 |0 0 0 0 0 x 0 0
2 |0 0 0 0 0 0 x 0
3 |0 0 0 0 0 0 0 x
4 |0 0 0 0 0 0 0 0
5 |0 0 0 0 0 0 0 0
6 |0 0 0 0 0 0 0 0
7 |0 0 0 0 0 0 0 0

Voila, j'ai enfin tout défini!

Je cherche à un algo qui me permettrait de savoir combien on peut mettre de 1 au maximum sur la demi-diagonale. (On a le droit d'inverser les lignes colonnes comme montrées plus haut). Comme n est compris entre 0 et 200, je souhaite avoir une complexité polynomiale.

J'ai eu vraiment beaucoup d'idées, mais elles étaient toutes en n! ou en (n/2)!.

A mon avis faudrait faire une opération sur la matrice qui pourrait me donner le résultat de cette rotation sans les tester effectivement toutes...

Si quelqu'un à une idée, ou même une piste je suis preneur.

Merci d'avance

[Flodelarab]

Bonjour

Le majorant est le nombre de valeur de k. Si un majorant est atteint, c'est un un maximum. La question est : Qu'est-ce qui pourrait empêcher la demi-diagonale de se remplir de 1 ?

[emixam16]

Tout d'abord merci de ta réponse!

Le majorant est le nombre de valeur de k. Si un majorant est atteint, c'est un un maximum.

Si ce que tu appelles "le nombre de valeur de k" est le nombre d’éléments qu'on peut mettre sur la demi-diagonale, alors oui évidemment si la diagonales est complète ça fait un maximum, la valeur de ce maximum atteignable est n/2.


Par exemple si j'ai cette matrice


col 0 1 2 3 4 5 6 7
lin _ _ _ _ _ _ _ _
0 |0 0 0 0 0 0 0 1
1 |0 1 0 1 0 1 1 1
2 |0 0 0 0 0 0 0 1
3 |0 0 0 0 0 0 0 1
4 |0 0 0 0 0 0 0 1
5 |0 0 0 0 0 0 0 1
6 |0 0 0 0 0 0 0 0
7 |0 0 0 0 0 0 0 0

On ne pourra jamais remplir la 1/2 diagonale peu importe la rotation de la matrice.

Par contre cette matrice marche


col 0 1 2 3 4 5 6 7
lin _ _ _ _ _ _ _ _
0 |0 0 0 0 0 0 0 1
1 |0 0 0 0 0 0 1 0
2 |0 0 0 0 1 1 0 0
3 |0 0 0 0 1 0 0 1
4 |0 0 0 0 0 0 0 0
5 |0 0 0 0 0 0 0 0
6 |0 0 0 0 0 0 0 0
7 |0 0 0 0 0 0 0 0

Car elle peut se transformer en cette matrice.

col 0 1 2 3 7 6 5 4
lin _ _ _ _ _ _ _ _
0 |0 0 0 0 1 0 0 0
1 |0 0 0 0 0 1 0 0
2 |0 0 0 0 0 0 1 1
3 |0 0 0 0 1 0 0 1
7 |0 0 0 0 0 0 0 0
6 |0 0 0 0 0 0 0 0
5 |0 0 0 0 0 0 0 0
4 |0 0 0 0 0 0 0 0

Il faudrait donc que j'arrive à trouver un algo qui me permettent de voir si des rotations permettent de compléter la demi diagonale (sinon voir combien de zéros resteront dans la demi diagonale au minimum).

J'ai l'impression qu'en faisant des produit matriciels avec masque on doit pouvoir se rapprocher de la solution, mais je n'arrive pas à trouver exactement comment. Je n'arrive pas non plus a voir comment faire marcher une méthode itérative (en complexité polynomiale)...

Une dernière façon de le voir serait en degrés d'hyperstatisme, et il suffirait de les enlever 1 par un mais la réalisation d'une solution de ce type ne me semble pas triviale.

Intuitivement, j'ai l'impression qu'on peut retirer les degrés 2 par deux en faisant la somme logique (1+1=1) des termes sur chaque lignes & colonne et les additionner ex :

col 0 1 2 3 4 5 6 7
lin _ _ _ _ _ _ _ _
0 |0 0 0 0 0 0 0 1 ->1
1 |0 0 0 0 0 0 1 0 ->1
2 |0 0 0 0 1 1 0 0 ->1
3 |0 0 0 0 1 0 0 1 ->1
4 |0 0 0 0 0 0 0 0 ->0
5 |0 0 0 0 0 0 0 0 ->0
6 |0 0 0 0 0 0 0 0 ->0
7 |0 0 0 0 0 0 0 0 ->0
| | | | | | | |
0 0 0 0 1 1 1 1

lin+col:
0 = 1+0 = 1
1 = 1+0 = 1
2 = 1+0 = 1
3 = 1+0 = 1
4 = 0+1 = 1
5 = 0+1 = 1
6 = 0+1 = 1
7 = 0+1 = 1
On a que des uns donc on est sur qu'on peut retirer 2 degrés d'hyperstatisme et qu'il y aura 2 un sur la demi-diagonale.

Mais la ou je bloque est de savoir a quelle matrice rappliquer cette méthode jusqu'à trouver un 0...

Si quelqu'un à une idée sur cette méthode ou sur une autre je suis preneur,

Merci beaucoup

[stendhal666]

Je n'ai eu que quelques minutes pour réfléchir à ton problème, donc je donne un avis qui vaut ce qu'il vaut: tu peux améliorer grandement l'efficacité d'un algorithme de complexité factorielle en ajoutant une heuristique qui te donne la direction à regarder en priorité: l'idée est d'attribuer un score aux différentes permutations de colonnes possibles à partir d'une position donnée, et d'explorer en priorité la permutation qui a le meilleur score (en l'occurrence le score pourrait être le nombre de 1 placés correctement sur la demi-diagonale). Si tu trouves une demi-diagonale complète le tour est joué; sinon, il faudrait regarder précisément la complétude de l'algorithme mais il n'est pas impossible qu'à partir du moment où le score recule tu puisses considérer que tu as atteint le nombre de 1 maximal sur la demi-diagonale.

[anapurna]

salut

en regardant tes exemple
e serait il pas simple de vérifier t'a diagonal
et lorsque celle ci est a un vérifier l’existence de ce point dans l'autre diagonal

je verrai bien un truc du genre

Code :

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

1
2
3
4
5
6
7
 
impossible = false
pour i de 0 a n
  pour j de i a n 
    si tab[i,j] = 1 alors 
      si tab[j,i] = 1 alors 
         impossible = vrai

[emixam16]

Merci encore pour vos réponses!

Je n'ai eu que quelques minutes pour réfléchir à ton problème, donc je donne un avis qui vaut ce qu'il vaut: tu peux améliorer grandement l'efficacité d'un algorithme de complexité factorielle en ajoutant une heuristique qui te donne la direction à regarder en priorité: l'idée est d'attribuer un score aux différentes permutations de colonnes possibles à partir d'une position donnée, et d'explorer en priorité la permutation qui a le meilleur score (en l'occurrence le score pourrait être le nombre de 1 placés correctement sur la demi-diagonale). Si tu trouves une demi-diagonale complète le tour est joué; sinon, il faudrait regarder précisément la complétude de l'algorithme mais il n'est pas impossible qu'à partir du moment où le score recule tu puisses considérer que tu as atteint le nombre de 1 maximal sur la demi-diagonale.

Ll'idée d'une heuristique me semble intelligent, mais dans l'état actuel, je ne crois pas que ça soit applicable. En effet, pour donner un score aux différentes permutations, il faut que je les teste toutes, non? Et même si donner un score est très rapide, je reste dans du O(n!), impossible pour n grand... Ou alors, j'ai pu mal comprendre quelque chose !

impossible = false
pour i de 0 a n
pour j de i a n
si tab[i,j] = 1 alors
si tab[j,i] = 1 alors
impossible = vrai

Je ne comprends pas ce que tu veux faire avec cet algorithme, mais en l'état actuel ça ne peut pas marcher (ou en tout cas je ne vois pas comment l'utiliser).

N'ayant toujours pas trouvé de solution à mon problème, je reste ouvert à vos idées

Maxime.