限制式程式設計學習筆記[8] 簡單的不完全求解器

目錄

6 Some incomplete constraint solvers

6.1 A useful lemma

6.2 Equality and disequality constraints

6.3 Boolean constraints

Q: 解釋“‘customise’ the general framework to a specific language”

A: 提示：比如：用hyper-arc consistency能剪掉一些定義域，但是剪了之後的集合不好表示，這就不行。

interval arithmetics就有這類問題，是以最後取了各個區間的凸包。

Q: hyper-arc consistency和domain reduction有何聯系？

A: 回憶上一章内容：reduction（剪枝）分為剪定義域和剪限制，其中利用單個限制剪定義域的最一般情況就是hyper-arc consistency.

hyper-arc consistent CSP不可能再通過單個限制剪任何定義域。

Q: 如何了解“the HYPER-ARC CONSISTENCY rule is the strongest.”

A: 在所有使用單個限制剪定義域的方法中，該規則是最強的（即可以達到理論上最優的定義域縮減效果）

在具體問題中，如果使用其它辦法達到了hyper-arc consistency，那也就是達到某種意義的“最強”“最優”了。

Q: 對于proof system EQU，涉及相等的可以使用集合的交，涉及不等的卻隻考察了\(y=a\)或\(x=a\)的情況，沒有對一般的\(x=y\)情況給出剪枝規則，這為什麼沒有影響其最優性？

A: 這是一個具有誤導性的問題。

注意，\(x\ne y, x\in\{0,1\},y\{1,2\}\)是剪不了的。隻要定義域中至少有2個元素，不等限制就剪不了。

Q: 為什麼說EQU是不完全的？

A: 例如\(x=y,x\ne y\)造成的沖突其無法捕捉到，則closed under the rules時既不成功也不失敗。

回憶：

to bring the initial CSP to some specific, simpler form that usually satisfies some specific local consistency notion.

Q: propositional formula \(x\wedge y\)就是AND constraint嗎？

A: 不是。AND constraint指的是\(x\wedge y = z\)，而propositional formula實際上相當于指定某表達式為1，即\(x\wedge y = 1\).

Q: 通過有限次、equivalence preserving的Preprocess過程，可以得到形式（）

A: 所有限制都形如\(x=y,\neg x=y,x\wedge y=z,x\vee y=z\). 注意其中\(x,y,z\)都是布爾變量，而非一般的布爾表達式。過程中可能引入許多新的變量。

Q: 如何了解“each of these rules can yield a failed CSP”. 明明沒有看到任何\(\perp\)啊？

A: \(x=1\)是定義域，而不是限制。因為1是domain element. 是以如果定義域縮減到空就是fail.

Q: BOOL system在什麼意義下有最優性？

A: 其能達成hyper-arc consistency（暴力讨論可證明），而删除其任意一條規則就不能了。