-
組合優化
鎖定
組合(最)優化問題是最優化問題的一類。最優化問題似乎自然地分成兩類:一類是連續變量的問題,另一類是離散變量的問題。具有離散變量的問題,我們稱它為組合的。在連續變量的問題裏,一般地是求一組實數,或者一個函數;在組合問題裏,是從一個無限集或者可數無限集裏尋找一個對象——典型地是一個整數,一個集合,一個排列,或者一個圖。一般地,這兩類問題有相當不同的特色,並且求解它們的方法也是很不同的。
來源:《組合最優化算法和複雜性》,高等教育出版社,1988,C.H. Papadimitriou, K. Steiglitz (劉振宏,蔡茂誠 譯)
- 中文名
- 組合優化
- 外文名
- Combinatorial Optimization
- 釋 義
- 組合問題的可行解集中求出最優解
組合優化概念定義
組合優化(Combinatorial Optimization)問題的目標是從組合問題的可行解集中求出最優解,通常可描述為:令Ω={s1,s2,…,sn}為所有狀態構成的解空間,C(si)為狀態si對應的目標函數值,要求尋找最優解s*,使得對於所有的si∈Ω,有C(s*)=minC(si)。組合優化往往涉及排序、分類、篩選等問題,它是運籌學的一個重要分支。
組合優化問題分類
典型的組合優化問題有:
生產調度問題(Production Scheduling Problem,如Flow-Shop,Job-Shop);
0-1揹包問題(Knapsack Problem);
裝箱問題(Bin Packing Problem);
圖着色問題(Graph Coloring Problem);
聚類問題(Clustering Problem);
最大團問題 等。