CSP过滤
• 15 min read • 2835 words
Tags: CSP
Categories: Introduction to Artificial Intelligence
CSP过滤
1. 相关概念
在约束满足问题中,过滤(Filtering) 是通过约束传播来缩小变量域的技术。过滤的核心思想是在搜索过程中主动推理,提前发现和消除不可能的赋值,从而显著减少搜索空间。
过滤不同于盲目的回溯搜索,它利用约束的结构信息进行局部推理,在赋值之前就排除明显不可行的选择,避免了大量无意义的搜索尝试。
2. 一致性层次
过滤基于不同层次的一致性概念,这些一致性条件越强,过滤效果越好,但计算成本也越高。
节点一致性(Node Consistency)
节点一致性要求每个变量的域都满足所有涉及该变量的一元约束。
对于变量,如果其域中的每个值都满足所有一元约束,则称是节点一致的。
例:如果约束是 X ≠ 红色,那么红色必须从X的域中移除
弧一致性(Arc Consistency)
弧一致性是最重要和最常用的一致性概念。对于约束,如果对于域中的每个值,在的域中都存在至少一个值使得约束得到满足,则称弧是一致的。
形式化定义:
关于弧一致性的详细内容CSP算法章节有详细介绍,这里略去。
4. 前向检查
相关概念
与弧一致性不同,前向检查并不是在搜索前的预处理,而是在搜索过程中、有一个变量被赋值时触发。
前向检查具有局部性。只检查刚刚被赋值的变量的直接邻居,不会产生连锁反应,只能发现由当前赋值直接导致的冲突。
算法实现
def forward_check(self, var: Variable, value: Any,
assignment: Dict[Variable, Any]) -> Optional[Dict[Variable, Set[Any]]]:
"""
Perform forward checking after assigning value to var
Returns dict of removed values or None if inconsistent
"""
removed_values = {}
for constraint in self.csp.constraints:
if constraint.involves_variable(var):
for other_var in constraint.variables:
# Only trigger in assignment
if other_var != var and other_var not in assignment:
to_remove = set()
for other_value in other_var.domain:
test_assignment = assignment.copy()
test_assignment[var] = value
test_assignment[other_var] = other_value
if not constraint.is_satisfied(test_assignment):
to_remove.add(other_value)
if to_remove:
if other_var not in removed_values:
# Memorize what we will do to removed value
removed_values[other_var] = set()
removed_values[other_var].update(to_remove)
other_var.domain -= to_remove
# Check if domain becomes empty
if not other_var.domain:
return None
# Return the record of removed value
return removed_values
5. 弧一致性的维护
在搜索过程中动态维护弧一致性可以获得比单纯前向检查更强的过滤效果。
MAC算法
MAC算法是搜索算法中的一种,当给一个变量赋值时,它会:
- 先调用前项检查,检查变量邻近值的可行性。
- 然后调用弧一致性检查,使用ac3算法检查弧一致性。
class MaintainingArcConsistency(ConsistencyFilter):
"""MAC (Maintaining Arc Consistency) algorithm"""
def __init__(self, csp: 'CSPWithFiltering'):
super().__init__(csp)
self.ac_filter = ArcConsistencyFilter(csp)
def propagate_assignment(self, var: Variable, value: Any) -> bool:
"""
Propagate assignment and maintain arc consistency
Returns False if inconsistency detected
"""
# Remove inconsistent values from assigned variable
var.domain = {value}
# Remove inconsistent values from neighbors
for constraint in self.csp.constraints:
if constraint.involves_variable(var):
for other_var in constraint.variables:
if other_var != var:
to_remove = set()
for other_value in other_var.domain:
assignment = {var: value, other_var: other_value}
if not constraint.is_satisfied(assignment):
to_remove.add(other_value)
other_var.domain -= to_remove
if not other_var.domain:
return False
# Maintain arc consistency
return self.ac_filter.ac3()
6. 更强的一致性
路径一致性(Path Consistency)
路径一致性要求对于任意两个变量和的值组合,都存在中间变量的值,使得约束和都得到满足。
路径一致性算法PC-2算法类似于AC-3,但处理的是三元组:
def pc2(self) -> bool:
"""
PC-2 algorithm implementation
Returns False if inconsistency detected
"""
queue = deque()
# Initialize queue with all variable triples
variables = self.csp.variables
for i, xi in enumerate(variables):
for j, xj in enumerate(variables):
if i != j:
for k, xk in enumerate(variables):
if k != i and k != j:
queue.append((xi, xj, xk))
while queue:
xi, xj, xk = queue.popleft()
if self.revise_path_consistency(xi, xj, xk):
if not self.has_consistent_pairs(xi, xj):
return False
# Add related triples back to queue
self.add_related_triples(queue, xi, xj, xk)
return True
def revise_path_consistency(self, xi: Variable, xj: Variable, xk: Variable) -> bool:
"""Revise path consistency for triple (xi, xj, xk)"""
revised = False
to_remove = []
# Check all value pairs for xi and xj
for x in xi.domain:
for y in xj.domain:
# Check if there exists a supporting value in xk
has_support = False
for z in xk.domain:
assignment = {xi: x, xj: y, xk: z}
if self.satisfies_path_constraints(xi, xj, xk, assignment):
has_support = True
break
if not has_support:
to_remove.append((x, y))
revised = True
# Remove unsupported pairs (simplified - actual implementation
# would need to maintain explicit constraint relations)
return revised
k-一致性
k-一致性是一致性概念的推广:如果任意个变量的一致赋值都可以扩展为包含第k个变量的一致赋值,则CSP是k-一致的。
- 1-一致性 = 节点一致性
- 2-一致性 = 弧一致性
- 3-一致性 = 路径一致性
7. 过滤与搜索的结合
智能回溯
可以将过滤算法应用到回溯算法中,让回溯更加智能:
def intelligent_backtrack(self, assignment: Optional[Dict[Variable, Any]] = None) -> Optional[Dict[Variable, Any]]:
"""Intelligent backtracking with filtering"""
if assignment is None:
assignment = {}
# Apply constraint propagation
if not self.arc_filter.ac3():
return None
# Check if solved by propagation alone
if all(len(var.domain) == 1 for var in self.variables):
return {var: next(iter(var.domain)) for var in self.variables}
if self.is_complete(assignment):
return assignment
# Select variable using heuristics
var = self.select_variable(assignment)
if var is None:
return assignment
# Try each value in domain
for value in self.order_values(var, assignment):
assignment[var] = value
# Save state for backtracking
saved_state = self.arc_filter.save_state()
# Apply MAC
if self.mac_filter.propagate_assignment(var, value):
result = self.intelligent_backtrack(assignment)
if result is not None:
return result
# Restore state and backtrack
self.arc_filter.restore_state(saved_state)
del assignment[var]
return None