Algo de recherche ds une matrice - Page 1

Hello,
Je programme un truc en BASIC (je le porterai en C après), et j'ai besoin d'un algo qui donne la distance la plus courte entre une cellule mat[l,c] et une cellule contenant la valeur n.
J'en ai un, mais il est plutôt bourrin...
donc si vous avez mieux, n'hésitez pas.

cherche(n)
Prgm
5->dl:10->dc
For a,1,5
For b,1,10
If map[a,b]=n Then
If abs(l-a)<dl ans abs(c-a)<dc Then
a->dl:b->dc
EndIf
EndIf
EndFor
EndFor
dl²+dc²->d
EndPrgm

J'ai des idées pour abréger la recherche, mais c'est un peu compliqué et je me demande si ce sera vraiment plus rapide, puisque ça passera forcément par des IF en plus, donc qui ralentiront les boucles.

J'ai corrigé un truc : j'avais mis un TRY...ENDTRY alors que c'était inutile, parce qu'avant, j'utilisais un algo qui en avait besoin et j'ai pas pensé à l'enlever.
[edit]Edité par jackiechan91 le 21-12-2001 à 13:43:52[/edit]

bah deja si c dans une vraie map . c pas aléatoire la repartition des distances ...

(je dois mal comprendre le probleme là ..)

ouais moi non plus je comprends pas très bien...

hmmm tu as un algo en O(n*k) là et moi je dis y'a mieux... (et y'a mieux que mon algo qué tout pourri)
imagine que tu mets ta matrice en ligne "à plat"
ex: [[1;2][3;4]] devient {1;2;3;4}.
maintenant tu cherches la plus courte distance entre un 2 et l'element qui est en (2,2) donc 4.
ton probleme devient un prbleme de recherche d'un element dans une liste, avec memorisation de la distance. donc dichotomie, tu passes en O((n+k)*ln(n+k)).
y'a plus elegant et sans passer par les listes, c'est la dichotomie sur les matrice: tu decoupes ta matrice en 4 matrices, ... mais là c chiant à faire je trouve. (meme si les listes c chiant aussi).
vala g d'autres idées sympas aussi si tu veux. mais moi je choisirai le premiere... meme si elle prend de la place memoire... (tu peux faire comme si ta matrice etait une liste et la gerer comme tel mais là c bordelique).

la méthode récursive est très souvent de loin la plus rapide, donc pourquoi pas ...
mais c'est moins évident à mettre en place, et ça marche pas tout à fait pareil en basic et en C, mais sinon, découper une matrice en 4, c pas con du tout

Bon, je vais essayer de m'expliquer un peu mieux :
La matrice est comme ça (par exemple) :
{{1,5,2,5,4,3,0,1,5,2}
{1,0,2,0,4,3,0,1,1,2}
{5,1,2,0,3,4,0,1,2,4}
{1,0,2,3,4,0,0,0,1,2}
{0,2,5,4,3,2,0,1,3,0}}

Avec une valeur aléatoire dans chaque cellule.
Et j'aimerais à partir d'une cellule (celle en rouge, par ex) savoir quelle est la distance entre cette cellule et la cellule la plus proche qui contient la valeur 3 (en bleu), par exemple.

Voilà, sinon, je suis désolé, chikensaver, mais je ne comprends pas trop ce que tu m'as conseillé, je ne connais pas la dichotomie.
Et la méthode en découpant la matrice en 4 matrice, je ne comprends pas pourquoi ça serait plus pratique...

Voilà, merci pour vos réponses.
[edit]Edité par jackiechan91 le 21-12-2001 à 13:47:29[/edit]

J'ai peut-être une solution si jamais ta variable en bleu étais la plus grande du tableau. Ça doit être facilement adaptable si c'est pas le cas mais je n'ai pas envie de réfléchir vu l'heure...

disons que ta matrice est simple : 4 sur 4...

[3,2,2,1]
[2,3,1,3]
[3,1,3,2]
[1,1,2,3]

tu prépare une liste de 4x4=16 éléments qui se suivent : {1,2,3,4,5,6,7,8,9,10...}->model

ensuite tu fais :
mat»list(mat)->list
sortd list,model

les premiers éléments de 'list' seront donc ceux que tu recherche, et leur position dans la matrice te sera indiquée dans 'model'

par exemple :
model : {1,6,8,9,11,16,...}
list : {3,3,3,3,3,3,2,2,2...}

tes 6 premiers éléments de 'list' sont la valeur recherchée (3), et leur position est indiquée dans model. list[4] a pour position ds la matrice model[4]. Bien sur il faut reconvertir cette position de liste en position de matrice : mod(model[4],4) en X et int((model[4]-1)/4) en Y.

Voilà il ne te reste plus qu'a prendre la + proche de ces quelques valeurs. Certes cette solution n'est pas la + rapide, loin de la, mais elle l'est quand même plus que ton ancienne, et ne nécéssite pas de connaissances approfondies en maths.

C'est une très bonne idée, mais ça ne convient pas à mon prog, puisque la valeur recherchée n'est pas forcément la plus grande tu tableau

il y a peut-être un moyen d'adapter : le fait que ça soit la + grande valeur du tableau ne servait que pour le 'sort', on doit pvoir se démerder autrement...

Voilà j'ai trouvé :

avant de faire le 'sort', tu fais ça :

abs(list-valeur_recherchée)->list

Comme ça toutes les cases qui avaient la valeur recherchées valent 0, et les autres on nbr supérieur à 0. Il suffit donc de remplacer le sortd par un sorta et le tour est joué

heu même pas besoin de remplacer le sort, les valeurs se retrouveront à la fin de la liste au lieu du début, ça ne change rien.

Merci beaucoup...
Je vais essayer

tu me diras si ça a marché...