唯一父状态堆枚举
把隐式状态空间组织成每个非根状态恰有一个父状态的树;父值不大于子值,堆按值弹出即可不重不漏地做第 k 小枚举。标签 算法 / 堆 / 枚举 / 偏序 / 第k小
模型
设 是状态集, 是根状态, 是状态值。每个非根状态 指定唯一父状态
并要求:
- 父链有限,最终到达 ;
- 。
记 的子状态集合为
算法维护一个小根堆,初始只放 。重复 次:
- 取出堆中 最小的状态 ;
- 把 中的状态全部加入堆。
第 次取出的状态就是第 小状态。若需要输出方案,在加入子状态时记录父指针即可。
这是 序贪心条件 中后继关系的一个特例: 是 的后继集合,父值不大于子值保证后继键不减。
正确性
唯一父状态保证每个状态只有一条从 出发的路径,因此每个状态只会被加入一次。
设某状态 尚未被加入时,堆顶取出 且 。沿 的父链向上,所有权值都不超过 ,因此这些祖先都应在 之前被取出;它们被取出时会把 加入堆,矛盾。因此堆顶按 非降序弹出,第 次弹出的就是第 小状态。
每个状态生成 个子状态;若每个状态的后继数为常数,则枚举 个状态的时间为 ,空间为 。