组合最优化

扩展释义

组合最优化又称组合规划，是在给定有限集的所有具备某些特性的子集中，按某种目标找出一个最优子集的一类数学规划。初期，它所研究的问题，如广播网的设计、旅游路线的安排、课程表的制订等，都是网络上的一些极值问题。后来，对这些问题进行概括和抽象，在理论上研究了拟阵中一些更一般的组合最优化问题及算法。主要研究内容有：线性组合最优化问题；网络上的最优化问题；独立系统和拟阵，拟阵是组合优化中一个基本而重要的概念，许多组合问题都可化为拟阵问题。贪心算法是求拟阵的最优独立集的简单算法；交错链算法是求解最优交问题的基本算法。对问题算法的分类也是一类主要研究内容。某些算法具有多项式时间复杂度，如贪心算法、交错链算法，...