Déjà rien que pour formuler le titre du topic j’ai du mal, c’est pour dire.
En fait j’ai 2 matrices et dans celles-ci j’essaye de trouver la partie commune aux deux.
J’ai fait un (superbe) dessin :
Pour résoudre le pb j’ai essayé de le faire sur un tableau à 1 dimension seulement au départ. Mais en 2D le truc est juste complètement différent et je sais pas comment trouver la zone commune maximale…
Sur le dessin « abcdef » est la partie maximale mais j’arrive pas à la différencier de « fghi ».
Il faut que je fasse quoi ? Que je stocke dans un tableau toutes les parties communes de plus de 1 case de côté et regarder à la fin quelle est la plus grande ?
Si vous avez une piste où si vous avez déjà résolu ce truc tordu de façon plus simple, faites moi signe.
Déjà, arrives tu à trouver la partie commune ? Dans ce cas, tu peux commencer ton algo de détection des parties communes à l’envers (cad en partant de la matrice elle même comme point de comparaison, puis en enlevant petit à petit des lignes ou colonnes). Ca devrait te donner la première partie commune la plus grande (sachant qu’il peut y en avoir plusieurs de même taille).
[quote name=‹ kaneloon › date=’ 20 Jan 2005, 14:09’]Déjà, arrives tu à trouver la partie commune ? Dans ce cas, tu peux commencer ton algo de détection des parties communes à l’envers (cad en partant de la matrice elle même comme point de comparaison, puis en enlevant petit à petit des lignes ou colonnes). Ca devrait te donner la première partie commune la plus grande (sachant qu’il peut y en avoir plusieurs de même taille).
[right][post=« 324094 »]<{POST_SNAPBACK}>[/post][/right][/quote]
J’arrive tout juste à résoudre le problème sur une dimension mais je n’arrive même pas à raisonner sur 2.
Par exemple
a b c
d e
est une partie commune mais pas « rectangulaire », donc il faudrait que je la rejette. Tous ces petits problèmes m’empêchent de trouver une façon clean de raisonner.
En fait je finis toujours par me retrouver avec des dizaines d’imbrications de for, de if et autres while…
Sinon merci beaucoup Moktar, ton url m’aurait bien aidé mais c’est malheureusement en C++ et là je suis bloqué en C
Breuaf,
En prenant la matrice la plus petite comme référence (A)(col + lignes).
Tu as col*lignes types de sous-matrices pouvant se retrouver dans la plus grande matrice ( B ).
Par ex : (nb lignes, nb col.) avec k = nb de colonnes de la plus petite matrice et n = nb de lignes de la plus petite matrice
(1,1) (1,2) … (1, n)
(2,1) (2,2) … (2, n)
(k,1) (k,2) … (k, n)
Ensuite, tu prends toutes les sous_matrices de A de taille (1,1), et tu regardes si une est présente dans B. Et ainsi de suite… Sachant que si une sous_matrice de taille (x,y) n’est pas présente, alors les sous-matrices de taille (x, y+1); (x+1,y);(x+1;y+1) ne seront pas présentes, ce qui devrait accélérer le calcul.
Il existe surement plein d’optimisation de ce truc…Je te pond ça en live.
[quote name=‹ Kingston › date=’ 20 Jan 2005, 14:50’]J’arrive tout juste à résoudre le problème sur une dimension mais je n’arrive même pas à raisonner sur 2.
Par exemple
a b c
d e
est une partie commune mais pas « rectangulaire », donc il faudrait que je la rejette. Tous ces petits problèmes m’empêchent de trouver une façon clean de raisonner.
En fait je finis toujours par me retrouver avec des dizaines d’imbrications de for, de if et autres while…
Sinon merci beaucoup Moktar, ton url m’aurait bien aidé mais c’est malheureusement en C++ et là je suis bloqué en C
[right][post=« 324112 »]<{POST_SNAPBACK}>[/post][/right][/quote]
Ben, tu fais une couche en C pour offrir le changement d’API C++ → C et tu mets tout ça dans une LIB, qui offre donc une API C. Hop, comme ça pas vu pas pris
[quote name=‹ Kingston › date=’ 20 Jan 2005, 17:22’]Merde on doit pas avoir le même level en C
Merci pour les pistes je vais essayer de voir ca…
[right][post=« 324181 »]<{POST_SNAPBACK}>[/post][/right][/quote]
C’est pas un probléme en C Mais tu peux faire des char** en les instanciant bien !
[quote name=‹ Kingston › date=’ 20 Jan 2005, 17:22’]Merde on doit pas avoir le même level en C
Merci pour les pistes je vais essayer de voir ca…
[right][post=« 324181 »]<{POST_SNAPBACK}>[/post][/right][/quote]
Bah… Si c’est un problème de programmation… hum… Tu poses une question d’algo… Si tu crois que je vais te répondre en C…
Tiens… Je pense à un truc… en rajoutant des colones remplies de 1 sur les matrices pour obtenir 2 matrice carrés de même taille, on doit pouvoir les comparer bien plus vite…et tout d’un coup… à creuser.
[quote name=‹ kaneloon › date=’ 20 Jan 2005, 18:06’]Bah… Si c’est un problème de programmation… hum… Tu poses une question d’algo… Si tu crois que je vais te répondre en C…
Tiens… Je pense à un truc… en rajoutant des colones remplies de 1 sur les matrices pour obtenir 2 matrice carrés de même taille, on doit pouvoir les comparer bien plus vite…et tout d’un coup… à creuser.
[right][post=« 324196 »]<{POST_SNAPBACK}>[/post][/right][/quote]
On parle C courament ici c’est pour ca que l’on fait peur au reste des gens d’ ailleur moi je sais pas Mais bon il serait naturel de leur faire peur si on parler LISP courament … Mais ma dignité à des frontiéres que ma conscience n’a pas …
[quote name=‹ koubiak › date=’ 20 Jan 2005, 18:43’]On parle C courament ici c’est pour ca que l’on fait peur au reste des gens dlleur moi je sais pas on leur feraii peur si on parler LISP courament …
Koubiak
[right][post=« 324207 »]<{POST_SNAPBACK}>[/post][/right][/quote]
ahah, mouaip, pour un algo, je trouve ça plus simple en langage naturel. En plus ça évite de se prendre la tête avec un formalisme, dont, personnellement, je me fous.
[quote name=‹ kaneloon › date=’ 20 Jan 2005, 18:46’]ahah, mouaip, pour un algo, je trouve ça plus simple en langage naturel. En plus ça évite de se prendre la tête avec un formalisme, dont, personnellement, je me fous.
[right][post=« 324208 »]<{POST_SNAPBACK}>[/post][/right][/quote]
On devrait instaurer que l’on doit tous coder en machine de turing
Bon je lâche pas l’affaire mais je lutte bien quand même, merci pour les explications en tout cas.
En plus Koubiak qui me nargue en disant qu’il pourrait le faire en une soirée
C’est pas du juste…
[quote name=‹ Kingston › date=’ 22 Jan 2005, 17:16’]Bon je lâche pas l’affaire mais je lutte bien quand même, merci pour les explications en tout cas.
En plus Koubiak qui me nargue en disant qu’il pourrait le faire en une soirée
C’est pas du juste…
[right][post=« 324792 »]<{POST_SNAPBACK}>[/post][/right][/quote]
A non pas en une soirée mais en deux heures surement
Mais la je plenche sur un probleme un peut plus long
Tu devrais pour une premiére étape trouver tout les similitude entre deux matrices
Tu peux pas faire une matrice moins l’autre de toute les maniere possible, Ensuite tu regardes le motif des 0 ?? tu stoques tout das un arbre (par exemple) et tu prends le plus grand motif …
Edit Pour prendre le plus grand motif (je suis en plein dans mes revision d’algebre)
Un fois que t’a ta matrice avec les 0 quand les 2 coef sont egaux …
Tu mets tous les coef differant de 0 a 1 ca te fait plein de vecteur
Pour tourver les motif tu regardes le vecteur qui a le plus de 0 ( n ) (en mettant les autre coordonnés a 1 sinon ca marche pas)
Tu regardes si il y en a d’autre si yen a pas tu passes au vecteur qui a n-1 0
Si il y en a tu mate si ya des vecteurs qui lui resemble (en faisant des produits scalaires par exemple)
Ce problème me titille le cortex depuis que je l’ai lu, je n’arrive pas à entrevoir de solution dont la complexité ne soit pas exponentielle. Je ne trouve pas, ça m’énerve et ça m’énerve.
Alors quand je lis que certains ont la solution toute prête dans leur tête, ça me frustre et ça me frustre.
Donc si quelqu’un a la solution, un algo suffisamment détaillé de la recherche des matrices communes, j’aimerais qu’il la poste ici ou en PM (bien que je pense que ce problème en intéresse d’autres) afin que j’atteigne enfin le calme et la sérénité.
[quote name=‹ GrandChef › date=’ 25 Jan 2005, 21:07’]Ce problème me titille le cortex depuis que je l’ai lu, je n’arrive pas à entrevoir de solution dont la complexité ne soit pas exponentielle. Je ne trouve pas, ça m’énerve et ça m’énerve.
Alors quand je lis que certains ont la solution toute prête dans leur tête, ça me frustre et ça me frustre.
Donc si quelqu’un a la solution, un algo suffisamment détaillé de la recherche des matrices communes, j’aimerais qu’il la poste ici ou en PM (bien que je pense que ce problème en intéresse d’autres) afin que j’atteigne enfin le calme et la sérénité.
[quote name=‘GrandChef’ date=’ 25 Jan 2005, 21:07’]Ce problème me titille le cortex depuis que je l’ai lu, je n’arrive pas à entrevoir de solution dont la complexité ne soit pas exponentielle. Je ne trouve pas, ça m’énerve et ça m’énerve.
Alors quand je lis que certains ont la solution toute prête dans leur tête, ça me frustre et ça me frustre.
Donc si quelqu’un a la solution, un algo suffisamment détaillé de la recherche des matrices communes, j’aimerais qu’il la poste ici ou en PM (bien que je pense que ce problème en intéresse d’autres) afin que j’atteigne enfin le calme et la sérénité.
Merci.
[right][post=“325667”]<{POST_SNAPBACK}>[/post][/right][/quote]
Je dis pas que j’ai la solution ultime. Mais bon, à mon avis, on doit pouvoir trouver un algo en O(n²), ou n = max(nblignes, nbcolonnes).
