CS50 Introduction to Artificial Intelligence with Python Lecture 4
第四讲的主题是Optimization，这里总结第四讲以及第四次作业。
课程地址：https://cs50.harvard.edu/ai/
备注：图片均来自课程课件。
Optimization
从选择集合内选择最佳选择。
Hill Climbing
爬山法的思路是查看当前状态的相邻节点，如果比当前状态更好，则将当前状态更新为相邻节点，否则直接返回当前节点；伪代码如下：
function HILL-CLIMB(problem):
current = initial state of problem
repeat:
neighbor = highest valued neighbor of current
if neighbor not better than current:
return current
current = neighborHill Climbing Variants
| 变量 | 定义 |
|---|---|
| steepest-ascent | 选择价值最高的邻居 |
| stochastic | 从较高价值的邻居中随机选择 |
| first-choice | 选择第一个高价值邻居 |
| random-restart | 进行多次爬山 |
| local beam search | 选择$k$个价值最高的邻居 |
Simulated Annealing(模拟退火)
- 早期，较高的“温度”：更可能接受比当前状态更差的邻居
- 之后，降低“温度”：接受比当前状态更差的邻居的可能性较小
伪代码如下：
function SIMULATED-ANNEALING(problem, max):
current = initial state of problem
for t = 1 to max:
T = TEMPERATURE(t)
neighbor = random neighbor of current
ΔE = how much better neighbor is than current
if ΔE > 0:
current = neighbor
with probability e^(ΔE/T) set current = neighbor
return currentLinear Programming
- 最小化目标函数$\mathbf{c}_{1} \mathbf{x}_{1}+\mathbf{c}_{2} \mathbf{x}_{2}+\ldots+\mathbf{c}_{\mathbf{n}} \mathbf{x}_{\mathbf{n}}$
- 约束为$\mathbf{a}_{1} \mathbf{x}_{1}+\mathbf{a}_{2} \mathbf{x}_{2}+\ldots+\mathbf{a}_{\mathbf{n}} \mathbf{x}_{\mathbf{n}} \leq \mathbf{b}$
解决方法一般有两种：
- 单纯形
- 内点法
这里主要介绍了如何使用相应的库函数，没有介绍具体原理。
Constraint Satisfaction
考虑安排考试日期的问题：
这里规定一个人不能在同一天安排两门考试，将上述关系用图表示，其中节点表示课程考试，两个节点相邻表示对应的课程考试不能安排在同一天：
Constraint Satisfaction Problem
- 变量集合$\left\{\mathrm{X}_{1}, \mathrm{X}_{2}, \ldots, \mathrm{X}_{\mathrm{n}}\right\}$
- 每个变量的可选集$\left\{\mathrm{D}_{1}, \mathrm{D}_{2}, \ldots, \mathrm{D}_{\mathrm{n}}\right\}$
- 约束集合$\mathbf{C}$
具体例子如下：
hard constraints and soft constraints
- hard constraints：必须满足的约束
- soft constraints：表达了一些概念，即哪些解比其他解更好
unary constraint and binary constraint
- unary constraint：$\{A \neq M o n d a y\}$
- binary constraint：$\{A \neq B\}$
node consistency
当变量域中的所有值都满足变量的一元约束时称为node consistency
arc consistency
当变量域中的所有值都满足变量的二元约束时称为arc consistency。
为了使$X$与$Y$保持arc consistency，从$X$的域中删除元素，直到$X$的每个选择都可以选择$Y$的域中某个元素。
伪代码如下：
function REVISE(csp, X, Y):
revised = false
for x in X.domain:
if no y in Y.domain satisfies constraint for (X, Y):
delete x from X.domain
revised = true
return revised上述代码是对$X,Y$操作，使其满足arc consistency，并且如果我们进行了修改则返回True，否则返回False。
完整图上的算法如下：
function AC-3(csp):
queue = all arcs in csp
while queue non-empty:
(X, Y) = DEQUEUE(queue)
if REVISE(csp, X, Y):
if size of X.domain == 0:
return false
for each Z in X.neighbors - {Y}:
ENQUEUE(queue, (Z, X))
return true其中
for each Z in X.neighbors - {Y}:
ENQUEUE(queue, (Z, X))是因为对X做了修改，所以要对其邻居重新进行操作。
CSPs as Search Problems
- 初始状态：empty assignment（无变量）
- 操作：给assignment添加$\{\text {variable}=\text {value}\}$
- 转移模型：显示添加assignment如何更改assignment
- 目标测试：检查所有分配的变量是否都满足约束
- 路径成本函数：所有路径具有相同的成本
Backtracking Search
可以利用回溯法进行搜索，找到满足约束的分配。
function BACKTRACK(assignment, csp):
if assignment complete: 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 ≠ failure: return result
remove {var = value} from assignment
return failure可以将推理和回溯法结合，得到如下算法：
function BACKTRACK(assignment, csp):
if assignment complete: 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
inferences = INFERENCE(assignment, csp)
if inferences ≠ failure: add inferences to assignment
result = BACKTRACK(assignment, csp)
if result ≠ failure: return result
remove {var = value} and inferences from assignment
return failure这里和回溯法的区别是一边搜索一边推理，可以提高效率。
SELECT-UNASSIGNED-VAR
- 最小剩余值（MRV）启发式选择：选择具有最小域的变量
- 度启发式选择：选择度最高的变量
DOMAIN-VALUES
- 最小约束值启发式：
- 首先尝试约束最少的变量
以下图为例
对于节点C，应该选择Wed，因为选择Wed只会影响2个节点，而Tue会影响3个。
Project
Crossword
该项目是填字游戏，基本上就是实现课程中的全部算法：
def enforce_node_consistency(self):
"""
Update `self.domains` such that each variable is node-consistent.
(Remove any values that are inconsistent with a variable's unary
constraints; in this case, the length of the word.)
"""
for var in self.domains:
words = self.domains[var].copy()
for word in words:
if len(word) != var.length:
self.domains[var].remove(word)
def revise(self, x, y):
"""
Make variable `x` arc consistent with variable `y`.
To do so, remove values from `self.domains[x]` for which there is no
possible corresponding value for `y` in `self.domains[y]`.
Return True if a revision was made to the domain of `x`; return
False if no revision was made.
"""
overlap = self.crossword.overlaps[x, y]
if overlap == None:
return False
#判断是否修改过
res = False
wordx = self.domains[x].copy()
for word1 in wordx:
#判断是否存在
flag = False
for word2 in self.domains[y]:
if word1[overlap[0]] == word2[overlap[1]]:
flag = True
break
if flag:
res = True
else:
self.domains[x].remove(word1)
return res
def ac3(self, arcs=None):
"""
Update `self.domains` such that each variable is arc consistent.
If `arcs` is None, begin with initial list of all arcs in the problem.
Otherwise, use `arcs` as the initial list of arcs to make consistent.
Return True if arc consistency is enforced and no domains are empty;
return False if one or more domains end up empty.
"""
if arcs == None:
arcs = []
for x in self.crossword.variables:
for y in self.crossword.variables:
if x != y:
arcs.append((x, y))
while len(arcs) != 0:
(x, y) = arcs.pop(0)
if self.revise(x, y):
if len(self.domains[x]) == 0:
return False
for z in self.crossword.neighbors(x):
if z != y:
arcs.append((z, x))
return True
def assignment_complete(self, assignment):
"""
Return True if `assignment` is complete (i.e., assigns a value to each
crossword variable); return False otherwise.
"""
return creator.crossword.variables == set(assignment.keys())
def consistent_helper(self, x, y, assignment):
#判断variable是否consistent
overlap = self.crossword.overlaps[x, y]
if overlap == None:
return True
word1 = assignment[x]
word2 = assignment[y]
return word1[overlap[0]] == word2[overlap[1]]
def consistent(self, assignment):
"""
Return True if `assignment` is consistent (i.e., words fit in crossword
puzzle without conflicting characters); return False otherwise.
"""
for x in assignment:
for y in assignment:
if x != y:
if not self.consistent_helper(x, y, assignment):
return False
return True
def order_domain_values(self, var, assignment):
"""
Return a list of values in the domain of `var`, in order by
the number of values they rule out for neighboring variables.
The first value in the list, for example, should be the one
that rules out the fewest values among the neighbors of `var`.
"""
words = self.domains[var]
neighbors = self.crossword.neighbors(var)
cnts = []
for word in words:
cnt = 0
for neighbor in neighbors:
if neighbor not in assignment and word in self.domains[neighbor]:
cnt += 1
cnts.append(cnt)
tmp = list(zip(words, cnts))
tmp.sort(key=lambda x: -x[1])
return [word[0] for word in tmp]
def select_unassigned_variable(self, assignment):
"""
Return an unassigned variable not already part of `assignment`.
Choose the variable with the minimum number of remaining values
in its domain. If there is a tie, choose the variable with the highest
degree. If there is a tie, any of the tied variables are acceptable
return values.
"""
variable = list(self.crossword.variables - set(assignment.keys()))
num_remain = [len(self.domains[var]) for var in variable]
degree = [len(self.crossword.neighbors(var)) for var in variable]
tmp = list(zip(variable, num_remain, degree))
def cmp(x, y):
if x[1] != y[1]:
if x[1] > y[1]:
return 1
else:
return -1
else:
if x[2] < y[2]:
return 1
elif x[2] > y[2]:
return -1
else:
return 0
sorted(tmp, key=functools.cmp_to_key(cmp))
return tmp[0][0]
def backtrack(self, assignment):
"""
Using Backtracking Search, take as input a partial assignment for the
crossword and return a complete assignment if possible to do so.
`assignment` is a mapping from variables (keys) to words (values).
If no assignment is possible, return None.
"""
if self.assignment_complete(assignment):
return assignment
var = self.select_unassigned_variable(assignment)
for value in self.order_domain_values(var, assignment):
assignment[var] = value
if self.consistent(assignment):
result = self.backtrack(assignment)
if result != None:
return result
assignment.pop(var)
return None本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere