algorithme pour traverser les coordonnées 3D sans revoir

Question

Disons que nous avons un ensemble de coordonnées 3D (entier) de (0,0,0) à (100,100,100) Nous voulons visiter chaque coordonnée possible (100^3 coordonnées possibles à visiter) sans visiter chaque coordonnée plus d'une fois. La somme des différences entre chaque coordonnée dans les étapes adjacentes ne peut pas être supérieure à 2 (je ne sais pas si cela est possible, sinon elle est minimisée) par exemple, le pas de (0,2,1,1)) à (2,0,0) a une différence totale de 5 car | x1-x2 | + | y1-y2 | + | z1-z2 | = 5

Comment générer une telle séquence de coordonnées?

par exemple, pour commencer: (0,0,0) (0,0,1) (0,1,0) (1,0,0) (1,0,1) (0,0,2) (0,1,1) (0,2,0) (1,1,0) (2,0,0) (3,0,0) (2,0,1) (1,0,2) (0,0,3) etc ...

Tout le monde connaît un algorithme qui va générer une telle séquence à une coordonnée arbitraire (x, y, z) où x = y = z ou peut prouver que c'est imp ossible pour tel et l'algorithme d'exister? Merci

Crédit supplémentaire: montrer comment générer une telle séquence avec x = y = z:! D

Answer 1

Un des trucs (il y a d'autres approches) est de le faire une ligne [secteur] à la fois, un plan [carré] à heure. Abordant la dernière partie de la question, cette approche fonctionne, même si la taille du volume visité n'est pas la même dans chaque dimension (ex: un bloc de 100 x 6 x 33).

En d'autres termes:

 
Start at (0,0,0), 
move only on the Z axis till the end of the segment, i.e. 
(0,0,1), (0,0,2), (0,0,3), ... (0,0,100), 
Then move to the next line, i.e. 
(0,1,100) 
and come backward on the line, i.e. 
(0,1,99), (0,1,98), (0,1,97), ... (0,1,0), 
Next to the next line, going "forward" 

And repeat till the whole "panel is painted", i.e ending at 
... (0,100,99), (0,100,100), 
Then move, finally, by 1, on the X axis, i.e. 
(1,100,100) 
and repeat on the other panel,but on this panel going "upward" 
etc. 

Essentiellement, chaque mouvement se fait sur une seule dimension, exactement un. C'est un peu comme si vous «marchiez» d'une pièce à l'autre dans un bâtiment 101 x 101 x 101 où chaque pièce peut conduire à n'importe quelle pièce directement sur un axe donné (c'est-à-dire ne pas se rejoindre en diagonale).

L'implémentation de ce type de logique dans un langage de programmation est triviale! La seule partie avec un léger défi consiste à faire face au "va-et-vient", c'est-à-dire le fait que parfois, certains changements dans une dimension donnée sont positifs, et parfois négatifs).

Éditer: (La question de Sid à propos de faire la même chose en diagonale):
Oui! ce serait tout à fait possible, puisque le problème indique que nous pouvons avoir une distance de [Manhattan] de deux, ce qui est nécessaire pour aller en diagonale.
Le chemin serait similaire à celui indiqué ci-dessus, c'est-à-dire.les lignes faisant, de va-et-vient (ici seulement des lignes de longueur variable), se déplaçant ensuite vers la prochaine « panneau », dans la troisième dimension, et à répéter, ne va « vers le haut », etc.

 
(0,0,0) (0,0,1) 
(0,1,0)     first diagonal, only 1 in lengh. 
(0,2,0)     "turn around" 
(0,1,1) (0,0,2)   second diagonal: 2 in length 
(0,0,3)     "turn around" 
(0,1,2) (0,2,1) (0,3,0) third diagonal: 3 in length 
(0,4,0)     turn around 
etc. 

Il est En effet, il est possible de mélanger ces approches, à la fois au niveau du "panneau" complet, en faisant par exemple un en diagonale et le suivant horizontalement, ainsi que dans un panneau donné, par exemple en commençant en diagonale, mais en haut ligne, en procédant avec le motif horizontal, en s'arrêtant simplement un peu plus tôt en faisant une boucle sur le côté "gauche", puisqu'une partie de ce côté a été manipulée avec les diagonales.
Effectivement cela permet un nombre assez important (mais évidemment fini) de "peindre" l'ensemble de l'espace. L'essentiel est d'éviter de laisser (trop) de zones adjacentes non peintes derrière, car revenir vers elles peut soit nous mener dans une impasse, soit nécessiter un «saut» de plus de 2.

Answer 2

Peut-être que vous pouvez généraliser Gray Codes, qui semblent résoudre un cas particulier du problème.

Answer 3

Cela semble trivial au début mais une fois commencé, c'est difficile! En particulier, les étapes peuvent être 1 ou 2.
Ceci n'est pas une réponse mais plutôt une démos- tration des 10 premiers pas pour une séquence particulière qui, espérons-le, peut aider les autres à visualiser. Sid, s'il vous plaît laissez-moi savoir si ce qui suit est faux:

 
s = No. of steps from the prev corrdinates 
c1 = Condition 1 (x = y = z) 
c2 = Condition 2 (x!= y!= z) 
(x,y,z) s c1 c2 
--------------- 
(0,0,0) * (start) 
(0,0,1) 1 
(0,1,0) 2 
(1,0,0) 2 
(1,0,1) 1 
(1,1,0) 2 
(1,1,1) 1 * 
(2,1,1) 1 
(2,0,1) 1 * 
(2,0,0) 1 
(2,1,0) 1 * 
(2,2,0) 1 
(2,2,1) 1 
(2,2,2) 1 * 
(2,3,2) 1 
(2,3,3) 1 
(3,3,3) 1 * 
(3,3,1) 2 
(3,2,1) 1 * 
(3,2,0) 1 * 
    . 
    . 
    .