組合最最佳化問題是在給定有限集合的所有具某些特性的子集簇中,尋找使某種指標達到最優的子集的問題。依據問題的性質,包括有排序問題、匹配問題和網路流問題等。組合最最佳化的特點是:多數問題屬於所謂的NP完全問題,即對該問題基本上不存在一種算法,使得當所有的具體問題的變數和約束條件的數目兩者之和甚大時,可以在容許時間(即所謂的多項式時間)之內給出所要的解。由於這類問題在生產實際中經常出現,不能予以忽視,於是出現了兩類解決問題的途徑:一類是所謂的直觀算法,另一類是近似算法。隨著組合最最佳化研究的進展,一些數學分支,如組合數學、擬陣和廣義擬陣以及圖論等,也相應地得到新的發展。
基本介紹
- 中文名:組合最最佳化問題
- 外文名:combinatorial optimizationproblem
- 套用學科:數學術語
- 範疇:數理科學
- 定義:一類在離散狀態下求極值的問題
- 涉及:離散數學
概述
基本原理
![](/img/d/1d2/1b24bfdbf398167698bbdc36340a.jpg)
![](/img/f/b96/0d338bb96ed6f108d9faa6ebb873.jpg)
![](/img/4/100/e92aa9ebd8df63c1c59bca66ca69.jpg)
![](/img/8/505/354bb724b1a4f4dc1f01e02f3199.jpg)
![](/img/a/13e/adddca10488367b21ec4c8b34379.jpg)
![](/img/4/1cc/42b5ffedf41b08c469598b40e213.jpg)
![](/img/9/f6b/a6c4631dc04c8f652aca2a5e84d4.jpg)
![](/img/e/8e6/cb00ec9960a967a862a395b9deca.jpg)
![](/img/c/72b/14320bf88513b2e898069587e5d2.jpg)
![](/img/a/782/803b684802e229ba80297d0e82d7.jpg)
![](/img/a/2cd/ec78c6c6c2b7aee9d1fa8faee6aa.jpg)
![](/img/b/64b/f310efca92d4db4513337ca8f0cc.jpg)
![](/img/1/262/2317e51587204afd867edee197bb.jpg)
![](/img/a/b1c/6681432f68c2e97f78591740276e.jpg)
![](/img/e/be8/66f9bc772e69874c3478bd3ffaad.jpg)
![](/img/2/95c/d7ade2dfd0b5d1a2891095c551b2.jpg)
![](/img/c/528/04cb11996ffc4525080f51928791.jpg)