贪心算法（构造式，Greedy for Construction）
在组合优化构造阶段，贪心指：在尚未完成的解上，每一步在可行候选中，按立即可得的得分（边际长度、即时代价、按规则排序的优先序等）取当前看来最好的一步决策，不回溯、不把后步并入同一次全局优化里重解。是 基础启发式 中构造式的代表之一，与改进式邻域搜索相对。与动态规划、全局最短路等「在子结构上有最优性」的模型不同，贪心不保证在一般组合实例上全局最优。见 启发式算法总览 中「一、基础启发式」下的构造式折叠。
模式与作用
- 典型流程：自空或根状态，重复「列出本步可行候选 → 用规则或键值选一个 → 定稿」直至完整可行解。
- 常见用途：快出可行解和上界；作 GRASP 在 α=0 时 RCL 退化为纯贪心的起点；在分支定界或列生成中热启动或剪枝用界。
- 不保证性：TSP 最近邻、背包按价值密度装等，都有反例使解任意劣于最优。工程上常先贪心，再 k-opt 系列 或元启发式改进。
例子（路径与列表调度）
- TSP 最近邻：自某起点，每步在未访点里选离当前最近者，直至全访完。复杂度常为 O(n²) 量级，解的质量与起点、并列时的处理约定有关。
- MST/集合覆盖等子问题：Prim、Kruskal 等有证明的贪心是该子问题的最优，但嵌在更大原模型里时，整体仍可能是启发式叙述。
- 列表调度：如按截止期 EDD 排序后再顺排，是用贪心序驱动构造。
与随机化、元启发式的衔接
注：在可结构化的极值问题上，「贪心」有时能证最优；在构造可行上界或快速启发式的场景里，多数只强调不证全局、只求快。读论文时以作者是否给出最优性或近似比为准。