组合算法

组合算法（combinatorial algorithm），理学-计算机科学技术-计算机科学理论-算法-组合算法，算法的核心内容之一，通常是指在图（graph）等离散结构上的算法。组合算法研究离散结构上的计算问题，离散结构包括图、超图（集族）、拟阵、偏序集、字符串、排列组合等数学对象，计算问题包括产生（generation）、枚举（enumeration）、计数（counting）、判定（decision）、搜索（search）、优化（optimization）等形式。以图为例，图上的组合算法主要有最大匹配算法、最大流与最小割算法、最短路径算法、最小生成树算法等。组合算法有计算机科学和数学两个源头。计算机科学家主要研究离散组合算法，包括贪心法、动态规划法等，数学家主要研究连续优化算法，如线性规划等。对组合算法的研究亦导致对计算复杂性的研究。例如1965年埃德蒙兹（Edmonds）在研究一般图上最大匹配算法时，就讨论过多项式时间算法与指数时间算法的区别。