具有挑战性的动态规划问题

23 投票

6 回答

2881 浏览

数据工程师

提问于 2025-04-16 06:48

这是一个简化版的计算机视觉问题，我需要解决。假设你有参数 n 和 q，需要计算将整数 0 到 (q-1) 分配给 n 乘 n 的网格中元素的方式，要求每种分配都满足以下条件：

相邻的元素（水平或垂直）不能有相同的值。
位置 (i,j) 的值必须是 0。
位置 (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 小时）。

算法优化计算机视觉动态规划暴力破解网格分配相邻元素约束整数分配 TopCoder

6 个回答

更新于11月11日：我在TopCoder论坛上也问过这个问题，他们提供的解决方案是我见过的最有效的（对于n=10，任何q，作者的估计大约需要41小时）。

我是作者。其实不是41小时，只需要3个可怕的并行计算小时。我已经计算了对称性。对于n=10，实际上只有675对（i,j）和（k,l）是完全不同的。我的程序每对大约需要16秒。

回答于 2025-04-16 由 Python大师

分享举报

这不是一个答案，只是对讨论的补充，内容太长不适合放在评论里。

简单来说，任何一种算法如果只是“计算可能性并进行计数”，比如Eric Lippert的方法或暴力破解的方法，都不适合@Yaroslav的目标，即q <= 100和n <= 18。

首先，我们来想想一个单独的n x 1列。这一列有多少种有效的编号方式呢？对于第一个单元格，我们可以从q个数字中选择。由于不能在垂直方向上重复，所以第二个单元格只能从q - 1个数字中选择，第三个单元格也是如此，依此类推。对于q == 100和n == 18，这意味着有效的着色方式有q * (q - 1) ^ (n - 1) = 100 * 99 ^ 17，大约是10 ^ 36。

现在考虑两个有效的列（我们称它们为“面包列”），它们之间有一个缓冲列（我们称它为“芥末列”）。这里有一个简单的算法来找到芥末列的有效值，当q >= 4时。我们从芥末列的顶部单元格开始。我们只需要关注面包列的相邻单元格，这些单元格最多有2个不同的值。为芥末列选择任何第三个数字。考虑芥末列的第二个单元格。我们必须考虑前一个芥末单元格和2个相邻的面包单元格，总共最多有3个不同的值。选择第4个值。继续填充芥末列。

我们最多有2列包含一个硬编码的0单元格。通过使用芥末列，我们可以至少创建6个面包列，每个列大约有10 ^ 36种解决方案，总共至少有10 ^ 216种有效解决方案，可能会因为四舍五入的误差而有所不同。

根据维基百科，宇宙中大约有10 ^ 80个原子。

所以，要更聪明一些。

回答于 2025-04-16 由 Python大师

分享举报

这听起来可能太简单了，但确实有效。你可以随机把数值分配到所有的单元格，直到只剩下两个是空的。然后检查所有数值之间是否相邻。接着计算成功的尝试次数和总尝试次数的平均值，直到这个平均值的波动范围降到一个可以接受的水平。

这样做的风险几乎为零，真正有风险的只是稍微增加了一点运行时间。

回答于 2025-04-16 由 Python大师

分享举报

具有挑战性的动态规划问题

6 个回答

撰写回答