分类:组合优化

组合优化在离散对象中寻找满足约束的最优选择，常见对象包括路径、树、集合族与网络。对象有限并不表示可以在可接受时间内枚举完毕，结构性质决定了能否采用贪心、精确算法或近似方法。

• 集合与代价：击中集 → 最大覆盖问题 → 次模函数 → 超模函数。
• 可行结构：拟阵 → 拟阵交 → 多拟阵 → 图拟阵。
• 网络中的优化：斯坦纳树问题 → 反馈边集 → 反馈顶点集。

先写明可行集合与目标，再区分精确最优和具有保证的近似结果。次模性、拟阵等结构能支持特定算法，但不能把相应保证直接迁移到缺少这些条件的问题上。