文章目录
- 1、新的柱稳定问题
- 2、边界传播器
- THE END
1、新的柱稳定问题
\qquad
给定:可能的垂直龙脉
D
(
X
)
D(X)
D(X)和可能的水平龙脉
D
(
Y
)
D(Y)
D(Y),龙脉只可能存在于整数的位置。
\qquad
问题:找到最大的
D
′
(
X
)
⊆
D
(
X
)
D'(X) \subseteq D(X)
D′(X)⊆D(X)和
D
′
(
Y
)
⊆
D
(
Y
)
D'(Y) \subseteq D(Y)
D′(Y)⊆D(Y),对于
X
=
m
i
n
(
D
′
(
X
)
)
X=min(D'(X))
X=min(D′(X)),存在整数
Y
,
m
i
n
(
D
′
(
Y
)
)
≤
Y
≤
m
a
x
(
D
′
(
Y
)
)
Y, min(D'(Y)) \leq Y \leq max(D'(Y))
Y,min(D′(Y))≤Y≤max(D′(Y)),使得
∣
X
∣
+
∣
Y
∣
=
10
|X|+|Y|=10
∣X∣+∣Y∣=10;同时对于
X
=
m
a
x
(
D
′
(
X
)
)
X=max(D'(X))
X=max(D′(X))也有同样的要求。
2、边界传播器
\qquad
一个边界传播器只检验和改变变量值域的上界和下界,假如某条约束有
n
n
n个变量,则这条约束的边界传播器只需要处理2
n
n
n条信息即可,相对于值域传播器,边界传播器要高效许多。
\qquad
最强的边界传播器:对于约束
C
C
C,最强的边界传播器会检查当前每个变量值域的边界数值(即上下界)是否在
C
C
C的ITA变量的值域的上下界之间能找到整数支持;如果不能,则将这个边界数值移除,由于此处要求的是整数支持,所以也称边界(
Z
Z
Z)相容。
\qquad
下面通过一个例子来说明边界传播器:对于约束
X
=
∣
Y
∣
X=|Y|
X=∣Y∣,它的边界传播器可以如下进行设定:
\qquad
关于约束
X
=
∣
Y
∣
X=|Y|
X=∣Y∣的最强的约束传播器可以如下进行设计:
\qquad
对于一个线性约束调用最强的边界传播器的时间复杂度是
N
P
NP
NP困难的,对于线性不等式调用边界传播器的时间复杂度是线性的。
\qquad
最强的实数边界传播器:对于一个约束
C
C
C,最强的边界实数传播器会检查当前每个变脸值域的边界数值,是否在
C
C
C的其他变量值域的上下界之间能找到实数支持;如果不能,则将这个边界数值移除。边界实数传播器也称边界
R
R
R相容。