類別

主題軟件網絡科學家類別:網絡理論類別:圖論vte組合優化是數學優化的一個子領域，包括從一個有限的對象集合中找到一個最佳對象，其中可行的解決方案的集合是離散的或可以減少到一個離散的集合。典型的組合優化問題是旅行推銷員問題（TSP）、最小生成樹問題（MST）和結囊問題。在許多這樣的問題中，如前面提到的問題，窮舉搜索是不可行的，因此必須采用能迅速排除大部分搜索空間的專門算法或近似算法來代替。組合優化與運籌學、算法理論和計算復雜性理論有關。它在多個領域有重要的應用，包括人工智能、機器學習、拍賣理論、軟件工程、應用數學和理論計算機科學。

供應鏈優化開發最佳的輻條和目的地的航空網絡決定車隊中哪些出租車要去取票確定運送包裹的最佳方式將工作以最佳方式分配給人設計水分配網絡地球科學問題（如水庫流量）方法對于某些特殊類別的離散優化，有大量的多項式時間算法的文獻。其中相當多的文獻是由線性規劃理論統一的。這個框架所涵蓋的組合優化問題的一些例子是最短路徑和最短路徑樹、流量和循環、生成樹、匹配和矩陣問題。對于NP-完整的離散優化問題，目前的研究文獻包括以下主題。多項式時間可精確解決的問題的特例（如固定參數可解決的問題）在隨機實例上表現良好的算法（如旅行推銷員問題）在多項式時間內運行并找到接近最優解的近似算法解決實踐中出現的現實世界的實例，不一定表現出NP-完全問題的最壞情況（如。組合優化問題可以被看作是尋找一些離散項目集合的最佳元素；因此，原則上，任何種類的搜索算法或元啟發式都可以用來解決它們。

也許最普遍適用的方法是分支和邊界（一種可以在任何時間點停止的精確算法，作為啟發式算法）、分支和切割（使用線性優化來產生邊界）、動態編程（一種具有有限搜索窗口的遞歸解決方案構造）和塔布搜索（一種貪婪型交換算法）。然而，通用搜索算法不能保證首先找到最優解，也不能保證快速運行（在多項式時間內）。由于一些離散優化問題是NP-完備的，如旅行推銷員（決策）問題，除非P=NP，否則這是預期的。

從形式上看，一個組合優化問題A{displaystyleA}是一個四元組(I,f,m,g){displaystyle(I,f,m,g)}，其中，I,f,m,g是一個四元組。對于每一個組合優化問題，都有一個相應的決策問題，詢問對于某些特定的問題是否有可行的解決方案。