Local-search algorithms keep one candidate solution and inspect solutions reachable by a small
allowed change. They do not build a complete search tree. This applet compares strategies that
differ in how they generate a neighbor, decide whether to accept it, and respond when progress stalls.
Neighborhood and acceptance rule
The neighborhood is the set of states reachable by one permitted move. The
objective function scores each state. Simple hill climbing accepts an improving
neighbor; steepest ascent evaluates all generated neighbors and takes the best improvement;
stochastic and first-choice variants sample the neighborhood differently. Random restart changes
the starting state after a stall. Simulated annealing can accept a worse move.
Why greedy search gets stuck
A local optimum is better than every immediate neighbor but not necessarily better than every
state. A plateau contains many neighbors with equal score. A ridge may require a sequence of moves
that do not immediately improve the objective. A greedy algorithm that accepts only improvement
can stop at any of these structures even when a better region exists elsewhere.
No improving neighbor is a statement about the chosen move set and current location. It is not
evidence that the current solution is globally optimal.
Two escape mechanisms
Random restart runs a local search from several independently chosen starts and
keeps the best result. It does not repair one trapped trajectory; it samples additional basins of attraction.
Simulated annealing accepts an improving move and may accept a worsening move of
cost increase ΔE > 0 with probability exp(−ΔE/T). At high temperature
T, worsening moves are relatively likely. As temperature falls, the process becomes
more selective. Cooling too quickly can freeze the search; cooling slowly spends more evaluations exploring.
What the three problem families reveal
- Traveling salesperson: a neighbor reverses a tour segment. This implementation
generates 66 segment reversals for 12 positions, including some cycle-equivalent alternatives.
- Eight queens: moving one queen within its column creates many plateaus and local optima.
- Function landscape: the heatmap makes attraction basins and escape moves visible,
although the algorithm itself receives only objective values for candidate states.
What this model leaves out
Practical optimization can use tabu memory, adaptive neighborhoods, parallel restarts,
evolutionary populations, or problem-specific relaxations. Simulated annealing has asymptotic
global-convergence results only under restrictive assumptions and extremely slow schedules such
as logarithmic cooling; those results do not mean a finite classroom run is guaranteed to find
the global optimum.
For teachers
Curriculum: Objective functions, neighborhoods, local and global optima,
plateaus, random restart, simulated annealing, temperature, and cooling schedules.
Pre-exploration prompts:
- How would you search for a mountain peak if fog limited you to nearby slopes?
- Can every sequence leading to a better final answer improve at every step?
- Which part of an optimization problem defines what counts as nearby?
Post-exploration prompts:
- Run steepest ascent from several starts. Which differences come from the algorithm, and which from the start state?
- Compare random restart with one long climb. What additional regions are sampled?
- Compare fast and slow cooling. Count accepted worsening moves early and late.
- Find a plateau in eight queens. Why can equal-score neighbors matter even when none is better?
Misconceptions to test: local optimum means global optimum; more randomness
always helps; the algorithm sees the heatmap; theoretical convergence guarantees practical success.
局部搜索算法保留一个候选解，并检查通过一次小型允许变化能够到达的其他解。它不会建立完整搜索树。本工具比较多种策略，它们在生成邻居、决定是否接受邻居以及进展停滞时如何响应方面不同。
邻域与接受规则
邻域是通过一次允许移动可以到达的状态集合，目标函数为每个状态评分。简单爬山法接受改进邻居；最陡上升会评估生成的全部邻居并选择最佳改进；随机与首选变体采用不同的邻域抽样方式。随机重启在停滞后改变起点，模拟退火则可以接受更差移动。
为什么贪心搜索会卡住
局部最优比所有直接邻居更好，却不一定比所有状态更好。平台包含许多同分邻居，山脊可能需要连续执行若干不会立即改善目标的移动。只接受改进的贪心算法可能停在这些结构中，即使其他区域存在更好答案。
没有更好的邻居，只说明在当前地点和所选移动规则下没有即时改进，并不能说明当前解是全局最优。
两种逃逸机制
随机重启从多个独立选择的起点运行局部搜索，并保留最佳结果。它不是修复一条被困轨迹，而是对更多吸引域进行抽样。
模拟退火会接受改进移动，也可能以概率 exp(−ΔE/T) 接受成本增加 ΔE > 0 的更差移动。温度 T 较高时，更差移动相对容易被接受；温度下降后，过程逐渐严格。冷却过快可能使搜索冻结，冷却较慢则会花更多评估用于探索。
三类问题分别揭示什么
- 旅行商问题：一个邻居通过反转路线片段产生。本实现对 12 个位置生成 66 种片段反转，其中包括一些在循环路线意义下等价的方案。
- 八皇后：在每一列内移动一个皇后会形成许多平台和局部最优。
- 函数景观：热力图让吸引域和逃逸移动可见，但算法本身只接收候选状态的目标函数值。
这个模型省略了什么
实际优化还会使用禁忌记忆、自适应邻域、并行重启、进化种群或问题专用松弛。模拟退火的渐近全局收敛结果只在严格假设和极慢冷却方案下成立，例如对数冷却。这些理论结果并不意味着有限的课堂运行保证找到全局最优。
教师指导
课程目标：目标函数、邻域、局部与全局最优、平台、随机重启、模拟退火、温度和冷却方案。
探索前问题：
- 如果雾只允许你看到附近坡度，你会如何寻找山峰？
- 通往更好最终答案的每一步是否都必须立即改善？
- 优化问题中的哪一部分定义了什么叫附近？
探索后问题：
- 从多个起点运行最陡上升。哪些差异来自算法，哪些来自起始状态？
- 比较随机重启与一次长爬升。随机重启抽样了哪些额外区域？
- 比较快速和慢速冷却，统计早期与后期接受的更差移动。
- 在八皇后中找到一个平台。即使没有邻居更好，同分邻居为什么仍可能重要？
需要检验的误解：局部最优就是全局最优；随机性越多越好；算法能看到热力图；理论收敛保证实际运行成功。