Discussion :

[kenzo75]

Bonjour, j'essaye d'implémenter un algorithme de recherche d'élément par dichotomie (récursif si possible) sur une matrice trié par ligne et par colonne mais je n y arrive pas trop voir même pas du tout.
Sur un tableau 1D j' y arrive parfaitement mais sur une autre matrice c'est une autre affaire.

Voici un exemple de matrice triée :

1 2 5 9
8 12 15 17
10 13 16 19
11 14 17 23

J'ai pensé à diviser à prendre l'élément du milieu par exemple 13, puis comparer l'élément x recherché a 10 (premier élément de la ligne du milieu) et a 19 (dernier élément de la ligne du milieu). Si x > 10 et x > 19 alors on recherchera en bas de du milieu.
Si x < 10 et x < 19 on recherchera en haut du milieu etc ..
Ensuite faire de même à gauche et a droite, donc on divise la matrice en 4 en quelque sorte.
Mais il reste plusieurs sous cas que je ne trouve pas et je ne suis même pas sur que c'est faisable.
Merci de m'aider

[DonQuiche]

Bonjour.

D'abord j'imagine que tes lignes sont triées en fonction de leur premier élément seulement ? Mais qu'entre deux lignes consécutives, deux éléments de la même colonne (hormis le premier) peuvent être arbitrairement ordonnés ? Autrement dit on peut affirmer que M[i,0] < M[j,0] mais on ne peut rien dire sur M[i,k] et M[j,k] ?

Si oui tu ne peux pleinement exploiter la dichotomie que sur la dimension horizontale, au sein d'une ligne. Mais entre les lignes tu ne peux utiliser la dichotomie que pour rechercher la dernière des lignes à scanner. En effet tu ne dois scanner que les i tels que M[i,0] <= x. Mais tu dois impérativement scanner tout ce sous-ensemble. Soit un O(n.log(n))



Si en revanche je me trompe et que M[i,k] < M[j,k] quel que soit k et quels que soient i < j, alors je pense que la bonne stratégie est de chercher (en utilisant la dichotomie) la dernière des ligne à parcourir d'après le premier élément, puis au sein de ce sous-ensemble la dernière des colonnes à parcourir en utilisant la dernière ligne, puis au sein de ce sous-ensemble la première des lignes en utilisant la dernière colonne, puis la première colonne en utilisant la première ligne, etc. Autrement dit tu décrirais une spirale pour circonscrire un rectangle de plus en plus petit. C'est du O(2*log(n) + 2*log(n/2) + 2*log(n/4) + ...). C'est inférieur à O(log(n)*log(n)) puisqu'on a log2(n) termes. Je pense qu'on ne peut pas faire mieux.

[ToTo13]

Bonjour,

dans le cas d'une matrice, la dichotomie n'est plus l'algorithme le plus approprié : tu ne supprimes plus la moitié des éléments, mais un quart.
Il existe une recherche beaucoup plus rapide.

[kenzo75]

@donquiche
Si il y a une relation d ordre entre deux elements d'une même colonne :

1 2 5 9
8 12 15 17
10 13 16 19
11 14 17 23

Ici : 1<8<10<11 et même raisonnement pour les autres colonnes
Pour les lignes : 1<2<5<9

Je pense qu'un algo en o(n) est faisable : en comparant l element cherché à chaque premier élement des lignes de la matrice, puis en effectuant une dichotomie sur la ligne qui correspond.
Mais y aurai-t-il un un algorithme de meilleur complexité??

[ToTo13]

Mais y aurai-t-il un un algorithme de meilleur complexité??

Pour une matrice de taille NxM, il y a un algorithme en O(N+M). Il suffit de partir d'en bas à gauche et de comparer la valeur avec celle cherchée : plus petit tu montes, plus grand tu vas à droite.
Cela est possible car ta matrice est doublement triée.

[kenzo75]

Je pense aussi que c'est la meilleure implémentation, j vais essayer ça, biensur si quelqu'un d'autre à meilleure j'suis preneur.
Merci pour tout

[DonQuiche]

Pour une matrice de taille NxM, il y a un algorithme en O(N+M). Il suffit de partir d'en bas à gauche et de comparer la valeur avec celle cherchée : plus petit tu montes, plus grand tu vas à droite.
Cela est possible car ta matrice est doublement triée.

@donquiche
Si il y a une relation d ordre entre deux elements d'une même colonne :

Alors c'est le second cas de figure pour lequel j'avais proposé un algo en O(ln(n) * ln(n)), ce qui est meilleur que du O(n+n).

[kenzo75]

@donquiche
Je ne comprends pas trop l'algo, y aurait moyen de l'expliquer un peu plus , ou donner un exemple ? Merci

[DonQuiche]

Imagine que tu as un rectangle qui recouvre toute ta matrice, la valeur cherchée est quelque part là-dedans. Le principe de l'algorithme c'est de rétrécir le rectangle à chaque itération en bougeant un bord à chaque fois et en exploitant l'information obtenue à l'itération précédente. D'abord le côté inférieur, puis le gauche, puis le supérieur, puis le droit, et bis repetita.

Si on cherche 9 dans cet exemple:
1 2 5 7
8 9 15 17
10 13 16 19
11 14 17 23

En regardant (O(log 4)) la première colonne et on peut exclure les deux dernières lignes (tout y est supérieur ou égal à 10), ce qui laisse :
1 2 5 7
8 9 15 17

Maintenant on cherche (O(log 4)) dans la dernière ligne et on peut exclure la première colonne (tout y est inférieur ou égal à 8), ce qui laisse :
2 5 7
9 15 17

Maintenant on cherche (O(log 2)) dans la colonne de droite et on peut exclure la première ligne (tout y est inférieur ou égal à 7), ce qui laisse :
9 15 17


Pour une petite matrice l'algo en O(n+n) sera plus rapide. Mais si ta matrice est grande mieux vaut celui-ci.

[kenzo75]

Oui mais dans cet exemple je ne pense pas que cela foncionne : cherchons 14 dans
1 2 5 14
3 4 6 16
13 17 19 24
32 64 69 96

Il va chercher dans
13 17 19 24
32 64 69 96

Alors qu il est en premiere ligne nan?

[DonQuiche]

Non à la première itération tu gardes les trois premières lignes : celles qui sont susceptibles de contenir la valeur d'après la colonne de gauche. Tu recherches dans la colonne de gauche et par dichotomie le dernier élément inférieur ou égal à la valeur souhaitée.

[kenzo75]

Ici :

1 2 5 14
3 4 6 16
13 17 19 24
32 64 69 96

On recherche 16 par dichotomie dans la premiere colonne, on se débrouille pour que l indice renvoyé soit celui de 32.
Puis on garde que la sous matrice excluant la derniere ligne et on recommence mais cette fois ci avec la derniere ligne

1 2 5 14
3 4 6 16
13 17 19 24

Et on garde ce qui >= 16 donc on exclu la premiere colonne etc c est ça?
Mais j vois pas comment l 'implément ca a l'air compliqué à coder
Aurais tu une idee de pseudo code? Merci

[DonQuiche]

Quelque chose comme :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
M, X1, Y1, X2, Y2, X, Y, Valeur
 
fonction chercher(valeur)
   Valeur = valeur
   tant que vrai
      si ChercheX1OuModifieY2() retourner
      si ChercheY1OuModifieX2() retourner
      si ChercheX2OuModifieY1() retourner
      si ChercheY2OuModifieX1() retourner
   fin
fin
 
fonction ChercheX1OuModifieY2()
    Y = RechercheBinaireX(X1, Y1, Y2) // Renvoie plus grand inférieur ou égal à Valeur
    Y2 = Y
    retourner M[X1, Y] == Valeur
fin
 
fonction ChercheX2OuModifieY1()
    Y = RechercheBinaireX(X2, Y1, Y2)
    Y1 = Y + 1
    retourner M[X2, Y] == Valeur
fin

[ol9245]

Robert Sedgewick donne un algo génia que j'utilise aussi
tu fais une recherche dichotomique sur les lignes -> suppression de la moitié des lignes restantes.
puis la même chose sur les colonnes -> suppression de la moitié des colonnes restantes.
et ainsi de suite.

Pour +d'info je te conseille ce livre magnifique : http://www.amazon.fr/Algorithmes-en-.../dp/2744072567

[kenzo75]

@ol9245
C est ce que m a proposé donquiche nan?

@donquiche
Je t avoue que je comprends pas trop ton pseudo code.. peux tu me détailler un peu ?
Merci

[ol9245]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
fonction couper-matrice(double Matrice : M, double clé : cx, xy, integer bas-gauche : x0, x1, integer haut-droite : y0, y1, integer direction)
si direction = 1
si x1 == x0 -> il y a rien à couper : sortie
sinon     
    couper = (x0+x1)/2
    si cx < couper : x1 = couper
    sinon : x0 = couper
    fin si
fin si
 
sinon si direction = 2
si y1 == y0 -> il n'y a rien à couper : sortie
sionon
    couper = (y0+y1)/2
    si cy < couper : y1 = cx
    sinon : y0 = couper
   fin si
fin si

puis :

Code :

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

1
2
3
4
5
6
7
8
x0 = 1, x1 = nombre de colonnes
y0 = 1, y1 = nombre de lignes
direction = 1
 
tant que on n'a pas à la fois x0=x1 et y0=y1
    couper-matrice(M, cx, xy, x0, x1, y0, y1, direction)
    direction = 3 - direction (bascule 1-2 2-1)
fin tant-que

[ToTo13]

Mon algo est aussi trivial que rapide et s'implémente en quelques minutes. Commence donc par faire un test avec, puis tu essaies d'optimiser en testant les autres.

[kenzo75]

@ ol9245

Dans ton algo je ne comprends pas ce que sont cx et cy, qui ne sont pas de plus initialisées. Et je ne comprends pas pourquoi on fait aucun test avec la valeur chercher ..
Merci

[ol9245]

@ ol9245

Dans ton algo je ne comprends pas ce que sont cx et cy, qui ne sont pas de plus initialisées. Et je ne comprends pas pourquoi on fait aucun test avec la valeur chercher ..
Merci

c'est les arguments de la fonction, comme indiqué.

[kenzo75]

@donquiche
pourquoi pas Y1 = Y au lieu de Y1 = Y +1??