约束满足问题学习笔记

发表于

2023.6.27 完成作业时记录的笔记
上传留档

Click to open

CS50’s Introduction to Artificial Intelligence with Python Ep.5 Note

Constraints Satisfaction Problem: 约束满足问题

Constraints

hard / soft constraints: must be satisfied in the solution / preferred in the solution

unary constraint: just involves one single variable

binary constraint: two variables

node consistency: all the elements in the domain satisfies the variable’s unary constraints

  • when dealing with problems, conSsider unary constraints first to reach node consistency, through (for example) removing elements from the domain

arc consistency: satisfy the binary constraints

To max $X$ arc consistent with respect to $Y$, remove elements from $X$’s domain until every choice for $X$ has a possible chice for $Y$

max: some times we can’t reach it from one side

When choosing A.Wed, there’s no remaining choices for B in B’s domain, so remove Wed from A

Algorithm to enforce arc consistency

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def REVISE(csp, X, Y):
    revised = False
    # True if revised else ramain false
    for x in X.domain:
        if no y in Y.domain satisfies constraint of (X, Y):
            delete x from x.domain
            revised = True
    return revised



def AC_3(csp):
    queue = all arcs in csp
    while not queue.empty:
        (X, Y)=dequeue(queue)
        if REVISE(csp, X, Y):
            if X.domain.size==0:
                return False # nothing left in X.domain, so we can't solve the problem
            for Z in X.neighbors-{Y}:
                euqueue(queue, (Z, X))
    return true

Search Problems

csp and search problems

  • initial state: empty assignment
  • actions: add a variable-value pair to assignment
  • transition model: hwo adding an assignment changes the assignment
  • goal test: constraints all satisfied or not
  • path cost function: cost = constant(in this problem)
1
2
3
4
5
6
7
8
9
10
11
def BACKTRACK(assignment, csp):
    # 对于元素选择有要求的的回溯算法
    if assignment completed: return assignment
    var=select-unassigned-var(assignment, csp)
    for value in domain-values(var, assignment, csp):
        if value consistent with assignment:
            add {var=value} to assignment
            result=BACKTRACK(assignment, csp)
            if result!=False: return result
        remove {var=value} from assignment
    return False