序贪心条件
在可用集合上按优先级取极值;静态全序对应排序贪心,后继关系对应最佳优先与多路归并。标签 算法 / 贪心 / 排序 / 优先队列 / 交换论证
以下沿用 贪心决策模型 的记号。
静态全序
设 为动作集,。状态 下的可用动作集为 ,且
与 无关。每步取
设动作序列 是 的一个排列, 为目标函数值。若对相邻的 ,当 时
则存在按 非降序排列的最优动作序列。
后继关系
设 为当前可选动作集, 为后继关系,并假设每个尚未取出的动作 都存在 与链 。若
则
的 不大于任何尚未取出动作的 。因此按 非降序枚举时, 可作为下一个输出。堆、最佳优先枚举和多路归并属于此类。
边界
若存在相邻的 使 但 ,则静态排序的结论不成立。若存在 使 ,则不能由后继单调性推出 的 最小。