组合优化

类别

主题软件网络科学家类别:网络理论类别:图论vte组合优化是数学优化的一个子领域，包括从一个有限的对象集合中找到一个最佳对象，其中可行的解决方案的集合是离散的或可以减少到一个离散的集合。典型的组合优化问题是旅行推销员问题（TSP）、最小生成树问题（MST）和结囊问题。在许多这样的问题中，如前面提到的问题，穷举搜索是不可行的，因此必须采用能迅速排除大部分搜索空间的专门算法或近似算法来代替。组合优化与运筹学、算法理论和计算复杂性理论有关。它在多个领域有重要的应用，包括人工智能、机器学习、拍卖理论、软件工程、应用数学和理论计算机科学。

供应链优化开发最佳的辐条和目的地的航空网络决定车队中哪些出租车要去取票确定运送包裹的最佳方式将工作以最佳方式分配给人设计水分配网络地球科学问题（如水库流量）方法对于某些特殊类别的离散优化，有大量的多项式时间算法的文献。其中相当多的文献是由线性规划理论统一的。这个框架所涵盖的组合优化问题的一些例子是最短路径和最短路径树、流量和循环、生成树、匹配和矩阵问题。对于NP-完整的离散优化问题，目前的研究文献包括以下主题。多项式时间可精确解决的问题的特例（如固定参数可解决的问题）在随机实例上表现良好的算法（如旅行推销员问题）在多项式时间内运行并找到接近最优解的近似算法解决实践中出现的现实世界的实例，不一定表现出NP-完全问题的最坏情况（如。组合优化问题可以被看作是寻找一些离散项目集合的最佳元素；因此，原则上，任何种类的搜索算法或元启发式都可以用来解决它们。

也许最普遍适用的方法是分支和边界（一种可以在任何时间点停止的精确算法，作为启发式算法）、分支和切割（使用线性优化来产生边界）、动态编程（一种具有有限搜索窗口的递归解决方案构造）和塔布搜索（一种贪婪型交换算法）。然而，通用搜索算法不能保证首先找到最优解，也不能保证快速运行（在多项式时间内）。由于一些离散优化问题是NP-完备的，如旅行推销员（决策）问题，除非P=NP，否则这是预期的。

从形式上看，一个组合优化问题A{displaystyleA}是一个四元组(I,f,m,g){displaystyle(I,f,m,g)}，其中，I,f,m,g是一个四元组。对于每一个组合优化问题，都有一个相应的决策问题，询问对于某些特定的问题是否有可行的解决方案。