序贪心条件

在可用集合上按优先级取极值;静态全序对应排序贪心,后继关系对应最佳优先与多路归并。

标签 算法 / 贪心 / 排序 / 优先队列 / 交换论证

以下沿用 贪心决策模型 的记号。

静态全序

设 𝐸 为动作集,𝜅:𝐸→ℝ。状态 𝑠 下的可用动作集为 𝐴(𝑠)⊆𝐸,且

𝜅(𝑠,𝑎)=𝜅(𝑎)

与 𝑠 无关。每步取

𝑔(𝑠)∈argmin𝑎∈𝐴(𝑠)𝜅(𝑎).

设动作序列 𝜋=(𝑝1,…,𝑝𝑛) 是 𝐸 的一个排列,𝐶(𝜋) 为目标函数值。若对相邻的 𝑎,𝑏,当 𝜅(𝑎)≤𝜅(𝑏) 时

𝐶(…,𝑎,𝑏,…)≤𝐶(…,𝑏,𝑎,…),

则存在按 𝜅 非降序排列的最优动作序列。

后继关系

设 𝐴(𝑠) 为当前可选动作集,→ 为后继关系,并假设每个尚未取出的动作 𝑏 都存在 𝑎∈𝐴(𝑠) 与链 𝑎→…→𝑏。若

𝑎→𝑏⇒𝜅(𝑏)≥𝜅(𝑎),

则

𝑔(𝑠)∈argmin𝑎∈𝐴(𝑠)𝜅(𝑎)

的 𝜅 不大于任何尚未取出动作的 𝜅。因此按 𝜅 非降序枚举时,𝑔(𝑠) 可作为下一个输出。堆、最佳优先枚举和多路归并属于此类。

边界

若存在相邻的 𝑎,𝑏 使 𝜅(𝑎)≤𝜅(𝑏) 但 𝐶(…,𝑎,𝑏,…)>𝐶(…,𝑏,𝑎,…),则静态排序的结论不成立。若存在 𝑎→𝑏 使 𝜅(𝑏)<𝜅(𝑎),则不能由后继单调性推出 𝑔(𝑠) 的 𝜅 最小。

源码位置