唯一父状态堆枚举

把隐式状态空间组织成每个非根状态恰有一个父状态的树;父值不大于子值,堆按值弹出即可不重不漏地做第 k 小枚举。

标签 算法 / 堆 / 枚举 / 偏序 / 第k小

模型

设 𝑆 是状态集,𝑠0∈𝑆 是根状态,𝑤:𝑆→ℝ 是状态值。每个非根状态 𝑥∈𝑆∖{𝑠0} 指定唯一父状态

𝑝(𝑥)∈𝑆,

并要求:

  • 父链有限,最终到达 𝑠0;
  • 𝑤(𝑝(𝑥))≤𝑤(𝑥)。

记 𝑥 的子状态集合为

𝐶(𝑥)={𝑦∈𝑆:𝑝(𝑦)=𝑥}.

算法维护一个小根堆,初始只放 𝑠0。重复 𝑘 次:

  1. 取出堆中 𝑤 最小的状态 𝑥;
  2. 把 𝐶(𝑥) 中的状态全部加入堆。

第 𝑘 次取出的状态就是第 𝑘 小状态。若需要输出方案,在加入子状态时记录父指针即可。

这是 序贪心条件 中后继关系的一个特例:𝐶(𝑥) 是 𝑥 的后继集合,父值不大于子值保证后继键不减。

正确性

唯一父状态保证每个状态只有一条从 𝑠0 出发的路径,因此每个状态只会被加入一次。

设某状态 𝑦 尚未被加入时,堆顶取出 𝑥 且 𝑤(𝑦)<𝑤(𝑥)。沿 𝑦 的父链向上,所有权值都不超过 𝑤(𝑦),因此这些祖先都应在 𝑥 之前被取出;它们被取出时会把 𝑦 加入堆,矛盾。因此堆顶按 𝑤 非降序弹出,第 𝑘 次弹出的就是第 𝑘 小状态。

每个状态生成 |𝐶(𝑥)| 个子状态;若每个状态的后继数为常数,则枚举 𝑘 个状态的时间为 𝑂(𝑘log𝑘),空间为 𝑂(𝑘)。

源码位置