Iterative Improvement Algorithms
• In many optimization problems, the path to a goal is irrelevant
— the goal state itself is the solution
• State space = a set of goal states
— find one that satisfies constraints (e.g., no two classes at same time)
— or find optimal one (e.g., highest possible value, least possible cost)
• Iterative improvement algorithms – keep a single “current“ state, try to improve it
— Constant space
— Suitable for both offline and online search
n-Queens Problem
同一行同一列不能有两个皇后
迭代改进 Iterative improvement：在每一列中，尝试将皇后移动到减少冲突的位置。
Travelling Salesperson Problem
访问所有城市最短路径且一个城市只能去一次 最后回到起点城市
在每一步中，尝试通过交换路径中的两个城市来改进当前的路径。（两个城市交换目标城市）
Hill-climbing (or gradient ascent/descent)
试图通过逐步改善当前状态来找到问题的解决方案。在这个算法中，我们从一个初始状态开始，然后尝试移动到邻近状态中具有更高评价函数值（更接近目标状态）的状态。
• n-queens problem
a) 8皇后问题中的局部最小值（h = 1）
状态空间中的局部最小值指的是一种棋子配置，在这种配置下，单个移动无法改善局面，尽管它可能不是最优解（最优解是没有任何皇后互相攻击的状态，即 h = 0）。
在这种情况下，如果 h=1h=1，这意味着恰好有一对皇后互相攻击。
b) h = 17 的状态及每个可能后继的 h 值
在这种情况下，状态 h=17h=17 表示有 17 对皇后互相攻击。这是一个更复杂的配置，其中多个皇后存在冲突。
局部最小值h=1 表示一种非最优状态，但无法通过单次移动改善，而状态 h=17h=17 表示一个更复杂的配置，存在多个攻击对，评估后继状态有助于找到通向最优解的路径。
State space “landscape”
• Random-restart hill climbing:
— repeat with randomly chosen starting points
• If finitely many local maxima, then 
• Local maxima — peak that is lower than the highest peak in the state-space 局部最大
• Peak — search can oscillate 评估函数达到最高值的点
• Plateaux — state-space region in which evaluation function is flat 评估函数值相对平坦的区域
Annealing Algorithm
For a finite set of iterations
1 Sample a new point xt ∈ N (x) 从一个随机选择的当前解x生成一个新解xt
2 Jump to a new sample with probability given by an acceptance function P [x, xt, T ] 根据接受函数P[x, xt, T]计算接受新解xt的概率
3 Decrease temperature T 在每次迭代后，降低温度T
• Green lines represent gradient-following optimizations 沿着梯度方向进行搜索，以找到使目标函数最小化的参数值。
• Red lines represent jumps from simulated annealing
— Possibly avoiding local optimaSolution space 在搜索过程中引入一定的随机性，允许算法在某些情况下接受更差的解，从而有机会跳出局部最优解。
Properties of Simulated Annealing
• T → 0: like Hill climbing 只接受比当前解更好的解
• T → ∞: random walk 接受新解
— decrease T slowly
如果我们足够缓慢地减小 T，P 接近 1
标签：状态,Search,17,space,AI,state,皇后,Local,xt From： https://blog.csdn.net/weixin_74400487/article/details/142000193