Day 4/23 2020 AI0325

这节课讲的是约束满足问题。
所谓约束满足问题,指的是在若干子集子问题中,求出其中一个满足约束的子问题。
比如假设ABC三个时间的domain(值域)均为{1,2,3};
那么,他们之间还存在着若干约束:{a>b} {b!=c} {c!=a}

那么,显然,a=3 b=2 c=1 就是其中的一个值。

一般要解决这样的问题,我们可以采用搜索+推理的方法来解决。

最暴力(也是最简单)的方法,就是“裸dfs”,逐个试。

在介绍第二种方法之前,需要知道的先验知识是:弧相容。
弧相容的定义是:x->y 若x相容于y,那么对于任意的x,都存在一个y,使得对于序偶(x,y)满足约束。
如果两个变量(或者事件)不符合弧相容,那么一定是x过大,或者是y过小导致的。

那么第二种方法其实就是:DFS+FC(Forward Checking)约束向前传递(不是向后,向后是以前的,向前是未知的)。
大概方法就是:在一步一步执行dfs的操作过程中,再反过来执行一遍check操作使得相邻的事件值域缩减。
第一步A,直接赋值。对A的邻居向前传播约束。第二步在第一步缩小的值域的基础上,对b取值,然后继续向b的邻居向前传播约束。

第三种方法和第二种方法雷同,但是有不同。第三种方法叫做强制约束传播。arc-3

1、初始化:对于所有二元越苏,用2个弧来表示,x-y等价于(x,y)(y,x) 把所有的弧放入Queue.
2、while until queue=空集
若queue不空,从Queue中弹出一个约束(弧),检查弧相容情况
若不相容,(A)删去Domain(x)中,不存在y属于Domain(y),使x->y成立的值。

把约束,z->x加入到queue。

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注