爬山（Hill Climbing）
爬山（最陡/随机上升等变体在文献里统称 local search 的一类）是改进式基础启发式：自一可行解出发，在事先定义的邻域中反复将当前解换为不更差、直到邻域中不存在进一步改进的邻居为止，常停在目标函数的局部最优。与 k-opt 系列 常作为同一条「局部搜索子程序」的不同邻域；与 元启发式总览 里的模拟退火、禁忌、ILS 等相对，本页所述是不接受劣化、单轮下降的经典形态。总类见 基础启发式 中改进式、及 启发式算法总览。
记号
- 目标：多数叙述取最小化 f(s)，s 为解表示（路径序、位串等）。
- 邻域：N(s) 为与 s 在邻接关系上可达的一批可行解；具体由 2-opt、单点换等定义。
- 改进：从 s 若存在 s′∈N(s) 使 f(s′) < f(s)，则称存在改进；爬山一步即沿某规则选入这样一个 s′ 替换 s。
常见变体
- 最陡下降（steepest / best improvement）：一步中枚举 N(s) 全体（或一规范子集），选使 f 下降最大的邻居；步数可较少，单步代价大。
- 先改进（first improvement）：在预定扫描顺序中遇到第一个改进就接受，单步快、总步数可能更多。
- 随机化邻居序：在预生成或随机的 N(s) 顺序上做先改进，用于减轻确定序带来的偏向。
局限：若邻域不连通到全局最优附近，会停在多个局部最小之一。实践中常与随机重启、迭代局部搜索 的扰动、或接受劣化机制组合。
主过程（最小化、示意框）
下框用「在邻域内先改进、直至无」的固定写法；N 与邻接扫描方式由问题实现定稿。
▶ 爬山
1. 初始化
取可行初解 s，记 s* ← s（可维护历史最优，依实现与是否要记录全局最优二选一或并存）。
2. 邻域内改进
在 N(s) 上按你选的规则（最陡/先改进等）求改进邻居；若存在使 f 更小的 s′，令 s ← s′，并视需要更新 s*，返回步骤 2。
3. 终止
若 N(s) 中无更优邻居，则 s 为当前邻域的局部最优；结束（可再接外层 ILS/多起点等，不在本框内展开）。
注：连续优化里「梯度 + 小步长」的爬山与离散组合上基于邻域的爬山是同一套抽象在不同表示下的实例。