Calcul sur matrice

par **Clembou** » 10 Juil 2008, 13:42

Rémi83 a écrit:Bonjour à tous

J'ai une matrice rectangulaire, et je cherche un petit algorithme qui me permette de calculer sa trace maximale après permutation des lignes et des colonnes (pas sur que je m'exprime très bien). En fait je cherche à sélectionner le meilleur ensemble de point, sachant que je peux en sélectionner qu'un par colonne et par ligne.
Par exemple
pour la matrice
1 1 2 3
2 7 1 0
5 8 1 0
le résultat que cherche est 5+7+3

Merci si quelqu'un a une idée!

Un peu de combinatoire. Est-ce que tu as vu ce qu'est un graphe et sa matrice d'incidence ?

par **john32** » 10 Juil 2008, 13:59

En gros c'est un un problème d'optimisation ou tu veux garder les éléments qui te permettent d'avoir la plus grande somme ?

par **leon1789** » 10 Juil 2008, 14:01

Il cherche la plus grande somme.

Naïvement, je ferais une recherche exhaustive bien bourine. Ca m'intéresse aussi d'avoir une méthode intelligente là dessus :we:

par **Clembou** » 10 Juil 2008, 14:12

Rémi83 a écrit:c'est à dire, pour l'exemple qui m'intéresse, j'aurai une matrice 40*50, le bourrin, ça semble difficile...

Tu considères donc le graphe associé à ta matrice d'incidence et tu fais un algo de Dijsktra particulier (inversé). Par exemple :

Considères le graphe suivant (associé à la matrice d'incidence) :

ensuite il faut trouver trois chemins qui vont de A - B et C de valeur maximale mais qui n'arrivent pas sur les mêmes points d'arrivées.

Dans l'exemple :

(ici on ne peut pas faire

car

est déjà pris par

)

La somme est maximale :

et c'est le rang maximal de ta matrice

de départ...

par **leon1789** » 10 Juil 2008, 14:13

Rémi83 a écrit: En fait je cherche à sélectionner le meilleur ensemble de points

Rémi83 a écrit:oui, c'est bien un problème d'optimisation

ok, c'est donc très différent.

par **leon1789** » 10 Juil 2008, 14:16

Clembou a écrit:ensuite il faut trouver trois chemins qui vont de A - B et C de valeur maximale mais qui n'arrivent pas sur les mêmes points d'arrivées.

Oui, mais on va sommer deux éléments de ligne B en passant par B, non ?

par **leon1789** » 10 Juil 2008, 14:19

Clembou a écrit:ensuite il faut trouver trois chemins qui vont de A - B et C de valeur maximale mais qui n'arrivent pas sur les mêmes points d'arrivées.

j'ai du mal à voir comment on peut arriver à ça (de manière efficace pour une matrice 40x50)

par **Clembou** » 10 Juil 2008, 14:22

leon1789 a écrit:j'ai du mal à voir comment on peut arriver à ça (de manière efficace pour une matrice 40x50)

Tu considère un graphe qui a 40 sommets en haut et 50 sommets en bas (comme dans le graphe précédent) et tu regardes les arrêtes de valeur maximales. Bien sûr, il y aura des chemins plus ou moins efficace. Le tout c'est de suivre un algorithme bien défini pour trouver le bon chemin...

par **leon1789** » 10 Juil 2008, 14:26

Je ne comprends pas ta stratégie :

ligne 1 : je prends 3
ligne 2 : je prends 8
ligne 3 : je prends 2

j'arrive à seulement 13..
Tu vas me dire qu'il fallait prendre 5 à la ligne 2, oui, mais comment savoir ?

Clembou a écrit: Le tout c'est de suivre un algorithme bien défini pour trouver le bon chemin...

oui, c'est bien la question

par **Clembou** » 10 Juil 2008, 14:30

leon1789 a écrit:Je ne comprends pas ta stratégie :

ligne 1 : je prends 3
ligne 2 : je prends 8
ligne 3 : je prends 2

j'arrive à seulement 13..
Tu vas me dire qu'il fallait prendre 5 à la ligne 2, oui, mais comment savoir ?

oui, c'est bien la question

C'est là où est mon problème :zen: :briques: J'essaie de trouver une autre solution avec les multigraphes et Dijsktra

Calcul sur matrice

Qui est en ligne