组合优化(英语:Combinatorial optimization)是数学优化的一个子领域,在应用数学和理论计算机科学的领域中,组合优化是在一个有限的对象集中找出最优对象的一类问题。[1]在很多组合优化的问题中,穷举搜索/枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的,并且目标是找到最优解。常见的例子有旅行推销员问题最小生成树

组合优化涉及运筹学算法理论计算复杂性理论,在人工智能机器学习、拍卖理论、软件工程超大规模集成电路应用数学理论计算机科学等多个领域有重要的应用。

组合优化的难处主要是加入拓扑分析的情况,不同的拓扑形态下,不同部分的约束关系便不同,算法也就要调整。如果给定一个拓扑形态,组合优化往往退化成一个整数优化的问题。

应用

编辑

特定问题

编辑

参考文献

编辑
  1. ^ Schrijver 2003,第1页.
  2. ^ Sbihi, Abdelkader; Eglese, Richard W. Combinatorial optimization and Green Logistics (PDF). 4OR. 2007, 5 (2): 99–116 [2019-12-26]. S2CID 207070217. doi:10.1007/s10288-007-0047-3. (原始内容存档 (PDF)于2019-12-26). 
  3. ^ Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier. Sustainable supply chain network design: An optimization-oriented review (PDF). Omega. 2015, 54: 11–32 [2019-12-26]. doi:10.1016/j.omega.2015.01.006. (原始内容存档 (PDF)于2019-12-26). 

引注

编辑