Please upgrade your browser for the best possible experience.

Chrome Firefox Internet Explorer
×

Cassetête de la zone héroïque Traken 4 - Balmorra, République

STAR WARS: The Old Republic > Français (French) > Opérations, zones litigieuses, missions héroïques
Cassetête de la zone héroïque Traken 4 - Balmorra, République

Dici's Avatar


Dici
11.23.2012 , 01:24 PM | #21
Bonjour elyyn,

Ton idée a ses avantages, mais en voici les inconvénients.

Rappelons l'implantation la plus simple (algorithmiquement) de l'inversion d'une matrice par un ordinateur utilise la formule :
transposée(comatrice(A)) x A = det A * Identité

Le calcul de la transposée ne pose pas de soucis. La comatrice en revanche demande de calculer n déterminants d'ordre n-1 si A est carrée d'ordre n. Le calcul d'un déterminant est une somme sur un ensemble à n! éléments, dont chaque terme est un produit à n facteurs. Le calcul d'un déterminant d'ordre n-1 est donc en (n-1)!, le calcul de l'inverse avec cet algorithme est en n x (n-1)! = n!... c'est ENORME !!!

Si tu veux inverser une matrice avec une complexité raisonnable, tu introduis un autre problème beaucoup plus complexe que le premier. Certes, il existe des algorithmes faisant ça très bien, mais c'est vraiment utiliser des théorèmes très puissants pour résoudre un problème ridicule (la terminaison d'un certain algorithme d'inversion repose sur la densité des matrices inversibles dans l'ensemble des matrices sur R. Sans être hyper raffiné, c'est largement plus élaboré que mes schémas bêbêtes de résolution).


Autrement, il est vrai que mathématiquement ta solution est meilleure. La mienne n'a reposé que sur la recherche intuitive d'une "base de solution", tandis que tu rationalises le problème en utilisant des outils classiques. Seulement, ma technique de résolution est faisable à la main car sa complexité est faible, la tienne non. Mon algorithme peut s'implanter informatiquement et s'exécuter en un temps raisonnable, le tien également mais demande un grand raffinement dans la méthode employée, ce qui n'est pas mon cas.

Pour conclure je dirais que c'est plus élégant mais un peu inapproprié pour un solveur informatique.

PS : gros point pour toi par contre, tu peux généraliser très, très simplement ce problème à tout n et à toute configuration. Ma solution en revanche n'est pas du tout flexible...

Quand j'y pense, c'est d'ailleurs l'universalité de ta réponse qui fait que sa complexité est supérieure.

Dici's Avatar


Dici
11.23.2012 , 01:38 PM | #22
Quote: Originally Posted by xxBeebeexx View Post
Et les solveurs informatiques ne sont pas toujours des fins matheux mais exploitent plutôt la vitesse des processeurs pour tester bêtement toutes les solutions.
Ca c'est quand on n'a pas peur de bouffer de la mémoire pour rien... Je pense quand même que dans de nombreux domaines on cherche l'optimisation algorithmique : depuis quelques années, on peine à augmenter la puissance de calcul. La loi de Moore n'est plus vérifiée, il y a quelques pistes plus ou moins fouillées allant du calcul parallèle (très utilisé) aux ordinateurs quantiques (prémices) mais globalement, on freine.

Ainsi, pourquoi, au lieu de rendre les PC plus puissants, ne rendraient-on pas les algorithmes plus intelligents ? Dans ce cas précis l'ensemble des solutions est exponentiel... pas terrible !! (L'ensemble des solutions se construit par exemple comme suit : on choisit toutes les solutions possible impliquant 0 pylône parmi les n totaux, puis 1 pylône parmi n, ..., puis n parmi n. La somme du nombre d'éléments trouvés vaut 2^n)

Hovergame's Avatar


Hovergame
11.23.2012 , 01:48 PM | #23
L'exemple d'un problème simple ayant une solution exponentielle (factorielle) est une bonne idée, mais l'inversion de matrice se fait en n^3 simplement, via la matrice compagnon (méthode de Gauss généralisé), qui n'implique pas de définir un déterminant

elyyn's Avatar


elyyn
11.23.2012 , 01:53 PM | #24
J'ai inversé la matrice parce qu'elle était simple, mais il n'est absolument pas nécessaire de faire une inversion pour trouver la solution. L'inversion ne s'applique qu'au cas d'une solution unique, et monte effectivement rapidement en complexité. De façon plus généralisée, on applique directement le pivot de Gauss sur la matrice de départ, ou encore mieux une décomposition LU, afin de trouver "une" solution si elle existe. Ce sont des algorithmes relativement simples, rapides et faciles à implémenter. (en o(n^3) pour la décomposition LU comme dit au-dessus...)

Dici's Avatar


Dici
11.23.2012 , 01:54 PM | #25
Quote: Originally Posted by Hovergame View Post
L'exemple d'un problème simple ayant une solution exponentielle (factorielle) est une bonne idée, mais l'inversion de matrice se fait en n^3 simplement, via la matrice compagnon (méthode de Gauss généralisé), qui n'implique pas de définir un déterminant
Quote: Originally Posted by elyyn View Post
J'ai inversé la matrice parce qu'elle était simple, mais il n'est absolument pas nécessaire de faire une inversion pour trouver la solution. L'inversion ne s'applique qu'au cas d'une solution unique, et monte effectivement rapidement en complexité. De façon plus généralisée, on applique directement le pivot de Gauss sur la matrice de départ, ou encore mieux une décomposition LU, afin de trouver "une" solution si elle existe. Ce sont des algorithmes relativement simples, rapides et faciles à implémenter.

Oui j'en ai parlé sans l'évoquer explicitement. Ce que je voulais dire c'est que les algorithmes performants pour l'inversion d'une matrice n'étaient pas vraiment triviaux.

Par exemple pour la décomposition LU, si on veut prouver sa terminaison dans "presque tous les cas", il faut savoir prouver la densité des matrices inversibles dans l'ensemble des matrices d'un corps. Nous sommes d'accord, c'est pas non plus d'un niveau incroyable mais c'est quand même moins bateau que mon approche naïve.

M'enfin... je m'avoue battu ce que je propose s'étend facile à un nombre beaucoup trop limité de cas : il me faut les mêmes symétries que celles de Traken 4... Je n'avais pas pensé à voir ça comme ça, merci d'avoir élargi l'approche de ce problème !

Promis, je sècherai plus les cours d'algèbre pour dormir un peu plus...