贪婪算法（Greedy Algorithms）

大家好，欢迎来到IT知识分享网。

一，什么是贪婪算法

解决最简化问题的演算法，其解题过程可看成是由一连串的决策步骤所组成，而每一步骤都有一组选择要选定。

贪婪演算法的特性是 每一次选择都采取区域最佳接（locally optimal solution），而透过每一个区域最佳解最后综合成为全域最佳解（globally optimal solution）从而将问题解决

• 一个贪婪算法在每一决策步骤总是选定当下看来最好的选择
• 贪婪算法并不保证总是得到最佳解，但在有些问题可以得到最佳解

二，最短路径

三，使用贪婪解题策略的演算法

• 活动选择（activity-selection）演算法
• 背包（Knapsack）演算法
• Huffman编码演算法
• Kruskal最小扩张树演算法
• Prim最小扩张树演算法
• Dijkstra最短路径演算法

3.1 活动选择问题

• 假设有n个活动提出申请要使用一个场地，而这场地在同一时间点时最多只能让一个活动使用。
• 从这n个活动选一组数量最多，且可以在这场地举办的活动集。
• 假设活动 a_i 其提出申请使用场地的时段为半开半闭的区间 [ s_i, f_i )

一个活动选择问题

假设我们有一集合 S = { a₁, a₂, …,a_n }，其中有 n 个行销活动

• 对于每一个活动 a_i，其开始时间为 s_i 和结束时间为 f_i（当 0 ≤ a_i < f_i < ∞）
• 活动 a_i在半开放时间间隔内发生 [ s_i, f_i )

如果间隔[s_i，f_i）和[s_j，f_j）不重叠，则活动a_i和a_j是兼容的（compatible）

• 如果s_i ≥ f_i 或 s_i ≤ f_i，则说 a_i和a_j 是兼容的（compatible）

• 我们首先对这个程序制定一个动态规划解，其中我们将两个子问题的最优解结合起来，形成原始问题的最优解。
• 然后我们将观察到，我们只需要考虑一个选择——贪婪的选择——并且当我们做出贪婪的选择时，其中一个子问题被保证为空，因此只剩下一个非空的子问题。

活动选择问题的最优子结构

• S_ij= { a_k∈S : f_i ≤ s_k < f_k ≤ s_j }
  因此，S_ij 是 S 中活动的子集，可以在活动a_i结束之后开始，在活动a_j开始之前结束。
  
• 若 f₀ = 0 和 s_n+1 = ∞；
  则 S = S₀,_n+1（0 ≤ i, j ≤ n+1.）
  
• S_ij = S_ik ∪ {a_k} ∪ S_kj

1. a_i ∈! S → S 是 P(A{a_i}) 的最优解
2. a_i ∈ S → S {ai} 是 P(A\N[i]) 的最优解，但不一定是 P(A{a_i}) 的最优解<