Recherche d'une formule pour calculer le voisinage d'un point

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour à vous, j'essaye de programmer en python un algorithme qui me permet de calculer le voisinage à n saut d'un point précis. Exemple: soit le carré suivant

00 01 02 03 05

06 07 08 09 10

11 12 13 14 15

16 17 18 19 20

le voisinage à un saut de 0 est 1, 6 et 7. A deux sauts, 2, 8, 13, 11 et 12. Ainsi de suite? Il faut pouvoir calculer pour chaque point, son voisinage à n sauts. Je voudrais savoir si quelqu'un connaît une formule mathématique qui pourrait s'appliquer dans mon cas, parce que je galère vraiment :p Merci d'avance.

Édité par lewoudar

+0 -0

Salut.

Avant de répondre, une petite précision: est-ce que 0, 1, 6 et 7 sont accessibles depuis 0 en 2 sauts?

Pour l'algorithme suivant, je prends comme hypothèse que c'est le cas.

Prenons la fonction (O) jump(p, n) qui prend un point p de ta matrice et un nombre n et retourne une liste de points O.

Il te faudra aussi la fonction O neighbors(p) qui prend un point p et retourne une liste de points O. La sémantique de cette fonction est qu'elle donne tous les points qui sont voisins du point donné. (Je suppose que tu peux implémenter cette fonction toi même, mais n'hésite pas si tu as des soucis.)

Après donné un point p et n sauts il suffit d'appeler jump(p, n), retournant ta liste de points O et le nombre 0. Plus explicitement, jump ressemble à:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
O jump(p, n)

If(n == 1)
  Return (neighbors(p))
Else
  O = jump(p)
  K (liste of points)
  Foreach o in O
    K.add(jump(o, n-1))
  End
  Return K
End

Si j'ai pas fait d'erreur stupide, l'idée devrait marcher. Note que la liste de point n'est pas distincte, dans le sens que un point apparaitra plusieurs fois. C'est aussi un algorighme naïf qui utilise une structure de données extrêmement simple (une matrice), s'il te faut quelque chose de plus efficace, c'est possible.

Édité par Tom Tenv

D.W. "All problems in CS can be solved by another level of indirection" K.H. "…except for the problem of too many layers of indirection."

+1 -0

Tu cherches une formule explicite, ou un algorithme qui calcule les voisinages ? Pour un algo, je n'y ai pas trop réfléchi mais ça fait un peu de temps que je n'ai pas programmé.

Par contre, si tu veux une formule explicite, je pense que c'est ta représentation d'un carré qui n'est pas bonne,. La représentation sous forme de couples (m, n) avec m et n deux entiers devrait te faciliter la vie.

As-tu le choix dans la représentation de tes donnés ? Si c'est le cas, je te recommande de représenter par exemple le nombre 00 par le couple (0, 0), le nombre 03 par le couple (0, 3) et le nombre 14 par le couple (2, 3). Comme un repère cartésien avec l'origine en haut à gauche. Ça devrait être plus facile de trouver une formule.

Si tu ne peux pas faire cela à cause de tes contraintes, on devrait s'en sortir quand même, mais ça va être chiant parce qu'il y a plein de cas (voisinage pas trop grand ? le point dont on prend le voisinage est-il trop près du bord ? etc.)

Je rajoute que si tu as la possibilité de remplacer tes entiers par des couples, il sera toujours possible de trouver une bijection qui retransformera tes couples en entiers comme au départ.

Auteur du sujet

Salut.

Avant de répondre, une petite précision: est-ce que 0, 1, 6 et 7 sont accessibles depuis 0 en 2 sauts?

Tom Tenv

Non 0 n'a pour voisin à un saut que 1, 6 et 7. Par contre j'ai pas très bien saisi ton algorithme :p

Tu cherches une formule explicite, ou un algorithme qui calcule les voisinages ?

As-tu le choix dans la représentation de tes donnés ? Si c'est le cas, je te recommande de représenter par exemple le nombre 00 par le couple (0, 0), le nombre 03 par le couple (0, 3) et le nombre 14 par le couple (2, 3). Comme un repère cartésien avec l'origine en haut à gauche. Ça devrait être plus facile de trouver une formule.

c_pages

C'est un algorithme que je voudrais en fait. Oui j'ai le choix sur la représentation de données.

+0 -0

0 a pour voisin à 1 saut 1, 6 et 7. 1 a comme voisin à 1 saut 0, 2, 6, 7 et 8. Tu peux donc, en partant de 0, faire un saut et arriver à 6 puis retourner à 0 en un saut. 0 est donc atteignable depuis 0 en deux sauts, correct?

L'algorithme est basé sur un simple principe récursif. Tu peux rejoindre en un saut tous les voisins d'un point. (If condition)

Pour plus d'un saut du point p, disons n+1, tu peux rejoindre tous les points joignable en n sauts depuis les voisins de p. (Else condition)

Édité par Tom Tenv

D.W. "All problems in CS can be solved by another level of indirection" K.H. "…except for the problem of too many layers of indirection."

+1 -0

Cette réponse a aidé l'auteur du sujet

Si tu peux représenter ta matrice par des couples d'entiers, c'est facile. Tu considères le couple (i, j). Ses voisins à n sauts sont les couples (i, j+n), (i+1, j+n), …, (i+n, j+n), (i-1, j+n), …, (i-n, j+n). Il y a aussi (i-n, j), (i-n, j+1), …, (i-n, j+n), (i-n, j-1), (i-n, j-n). Enfin, (i, j-n), (i+1, j-n), …, (i+n, j+1), …, (i+n, j+n).

C'est assez illisible et je m'en excuse. Mais en fait c'est très simple : tu pars de ton point et tu notes les coordonnées des points qui sont sur le carré de longueur la taille de ton saut.

Après, il suffit de retirer les points dont les coordonnées dépassent les bords, c'est à dire les points qui ont au moins une coordonnée négative ou au moins une coordonnée plus grande que la taille du carré.

Auteur du sujet

Merci à vous, et particulièrement à c_pages, ton explication sur les couples (i,j) m'a sauvé sur ce coup. Depuis le début de la semaine je galérais sur cet algorithme. J'espère que je te revaudrais ça un jour :p

Vive le Zeste du savoir!! :D

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte