遍历三维坐标的算法，避免重复访问

Question

遍历三维坐标的算法，避免重复访问

3

假设我们有一组从(0,0,0)到(100,100,100)的三维（整数）坐标。我们希望访问每个可能的坐标（共有100^3个可能的坐标要访问），但不能重复访问任何一个坐标。

相邻步骤中每个坐标之间的差异总和不能超过2（如果不可能，则最小化）。例如，从(0,2,1)到(2,0,0)的步骤的总差异为5，因为|x1-x2|+|y1-y2|+|z1-z2|=5。

我们如何生成这样一系列坐标？

例如，开始时： (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) 等等...

有没有人知道一种算法，可以生成到任意坐标(x,y,z)的这样一个序列，其中x=y=z，或者能够证明这样的算法不存在？谢谢！

额外加分题：展示如何生成具有x!=y!=z的这样一个序列:D

- Sid Ayden

3个回答

0

也许你可以将格雷码泛化，它似乎解决了问题的一个特殊情况。

- Yuval F

0

一开始看起来很简单，但一旦开始就会变得棘手！特别是步骤可能是1或2。
这不是一个答案，而是对特定序列的前10多个步骤的演示，希望能帮助其他人进行可视化。Sid，请告诉我以下内容是否有误：

s = 上一个坐标到当前坐标的步数 c1 = 条件1 (x = y = z) c2 = 条件2 (x!= y!= z) (x,y,z) s c1 c2 --------------- (0,0,0) * (起点) (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 * . . .

- o.k.w

嗯，我不确定那会不会行，因为你漏掉了一些坐标（例如0,1,1），而且我不知道是否可能在之后返回以到达它们，但是是的，这就是那种想法。 - Sid Ayden

@Sid：我知道我错过了一些坐标，这就是我想要强调的问题。但在另一个序列中，我可以像mjv一样总是使用步长为1。即使使用步长=1，更不用说2，从一个点到另一个点有很多可能的序列。 - o.k.w

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mjv · Accepted Answer

其中一个技巧（还有其他方法）是一次处理一行 [段落]，一个平面 [正方形]。回答问题的最后一部分，即使每个维度中访问的大小不同，也可以使用此方法（例如：100 x 6 x 33块）。换句话说：

从（0,0,0）开始，
只在Z轴上移动到段落结束，即
（0,0,1），（0,0,2），（0,0,3），...（0,0,100），
然后移动到下一行，即
（0,1,100）
并向后在该行上移动，即
（0,1,99），（0,1,98），（0,1,97），...（0,1,0），
接下来移到下一行，“前进”
并重复直到整个“面板被涂满”，最后以以下方式结束：
…（0,100,99），（0,100,100），
然后沿X轴移动1格
（1,100,100）
并在另一面板上重复，但在此面板上向“上”移动
等等。

基本上，每次移动都是在单个维度上完成的，恰好为1个。这有点像在101 x 101 x 101建筑物中从房间到房间“步行”，其中每个房间可以直接通往其周围相邻的房间（即不对角线连接）。

在编程语言中实现这种逻辑很简单！唯一稍微具有挑战性的部分是处理“来回”，即在某些情况下，某些维度中的某些更改是正数，而在其他情况下则为负数。

编辑：（有关同时对角线进行相同操作的Sid问题）：
是的！这是完全可能的，因为问题说明我们可以具有距离为2的[曼哈顿]距离，这是对角线所需的距离。
路径类似于上面列出的路径，即按行执行，来回移动（只有这里的线长度可变），然后移动到第三个维度上的下一个“面板”，并重复操作，只是向上移动等等。

(0,0,0) (0,0,1)
(0,1,0)                  第一条对角线，只有1个长度。
(0,2,0)                  “转身”
(0,1,1) (0,0,2)          第二条对角线：长度为2
(0,0,3)                  “转身”
(0,1,2) (0,2,1) (0,3,0)  第三条对角线：长度为3
(0,4,0)                  转身
依此类推。

在it技术方面，确实有可能混合使用这些方法，可以完全按“面板”来混搭，例如先对角线，再水平排列，也可以在给定的面板内混合使用，例如开始时对角线排列，但当到达顶部时，继续使用水平模式，在“左”侧循环时提前停止一点，因为对角线已经处理了该侧的一部分。
有效地说，这使得 整个空间 "上色" 的方式可以相当多（但显然是有限的）。关键是要避免留下（过多的）未涂色的相邻区域，因为回到它们可能会导致我们陷入死胡同，或者需要跳跃超过2个步长。