2

我有一个二维对象数组。每个对象始终具有一些（可变）分数（即对象在时间t 的分数不一定是对象在时间t+1 的分数）。我想找到最有效的算法，该算法将复制任何得分高于其邻居的对象，并将该副本放入邻居的位置。1

我的第一个冲动是天真的解决方案：

  • 创建数组的副本
  • 将“changeWasMade”标志设置为 false
  • 循环遍历所有位置 p
    • 与所有邻居比较分数 n
    • 如果 score(p) > score(n)，将复制的网格中的 n 替换为 p 的副本并将“changeWasMade”设置为 true
  • 如果“changeWasMade”，则丢弃原来的网格，并重复使用副本作为新的原件；否则，退回副本

但是，对于一个 nxn 数组，这似乎是 O(n 4 ) （n 2次检查的 n 2次可能迭代），这对我来说似乎很慢。由于我的算法知识很差，我认为询问是否有更快的方法来做到这一点是明智的。

更新

我刚刚想到，进行一次“通过”替换可能会更快，然后检查所有新创建的（即克隆的）对象是否具有其邻居的最高分数（即是局部最大值）。如果是，那太好了，发生了正确的事情 - 如果不是，则用得分最高的邻居的副本替换它们。这可能会减少所需的迭代（尽管它需要一些良好的簿记来保持一切正常！） - 还有更快的方法吗？

**脚注**

  1. （在某些情况下，对于那些读过《量子窃贼》的人来说，这是开篇中描述的监狱设置）
4

1 回答 1

3

除非我读错了问题，否则明显的解决方案似乎是：

  1. 创建一个相同大小的空白数组，调用旧数组old和新数组new。
  2. 对于新数组中的每个单元格new[i][j]，将其设置为五个可能值中的最大值：old[i][j]、old[i-1][j]、old[i][j-1]、old[i+1][j]、old[i][j+1]。
  3. new现在是时间步长 t+1 的更新数组。
于 2013-05-21T20:33:21.043 回答