23

这是我需要解决的计算机视觉问题的简化版本。假设您有参数 n,q 并且必须计算将整数 0..(q-1) 分配给 n×n 网格的元素的方式的数量，以便对于每个分配，以下都是正确的

  1. 没有两个邻居（水平或垂直）获得相同的值。
  2. 位置 (i,j) 的值为 0
  3. 位置 (k,l) 的值为 0

由于 (i,j,k,l) 没有给出，输出应该是上面的评估数组，对于 (i,j,k,l) 的每个有效设置一个

下面是蛮力方法。目标是获得一种适用于 q<=100 和 n<=18 的有效算法。

def tuples(n,q):
  return [[a,]+b for a in range(q) for b in tuples(n-1,q)] if n>1 else [[a] for a in range(q)]

def isvalid(t,n):
  grid=[t[n*i:n*(i+1)] for i in range(n)];
  for r in range(n):
    for c in range(n):
      v=grid[r][c]
      left=grid[r][c-1] if c>0 else -1
      right=grid[r][c-1] if c<n-1 else -1
      top=grid[r-1][c] if r > 0 else -1
      bottom=grid[r+1][c] if r < n-1 else -1
      if v==left or v==right or v==top or v==bottom:
        return False
  return True

def count(n,q):
  result=[]
  for pos1 in range(n**2):
    for pos2 in range(n**2):
      total=0
      for t in tuples(n**2,q):
        if t[pos1]==0 and t[pos2]==0 and isvalid(t,n):
          total+=1

      result.append(total)

  return result

assert count(2,2)==[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1]

更新 11/11 我也在 TopCoder论坛上问过这个问题，他们的解决方案是迄今为止我见过的最有效的解决方案（根据作者的估计，n = 10，任何 q 大约需要 3 小时）

4

6 回答 6

3

Maybe this sounds too simple, but it works. Randomly distribute values to all the cells until only two are empty. Test for adjacency of all values. Compute the average the percent of successful casts vs. all casts until the variance drops to within an acceptable margin.

The risk goes to zero and the that which is at risk is only a little runtime.

于 2010-11-10T21:53:57.607 回答
2

这不是答案，只是对讨论的贡献，评论太长了。

tl; 博士；任何归结为“计算可能性并计算可能性”的算法（例如 Eric Lippert 的或蛮力方法）都不适用于 @Yaroslav 的q <= 100and目标n <= 18。

让我们首先考虑一个n x 1列。这一列有多少个有效编号？对于第一个单元格，我们可以在q数字之间进行选择。由于我们不能垂直重复，我们可以q - 1在第二个单元格的数字之间进行选择，因此q - 1在第三个单元格的数字之间进行选择，依此类推。因为这意味着存在非常粗略的有效q == 100着色。n == 18q * (q - 1) ^ (n - 1) = 100 * 99 ^ 1710 ^ 36

现在考虑由缓冲列（称为芥末列）分隔的任何两个有效列（称为面包列）。这是一个简单的算法，可以在 时为芥末列找到一组有效的值q >= 4。从芥末列的顶部单元格开始。我们只需要担心面包列的相邻单元格最多有 2 个唯一值。为芥末列选择任何第三个数字。考虑芥末列的第二个单元格。我们必须考虑前一个芥末细胞和两个相邻的面包细胞，总共最多有 3 个唯一值。选择第 4 个值。继续填写芥末栏。

我们最多有 2 列包含硬编码单元格 0。使用芥末列，因此我们可以制作至少 6 个面包列，每个列都有大约10 ^ 36解决方案，总共至少有10 ^ 216有效的解决方案，给或取一个数量级的舍入错误。

根据维基百科，有关于10 ^ 80宇宙中的原子。

因此，要聪明一点。

于 2010-11-10T19:21:39.730 回答
1

更新 11/11 我也在 TopCoder 论坛上问过这个问题，他们的解决方案是迄今为止我见过的最有效的解决方案（根据作者的估计，n = 10，任何 q 大约需要 41 小时）

我是作者。不是 41，只有 3 个令人尴尬的可并行 CPU 小时。我计算了对称性。对于 n=10，只有 675 个真正不同的 (i,j) 和 (k,l) 对。我的程序每个需要约 16 秒。

于 2010-11-12T08:58:01.853 回答
0

一些可能对其他回答者也有帮助的观察结果：

  1. 值 1..q 是可以互换的——它们可以是字母，结果是一样的。
  2. 没有邻居匹配的约束是一个非常温和的约束，因此蛮力方法将过于昂贵。即使您知道除了一个单元格之外的所有值，对于 q>8，仍然存在至少 q-8 个可能性。
  3. 这个输出会很长——每组 i,j,k,l 都需要一行。组合的数量类似于 n 2 (n 2 -3)，因为两个固定零可以在任何地方，除了彼此相邻，除非它们不需要遵守第一条规则。对于 n=100 和 q=18，最大困难的情况，这是 ~ 100 4 = 1 亿。因此，这是您的最低复杂性，并且由于目前的问题是不可避免的。
  4. 有一些简单的情况——当 q=2 时，有两个可能的棋盘，所以对于任何给定的零对，答案都是 1。

第 3 点使整个程序 O(n 2 (n 2 -3) ) 成为最小值，并且还建议您需要对每对零进行合理有效的处理，因为简单地编写 1 亿行而不进行任何计算将需要一段时间。作为参考，以每行 1 秒计算，即 1x10 8 s ~ 3 年，或 12 芯盒子上的 3 个月。

我怀疑给定一对零会有一个优雅的答案，但我不确定是否有一个分析解决方案。鉴于您可以根据零的位置使用 2 或 3 种颜色来完成，您可以将地图分成一系列区域，每个区域仅使用 2 或 3 种颜色，然后它只是不同组合的数量2 或 3 中的 q（qC2 或 qC3）为每个区域乘以区域数，乘以分割地图的方式数。

于 2010-11-11T06:38:07.160 回答
0

我不是数学家，但我突然想到这个问题应该有一个解析解，即：

首先，现在计算具有 Q 颜色的 NxN 板可能有许多不同的颜色（包括那些邻居，定义为具有共同的边缘不会得到相同的颜色）。这应该是一个非常简单的公式。

然后算出这些解中有多少在 (i,j) 中有 0，这应该是 1/Q 的分数。

然后根据曼哈顿距离 |ik|+|jl| 以及到棋盘边缘的距离和这些距离的“奇偶性”，如可被 2 整除的距离，计算出有多少剩余解决方案在 (k,l) 中为 0，能被 3 整除，能被 Q 整除。

最后一部分是最难的，虽然我认为如果你真的擅长数学，它仍然是可行的。

于 2012-06-12T16:10:54.633 回答
0

我正在根据 Dave Aaron Smith 对讨论的贡献进行贡献。

我们暂时不考虑最后两个约束（(i,j)和(k,l)）。

只有一列 (nx1) 的解决方案是q * (q - 1) ^ (n - 1).

第二列有多少选择？(q-1)对于顶部单元格（1,2），但如果（1,2）/（2,1）具有或不同的颜色，则对于单元格（2,2）q-1。q-2

(3,2) 也一样：q-1或q-2解决方案。

我们可以看到我们有一个可能性二叉树，我们需要对该树求和。让我们假设左孩子总是“顶部和左边的颜色相同”，而右孩子是“不同的颜色”。

通过在树上计算左列创建此类配置的可能性数量以及我们正在着色的新单元格的可能性数量，我们将计算为两列着色的可能性数量。

但是现在让我们考虑第二列着色的概率分布：如果我们想要迭代该过程，我们需要在第二列上具有均匀分布，这就像第一个不存在并且在所有着色中前两列我们可以说1/q它们在第二列的顶部单元格中具有颜色 0。

没有均匀分布是不可能的。

问题：分布是否均匀？

答案： 我们可以通过首先构建第二列，然后是第一列然后是第三列来获得相同数量的解决方案。在这种情况下，第二列的分布是均匀的，所以在第一种情况下也是如此。

我们现在可以应用相同的“树的想法”来计算第三列的可能性数量。

我将尝试在此基础上进行开发并建立一个通用公式（因为树的大小为 2^n，我们不想明确地探索它）。

于 2010-11-10T22:00:47.113 回答