贪心决策模型

把贪心抽象为确定性序贯决策:状态、动作、代价与安全选择;选择型和合并型都落入同一框架。

标签 算法 / 贪心 / 安全选择 / 交换论证

模型

设 𝑆 是状态集,𝑠0∈𝑆,𝑇⊆𝑆 是终止状态集。对非终止状态 𝑠,给定非空有限动作集 𝐴(𝑠)、转移 𝛿(𝑠,𝑎) 与代价 𝑐(𝑠,𝑎)∈ℝ。

从状态 𝑠 出发的动作序列是有限序列 𝜋=(𝑎1,…,𝑎𝑘),满足 𝑎𝑖∈𝐴(𝑡𝑖),其中 𝑡0=𝑠、𝑡𝑖+1=𝛿(𝑡𝑖,𝑎𝑖)。对应的状态序列为 𝑡0,…,𝑡𝑘;若 𝑡𝑘∈𝑇,称 𝜋 终止。假设从每个可达状态出发的极大动作序列都在有限步内终止。

状态值 𝐹(𝑠) 满足

𝐹(𝑠)=min𝑎∈𝐴(𝑠){𝑐(𝑠,𝑎)+𝐹(𝛿(𝑠,𝑎))},

其中 𝐹(𝑡)=0 对 𝑡∈𝑇。贪心策略由局部键 𝜅(𝑠,𝑎) 给出:

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

𝜅 不必等于真实代价。上述 𝐹 方程是 动态规划 在每条转移只有一个后继、聚合取 min 时的特例。

安全选择

若从 𝑠0 可达的每个非终止状态 𝑠 都满足

𝑔(𝑠)∈argmin𝑎∈𝐴(𝑠){𝑐(𝑠,𝑎)+𝐹(𝛿(𝑠,𝑎))},

则沿 𝑔 的路径最优;对剩余步数归纳即可。安全选择通常由交换论证证明。拟阵 只是选择型的一类交换结构,不是本模型的公理。

源码位置