- 本质：从眼前某一初始解出发，在每一个阶段都做出当前最优的决策，即贪心策略，逐步逼近给定的目标，尽可能快地求出更好地解。也即以逐步的局部最优达到全局最优。
- 推论：
- 贪心算法在每阶段面临选择时，都做出对眼前来说最有利的选择，并不考虑该选择对将来是否有不良影响。
- 算法不允许回溯，决策一旦做出不可改变。
- 贪心策略决定了算法的性能与表现。
- 算法具有不稳定性，不一定得到全局最优解，但也能得到最优解很好的近似解。因此，在贪心策略确定后应当提供严谨的数学证明，以证明其一定能得到问题的最优解。
- 算法具有高效性，可以很快获得一个问题的解。
指一个问题的最优解一定包含其子问题的最优解。换句话来说，也即一个问题能够分解成各个子问题来解决，通过各个子问题的最优解能够得到原问题的最优解，那么原问题的最优解一定包含各个子问题的最优解。
证明问题是否具有最优子结构性质的步骤如下：
- 设出问题的最优解；
- 给出“子问题的解一定是最优的”结论；
- 采用反证法证明Step-2中的结论。
指所求问题的整体最优解可以通过一系列局部最优的选择获得，即可通过逐步局部最优选择使最终的选择方案是全局最优的。其中每次所作的选择，可以依赖于之前的选择，但不依赖于将来的选择。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择能够最终导致问题的一个整体最优解。首先考查问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且作了贪心选择后，原问题简化为一个规模更小的子问题，然后证明最优子结构性质即可。
2.3 实例- 单源最短路径问题(Dijkstra——迪杰斯特拉)。相关概念界定如下：
- 源点：出发点；
- S S S集合：已经确定到源点最短路径的点构成的集合。
- V − S V-S V−S集合：尚未确定到源点最短路径的点构成的集合。
- 特殊路径：从源点出发，只经过 S S S中的点，到达 V − S V-S V−S中的点的路径。
最初：源点到自身的路径已经确定，其长度为0，故 S S S集合中只有源点；源点到其他顶点的路径尚未确定，故集合 V − S V-S V−S是除源点之外的其他所有点组成的集合。
该算法的贪心策略可表述为：选择特殊路径长度最短的，将其相连的 V − S V-S V−S中的顶点加入到集合 S S S中，检查新增加的特殊路径是否优于原来找到的特殊路径，若新的特殊路径最优，则优化。代码示例如下：
import sys
def dijkstra(start_point, graph):
n = len(graph)
# 初始化各项数据，把dist[start]初始化为0，其他为无穷大
dist = [sys.maxsize for _ in range(n)]#路径长度
pre = [-1 for _ in range(n)]#前驱pre
s = [False for _ in range(n)]#集合S
dist[start_point]=0
for i in range(n):
minLength = sys.maxsize
minVertex = -1
for j in range(n):
if not s[j] and dist[j] < minLength:
minLength = dist[j]
minVertex = j
s[minVertex] = True
# 从这个顶点出发，遍历与它相邻的顶点的边，计算特殊路径长度，更新dist和pre
for edge in graph[minVertex]:
if not s[edge[0]] and minLength + edge[1] < dist[edge[0]]:
dist[edge[0]] = minLength + edge[1]
pre[edge[0]] = minVertex
return dist, pre
if __name__ == "__main__":
data = [
[1, 0, 8],
[1, 2, 5],
[1, 3, 10],
[1, 6, 9],
[2, 0, 1],
[0, 6, 2],
[3, 6, 5],
[3, 4, 8],
[0, 5, 4],
[5, 6, 7],
[5, 3, 8],
[5, 4, 5]]#边集合（顶点，顶点，边权）
n = 7#图的顶点数n
graph = [[] for _ in range(n)]#图的邻接表
#根据输入的图构建图的邻接表
for edge in data:
graph[edge[0]].append([edge[1], edge[2]])
graph[edge[1]].append([edge[0], edge[2]])
dist,pre = dijkstra(1,graph)
print("dist=n",dist)
print("pre=n",pre
参考资料：王秋芳, 算法设计与分析[M], 清华大学出版社, 2021.
