2020-07-27【Math】约束编程学习

作者: 持刀的要迟到了 | 来源:发表于2020-08-10 14:31 被阅读0次

文章的例子中，通过求解数独，介绍约束編程。

image.png

定义问题的变量，定义域：
为每个空方块创建一个变量，对于每个变量，定义域。
域：{1，2，3，4}

但是，复杂数独，不能直接通过简单的域值排除，获得这个结果

所以让计算机猜测，猜测后看有没有被排除为空的域，如果有，那么本次猜测失败。

如果猜测失败，使用回溯。
首先恢复到猜测之前的状态，然后从域中删除猜测错误的值。

一次又一次的猜测与回溯，得到最终结果。

WFC波函数折叠（Wave Function Collapse）

是一个扭曲的约束问题-有成千上万可能的解决方案。如果我们随机猜测，而不是得到一个解算器，我们得到一个生成器。该生成器依然遵循我们指定的所有禁忌，从而使它比许多其他程序更具可控性。

在 WFC 中，目标是用切片填充网格，以便附近的切片相互连接。在上面使用的术语中，每个磁贴都是一个不同的值，网格中的每个单元格都是表示切片选择的变量。以及有关哪些磁贴可以放置在约束位置的规则。

Maxim 发现，通过合理的切片选择和合理的随机化例程，很少需要回溯，以便我们可以跳过实现它。这意味着 WFC 算法在最基本的方面如下所示：

对于每个网格，创建一个boo[] 代表此变量的域。域的每个tile都有一个entry(?.?)，他们都会被初始化为true。如果entry是true，则tile在域中。
使用“最小熵”启发式选择一个随机的单元格。
从该单元格域中随机选择一个tile，把其他的tile从域中移除
根据这个新的信息，更新其他单元格中的域，即繁殖单元格。这需要反复的进行，因为这些单元格的改变可能有进一步的影响。