挑战动态编程问题

Question

这是我需要解决的计算机视觉问题的低调版本.假设给你参数n,q并且必须计算将整数0 ..(q-1)分配给n-by-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大约3小时,任何q,来自作者的估计)

Answer 1

这不是一个答案，只是对讨论的贡献，对于评论来说太长了。

TL; 博士；任何归结为“计算可能性并计算它们”的算法，例如 Eric Lippert 的算法或强力方法都不适用于 @Yaroslav 的目标q <= 100和n <= 18。

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

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

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

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

因此，要更聪明。