Maximum de valeurs sur des "demi-diagonales" de matrices

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

Bonjour :coucou:

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 ?

Tout d'abord merci de ta réponse!

Citation:

---

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

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.

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:

---

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

---

Merci encore pour vos réponses!

Citation:

---

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 !

Citation:

---

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.

salut

mon idée est de ne vérifier que la moitie de la matrice donc ce que tu appel une diagonal
ensuite lors de ta vérification sur cette diagonale il te faut juste vérifier la possibilité de la faisabilite en inversant
simplement les indice => tab[i,j] => tab[j,i]
exemple tab[1,3] => tab[3,1]

rien ne sert de vérifier ta matrice complète puisqu'il existe une symétrie par rapport à la diagonal

Oui, de toute évidence, je ne vais pas m'amuser à checker les endroits inutiles. Ta methode ne peux pas marcher car elle fait tester toutes les rotations. si il y à N lignes dans la matrices, il y à n = N/2 cases sur la 1/2 diagonale et donc toujours n! où (N/2)! cas à tester,sans compter le temps de faire effectivement ces rotations, en O(N). Donc il est totalement impossible d'utiliser une implémentation de ce type.

Citation:

---

Envoyé par emixam16

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 !

---

Dans le scénario sans heuristique tu explores les n! permutations sans ordre. Si la demi-diagonale est trouvée à la n!ème permutation, tant pis pour toi
Dans le scénario avec heuristique tu explores d'abord n permutations, tu prends celle qui a le score maximal, puis tu génères n-1 permutations, tu prends celle qui a le score maximal, etc. Donc: au minimum tu trouveras nettement plus vite la demi-diagonale si elle existe. Ce qui est déjà un progrès. Mettons maintenant qu'elle n'existe pas. Mettons de plus que tu sois arrivé au terme de l'exploration des permutations qui permettent d'élever le score de façon maximale: est-ce que cela signifie qu'il n'existe pas d'autre chemin dans les permutations permettant d'augmenter le nombre de 1 sur la demi-diagonale? A vue de nez, c'est impossible à dire. Cela peut se tester de façon empirique, ou bien demande de réfléchir attentivement aux propriétés mathématiques du problème demandé. J'aurais tendance à utiliser la voie empirique puisque tu peux tester tes résultats.

On peut chercher dans une autre direction. Plutôt que faire des permutations, en fait, il suffit de chercher n/2 points qui vérifient quelques contraintes. Une fois qu'on a trouvé n/2 points, alors la façon dont on répartit ces n/2 points sur la demi-diagonale est neutre, on peut les disposer dans l'ordre qu'on veut.
Et quelles sont ces contraintes sur le choix des n/2 points ?
1. Les points sur la diagonale descendante sont interdits. On peut faire toutes les permutations qu'on veut, ils resteront sur la diagonale.
2. Si je prend un point sur la case i:j, alors tous les autres points qui se trouveraient sur la ligne i ou sur la colonne j deviennent interdits. On peut donc les remplacer par des 0.
3. Si j'ai un point qui est seul sur sa ligne, ou bien seul sur sa colonne (éventuellement après les suppressions de points des règles 1 et 2), je peux le sélectionner pour le mettre sur ma demi-diagonale, je suis sûr que c'est un choix optimal.

Avec ces principes, il semble qu'on arrive à trouver l'optimum avec très peu de backtracking.

Nouveau rectificatif :
Règle 2 : Si je prend un point sur la case i:j, alors tous les autres points qui se trouveraient sur la ligne i ou sur la colonne j deviennent interdits. On peut donc les remplacer par des 0. Et idem pour les points de la ligne j et ceux de la colonne i.

Citation:

---

Mettons de plus que tu sois arrivé au terme de l'exploration des permutations qui permettent d'élever le score de façon maximale: est-ce que cela signifie qu'il n'existe pas d'autre chemin dans les permutations permettant d'augmenter le nombre de 1 sur la demi-diagonale? A vue de nez, c'est impossible à dire

---

J'ai testé avec une heuristique. Des fois les chemins qui ont à priori le moins bon score fonctionnent quand même et d'autres avec un score très élevé non. Et en plus ça arrive souvent selon mes tests. Donc si je veux une bonne fidélité du résultat, je dois tout tester... Ce qui enlève l’intérêt d'une heuristique ... Donc je ne suis pas convaincu qu'une heuristique s'applique bien à mon exemple.

Citation:

---

On peut chercher dans une autre direction. Plutôt que faire des permutations, en fait, il suffit de chercher n/2 points qui vérifient quelques contraintes. Une fois qu'on a trouvé n/2 points, alors la façon dont on répartit ces n/2 points sur la demi-diagonale est neutre, on peut les disposer dans l'ordre qu'on veut.
Et quelles sont ces contraintes sur le choix des n/2 points ?
1. Les points sur la diagonale descendante sont interdits. On peut faire toutes les permutations qu'on veut, ils resteront sur la diagonale.
2. Si je prend un point sur la case i:j, alors tous les autres points qui se trouveraient sur la ligne i ou sur la colonne j deviennent interdits. On peut donc les remplacer par des 0.
3. Si j'ai un point qui est seul sur sa ligne, ou bien seul sur sa colonne (éventuellement après les suppressions de points des règles 1 et 2), je peux le sélectionner pour le mettre sur ma demi-diagonale, je suis sûr que c'est un choix optimal.

Avec ces principes, il semble qu'on arrive à trouver l'optimum avec très peu de backtracking.

Nouveau rectificatif :
Règle 2 : Si je prend un point sur la case i:j, alors tous les autres points qui se trouveraient sur la ligne i ou sur la colonne j deviennent interdits. On peut donc les remplacer par des 0. Et idem pour les points de la ligne j et ceux de la colonne i.

---

C'était la première idée que j'ai eu, et il doit y avoir moyen de s'en sortir avec. Cela dit, dans l'état des choses, il faut quand même tester toutes les possibilités pour avoir le "meilleur chemin". Donc, je ne vois pas comment faire mieux qu'un pire cas en O((n/2)!) avec cette idée de base.
Si tu as une idée pour abaisser la complexité, je suis toujours preneur. :)

Je pense avoir trouvé quelque chose, à tester.

Je me demandais ce que pouvait bien signifier cet énoncé. Ni la demi-diagonale, ni la manière de permuter n'ont de sens en calcul matriciel, du moins à ma connaissance.
En revanche, si la matrice est la matrice d'adjacence d'un graphe, c'est beaucoup plus parlant:
- la permutation ensemble de deux lignes et de deux colonnes est une manière d'échanger la place de deux sommets du graphe
- la petite diagonale signifie que les sommets sont reliés deux par deux (1 , n/2+1) ... (n/2 , n)

Si on prend une matrice dont seule la demi-diagonale est à 1, on peut la représenter par un graphe rectangulaire de dimensions: n/2 , 2
A B C D
| | | |
E F G H

En réalisant des permutations, on ne change pas la propriété fondamentale qu'il y a n/2 arêtes qui, deux par deux, ne sont connectées ni par l'origine ni par la destination.

Donc, trouver le nombre de 1 possibles sur la demi-diagonale équivaut à énumérer le nombre de paires de sommets reliés dont l'intersection deux par deux est vide. Cela est faisable avec un algorithme naïf en n² et certainement plus rapidement avec un peu de réflexion.

Pour reprendre tes exemples:

1. la matrice qui ne fonctionne pas
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 a uniquement 2 arêtes dont l'intersection 2 par 2 est vide:
0-7, 1-6 (ou 1-5, 1-3, peu importe)
=> le nombre maximal de 1 sur la demi-diagonale est de 2

2. la matrice qui fonctionne
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

on a 0-7, 1-6, 2-5 et 3-4: 4 arêtes dont l'intersection 2 par deux est vide
=> on peut remplir la demi-diagonale.

J'avais aussi tenté de voir le problème comme ça mais je ne suis pas sur que ça simplifie le problème

Voici une implémentation de cet algo.

Outre la médiocrité de mon implémentation, cet algorithme est proche de la solution. Mais il n'est pas optimal car c'est un algorithme glouton. Si on ne teste pas toute les possibilités on est jamais sur d'avoir pris la meilleure. Pour améliorer la précision du résultat, j'ai à chaque fois sélectionné le nœud avec le moins de possibilités avec celui avec le moins de possibilités compatible... Dans les tests que j'ai réalisés, je ne me suis jamais éloigné à plus de 2% de la solution optimale.

Cela dit, l'objectif de l'exercice est une solution optimale. Et mon implémentation naïve ne peut pas la donner. Si tu vois une manière d'améliorer celle-ci, même en perdant (un peu) d'efficacité, je suis preneur !

Je me disais qu'il y avait probablement un parti à tirer de la programmation dynamique, même si je ne suis pas sûr de la façon exacte.
Le but est de savoir si le quart de matrice en haut à droite contient une permutation de la demi-diagonale: il y a (n/2)! permutations de la demi diagonale.
On représente chaque permutation par un tableau, ex: {n/2, n/2+1 ... n) où le rang dans le tableau est l'indice x dans la matrice et la valeur dans le tableau l'indice y dans la matrice.
Alors Si on a testé toutes les permutations commençant par {4, 5 ...} il ne sert plus à rien de tester les permutations {5, 4 ... }.
Donc en conservant en mémoire une hashmap qui prend en clé un préfixe trié et en valeur le nombre de points de la permutation couverts dans la matrice, on peut éviter de parcourir toutes les permutations.
Je ne sais pas si le trade-off mémoire / temps te convient et je ne suis pas sûr de la complexité de l'algorithme, mais cela devrait être une amélioration assez radicale.

salut

en réfléchissant rapidement pour chaque rotation ,tu peut éliminer des diagonales si les point des extrêmes ne sont pas a 1
pour chaque test tu as 6 points a trouver
0,0
0,N\2
0,N
N\2,N\2
N\2,N
N,N
là tu n'aurais au pire que 3 segments qui corresponde à hypoténuses des triangles formé à vérifier
c'est a dire que chaque couple contrôlé aurais des 1 aux extrémité

ce qui complique le truc c'est le nombre de permutation que tu peut faire et j'ai du mal a voir comment on peut réduire ce nombre

PS un des point de la droite doit obligatoirement passer par sa diagonal donc
tu peut aussi éliminer les permutations ou le point extrême ne passe pas par (k,N\2+k)

salut

bon continuer sur ma réflexion
je suppose que tes case remplit de 1 sont dans une file ou un arbre car apparemment ta matrice s'apparente a une matrice creuse
et plus tu auras d’éléments a gérer plus tu prendra de la place en mémoire inutilement

donc si tu as remplis un file ou une liste en la parcourant
il te suffit de vérifier que le point peut vérifier cette condition (k,N\2+k)

si je me souvient bien il faut que tes ligne est le même ordre que tes colonne cela revient
donc à quelque soit les rotation tes points on en déplacement en diagonal

ce qui implique que quelque soit la rotation voulu le point doit forcement passer par cette condition
une fois que l'on a dis ça il ne te reste plus qu'a compter les point verifiant cette condition

Bonjour,

J'ai réussi à résoudre ce problème.

Ma méthode à été de prouver que le nombre de 1 est inférieur à une valeur m, et supérieure à une valeur M. Tant que m!=M, on supprime une ile qui pose problème et on recommence.

Cet algorithme est en O(d*n²) avec d = M-m.

C'est pas génialement optimisé, mais ça marche avec n>1000 donc je m'en contenterais.

Merci à tous de votre aide.

Je passe le sujet en résolu.

ça m'intéresserait d'avoir plus d'infos sur ta méthode, je ne comprends pas bien ce que tu veux dire...