#### 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 = neighbor

#### Hill 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 current

#### Linear 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\}$

#### arc consistency

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

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))

#### CSPs as Search Problems

• 初始状态：empty assignment（无变量）
• 操作：给assignment添加$\{\text {variable}=\text {value}\}$
• 转移模型：显示添加assignment如何更改assignment
• 目标测试：检查所有分配的变量是否都满足约束
• 路径成本函数：所有路径具有相同的成本

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

• 最小约束值启发式：
• 首先尝试约束最少的变量 ### 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] == word2[overlap]:
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] == word2[overlap]

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)

return [word 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 != y:
if x > y:
return 1
else:
return -1
else:
if x < y:
return 1
elif x > y:
return -1
else:
return 0

sorted(tmp, key=functools.cmp_to_key(cmp))

return tmp

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