一次访问二维数组的每个元素的最低效算法
Most inefficient algorithm to visit each elements of a 2d array once
我正在创建全景图像，为此我使用了一个相机，我通过编程逐步移动它。图像是逐行捕获的。
所以基本上捕获可以看作是某种二维数组：
[ 0, 1, 2, 3 ] # row 1
[ 4, 5, 6, 7 ] # row 2
摄像机在数字中依次移动。
我注意到，如果一辆车在镜头前移动，并且与镜头保持相同的速度，那么每张照片都会出现这辆车，全景看起来很奇怪。
所以，我有了以下想法：以非连续的顺序移动相机，这样汽车很可能只被拍摄一次。然后我想到了如何以相机在每个位置之间移动最多的方式捕捉图像。
我找到了单行全景图的方法。基本上它从头开始，向右跳到一半，向左跳到一半减 1，然后重复。
示例如下：
# 1x5 --> [0, 2, 4, 1, 3] # sequential indices: 0 3 1 4 2
# 1x6 --> [0, 2, 4, 1, 3, 5] # sequential indices: 0 3 1 4 2 5
# 1x7 --> [0, 2, 4, 6, 1, 3, 5] # sequential indices: 0 4 1 5 2 6 3
# 1x8 --> [0, 2, 4, 6, 1, 3, 5, 7] # sequential indices: 0 4 1 5 2 6 3 7
明确地说，这意味着对于 1x6 (0, 2, 4, 1, 3, 5) 相机移动如下：
x----- # pos 1
---x-- # pos 2
-x---- # pos 3
----x- # pos 4
--x--- # pos 5
-----x # pos 6
所以基本上它一直跳跃至少 n/2，这看起来是最佳的，因为没有捕获最终成为另一个捕获的邻居，并且捕获之间的距离看起来最大化并且波动很小。
我使用的简化代码是这样的：
def index_for(n, cols)
col = n % cols
if n.even?
col/2
else
(col / 2.0).ceil + (cols / 2.0).ceil - 1
end
end
# Sequential indices [0, 4, 1, 5, 2, 6, 3]
seq = (0..6).map{ |i| index_for(i, 7) }
# Visualization [0, 2, 4, 6, 1, 3, 5]
(0..6).map{ |i| seq.index(i) }
我尝试让它与多行一起工作，几乎达到了目标但后来放弃了。以下是我的想法示例：
# 3x4
[0, 2, 9, 11]
[4, 6, 1, 3]
[8, 10, 5, 7]
# 2x5
[0, 2, 5, 7, 9]
[4, 6, 8, 1, 3]
如果你看一下数字，我们会发现左边通常只是偶数，右边是奇数但以模数方式移动。这种奇数的移动很难算法化，因为逻辑会根据 rows/cols 为 even/odd.
而略有变化
目前我忽略了这些行，只是对每一行重新应用了相同的算法。这意味着 2x5 是这样完成的：
[0, 2, 4, 1, 3]
[5, 7, 9, 6, 8]
所以，这是我的问题：
- 用多行实现我想要的最佳算法是什么？我读到 https://en.wikipedia.org/wiki/Longest_path_problem 并且我认为可以构建一个图形，其中网格的所有节点之间都存在路径，并且每条边的权重将是节点之间的距离。这听起来很复杂而且不容易编写代码。
- 申请多行的simplest/most实用算法是什么？我同意 "good-enough" 解决方案（网格的尺寸应保持在 1x3 到 3x9 之间）。我不想要基于随机性的解决方案，因为我希望每次捕获全景图时捕获总是以相同的顺序发生。
编辑：附加信息：汽车通常移动缓慢（以连续捕获的速度），因此在周围跳跃是避免重复的好方法。如果汽车正好以摄像机的速度移动（这发生了），那么在 2-3 个方块中看到汽车比在其中 7 个方块中看到汽车更好。全景图通常在180°左右，但应该支持360°。每次图像捕获之间有大约 3 秒的停顿。全景图主要是捕捉巨型建筑工地（建筑物）的施工情况，但有时会有汽车或人走在建筑物前。我们不关心移动部件，目标是捕捉建筑物并尽量减少 person/car 对全景图进行轰炸。
我不相信最大化相机的移动距离会使汽车只出现一次。这辆车更有可能出现在多个 non-successive 帧中。这看起来也很奇怪。但值得一试。
一种简单的测试方法是将二维数组表示为一维数组，进行置乱，然后将其映射回二维。例如，这个二维数组：
[ 1, 2, 3, 4, 5]
[ 6, 7, 8, 9,10]
[11,12,13,14,15]
变成[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
现在您可以使用您的一维算法调整顺序，然后将其映射回二维。
我怀疑，与其正好走一半，不如选择一个不是宽度或高度的约数的质数。
另一种可能性是使用 Fisher-Yates 洗牌随机化单元格。这很容易做到，而且在实践中可以很好地消除汽车，就像确定性加扰算法一样。
好的，我找到了每行更简单的公式：
代码变得微不足道：
def index_for(n, cols)
(n + cols * (n % 2)) / 2
end
(0..7).map{ |i| index_for(i, 8) }
=> [0, 4, 1, 5, 2, 6, 3, 7]
所以，现在我将只对每一行使用它。我会等一会儿，以防有人对我的问题提出更好的答案。
我正在创建全景图像，为此我使用了一个相机，我通过编程逐步移动它。图像是逐行捕获的。
所以基本上捕获可以看作是某种二维数组：
[ 0, 1, 2, 3 ] # row 1
[ 4, 5, 6, 7 ] # row 2
摄像机在数字中依次移动。
我注意到，如果一辆车在镜头前移动，并且与镜头保持相同的速度，那么每张照片都会出现这辆车，全景看起来很奇怪。
所以，我有了以下想法：以非连续的顺序移动相机，这样汽车很可能只被拍摄一次。然后我想到了如何以相机在每个位置之间移动最多的方式捕捉图像。
我找到了单行全景图的方法。基本上它从头开始，向右跳到一半，向左跳到一半减 1，然后重复。
示例如下：
# 1x5 --> [0, 2, 4, 1, 3] # sequential indices: 0 3 1 4 2
# 1x6 --> [0, 2, 4, 1, 3, 5] # sequential indices: 0 3 1 4 2 5
# 1x7 --> [0, 2, 4, 6, 1, 3, 5] # sequential indices: 0 4 1 5 2 6 3
# 1x8 --> [0, 2, 4, 6, 1, 3, 5, 7] # sequential indices: 0 4 1 5 2 6 3 7
明确地说，这意味着对于 1x6 (0, 2, 4, 1, 3, 5) 相机移动如下：
x----- # pos 1
---x-- # pos 2
-x---- # pos 3
----x- # pos 4
--x--- # pos 5
-----x # pos 6
所以基本上它一直跳跃至少 n/2，这看起来是最佳的，因为没有捕获最终成为另一个捕获的邻居，并且捕获之间的距离看起来最大化并且波动很小。
我使用的简化代码是这样的：
def index_for(n, cols)
col = n % cols
if n.even?
col/2
else
(col / 2.0).ceil + (cols / 2.0).ceil - 1
end
end
# Sequential indices [0, 4, 1, 5, 2, 6, 3]
seq = (0..6).map{ |i| index_for(i, 7) }
# Visualization [0, 2, 4, 6, 1, 3, 5]
(0..6).map{ |i| seq.index(i) }
我尝试让它与多行一起工作，几乎达到了目标但后来放弃了。以下是我的想法示例：
# 3x4
[0, 2, 9, 11]
[4, 6, 1, 3]
[8, 10, 5, 7]
# 2x5
[0, 2, 5, 7, 9]
[4, 6, 8, 1, 3]
如果你看一下数字，我们会发现左边通常只是偶数，右边是奇数但以模数方式移动。这种奇数的移动很难算法化，因为逻辑会根据 rows/cols 为 even/odd.
而略有变化目前我忽略了这些行，只是对每一行重新应用了相同的算法。这意味着 2x5 是这样完成的：
[0, 2, 4, 1, 3]
[5, 7, 9, 6, 8]
所以，这是我的问题：
- 用多行实现我想要的最佳算法是什么？我读到 https://en.wikipedia.org/wiki/Longest_path_problem 并且我认为可以构建一个图形，其中网格的所有节点之间都存在路径，并且每条边的权重将是节点之间的距离。这听起来很复杂而且不容易编写代码。
- 申请多行的simplest/most实用算法是什么？我同意 "good-enough" 解决方案（网格的尺寸应保持在 1x3 到 3x9 之间）。我不想要基于随机性的解决方案，因为我希望每次捕获全景图时捕获总是以相同的顺序发生。
编辑：附加信息：汽车通常移动缓慢（以连续捕获的速度），因此在周围跳跃是避免重复的好方法。如果汽车正好以摄像机的速度移动（这发生了），那么在 2-3 个方块中看到汽车比在其中 7 个方块中看到汽车更好。全景图通常在180°左右，但应该支持360°。每次图像捕获之间有大约 3 秒的停顿。全景图主要是捕捉巨型建筑工地（建筑物）的施工情况，但有时会有汽车或人走在建筑物前。我们不关心移动部件，目标是捕捉建筑物并尽量减少 person/car 对全景图进行轰炸。
我不相信最大化相机的移动距离会使汽车只出现一次。这辆车更有可能出现在多个 non-successive 帧中。这看起来也很奇怪。但值得一试。
一种简单的测试方法是将二维数组表示为一维数组，进行置乱，然后将其映射回二维。例如，这个二维数组：
[ 1, 2, 3, 4, 5]
[ 6, 7, 8, 9,10]
[11,12,13,14,15]
变成[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
现在您可以使用您的一维算法调整顺序，然后将其映射回二维。
我怀疑，与其正好走一半，不如选择一个不是宽度或高度的约数的质数。
另一种可能性是使用 Fisher-Yates 洗牌随机化单元格。这很容易做到，而且在实践中可以很好地消除汽车，就像确定性加扰算法一样。
好的，我找到了每行更简单的公式：
代码变得微不足道：
def index_for(n, cols)
(n + cols * (n % 2)) / 2
end
(0..7).map{ |i| index_for(i, 8) }
=> [0, 4, 1, 5, 2, 6, 3, 7]
所以，现在我将只对每一行使用它。我会等一会儿，以防有人对我的问题提出更好的答案。