CMPUT 291 local seach

STA 问题

• 一个句子/表达式 使得P(x) = True

使用现有的方法 解决 STA

• 使用过大的空间
• 太多的K值
• 太多的变量
• 搜索了太多我们不关心的问题

local search

• 一个恒定的 令人满意的 问题
• neighbours function
• score function

neighbours

类似于其他搜索的successor

heuristic vs score

score is required

Hill CLimbing problems

1. Foothills : local max
2. Plateaus: Regions of the state space where the score is uninformative
3. Ridges: Foothills that would not be foothills with a larger neighbourhood
4. gnorance of the global optimum: Unless we reach a satisfying assignment, we cannot be sure that an optimum returned by local search is the global optimum.

Randomeized Algorithms

• random restart
• random step

seach END