組合優(yōu)化若干經(jīng)典問題新進展分析

王文杰

摘 要：采用計算機科學和運籌學交叉的學科研究的方法，是組合優(yōu)化對經(jīng)典問題進行研究的方式。組合優(yōu)化，就是對于離散結構的問題進行性質(zhì)的求解，將不同離散問題進行結構差異的分析，采用不同的技巧和研究手段，針對經(jīng)典問題進行計算和理論的研究。

關鍵詞：組合優(yōu)化；經(jīng)典問題；進展分析

中圖分類號：O224 文獻標志碼：A 文章編號：2095-2945（2018）13-0057-02

Abstract： Using the method of interdisciplinary research of computer science and operational research is the way of combinatorial optimization to study classical problems. Combinatorial optimization is to solve the problem of discrete structure， to analyze the structural differences of different discrete problems， to use different techniques and research methods， and calculate and study the classical problems.

Keywords： combinatorial optimization； classical problems； progress analysis

組合優(yōu)化是采用離散結構的性質(zhì)的求解的方式，擺圖論和擬陣以及多面體進行性質(zhì)和求解的方法，采用計算復雜性和幾何計算結合的方式，運用計算機科學和運籌學的交叉，將關鍵的研究課題進行關注，經(jīng)過組合和優(yōu)化，得到了關于基礎理論和方法的有效計算結果。隨著網(wǎng)絡技術和信息科學的發(fā)展，當前運用互聯(lián)網(wǎng)進行人類生活方式的改變，例如物聯(lián)網(wǎng)的創(chuàng)新發(fā)展，帶來了組合優(yōu)化的研究方法，包含計算復雜性理論、算法設計和分析應用的研究內(nèi)容，經(jīng)過設計和分析，最終在應用領域利用算法進行了成果的展示和問題的解決。

1 裝箱問題

裝箱問題是經(jīng)典組合優(yōu)化的問題，該問題經(jīng)過研究后，得到了在線算法和近似算法，經(jīng)典裝箱問題是經(jīng)過論證的，簡單敘述為：給定若干尺寸進行物品的裝箱，每個箱子裝的物品的尺寸不能超過1，劃分問題和裝箱問題密切關聯(lián)，根據(jù)假設，最終的問題的算法和求解值經(jīng)過比率的劃分，得到了結果是大于等于1，裝箱問題有若干變形。將裝箱裝入單位的容量的箱子中，物品是通過一個一個的形式出現(xiàn)的。一些物品假設物品為邊長不超過1的矩形，集中類型的箱子經(jīng)過選擇，箱子為單位正方形，可行的裝箱不允許出現(xiàn)變尺寸裝箱[1]。在物品之間以及物品的邊界有任何的重疊，人們對于裝箱問題的在線模式的探討，經(jīng)過同一個箱子的向量和分量的計算，可以得到結果，對于裝箱的算法進行了重新的界定。在線環(huán)境下，在不知道任何后續(xù)物品的信息的前提下，必須經(jīng)過裝箱，并作出決定不得更改。采用這一在線算法的決策，使得物品信息在不全的情況下，是由于信息的缺失導致的算法的效果。

2 旅行商問題

TSP（旅行商）問題是組合優(yōu)化的基本問題，給定的網(wǎng)絡中一系列的點經(jīng)過兩兩之間的距離，得到了路徑是最短的。這條路徑恰好經(jīng)過了每個點，最后回到出發(fā)點。作為實際的問題，有徐哲對于TSP中的NP難的問題進行了驗證，發(fā)現(xiàn)TSP問題不存在近似比，常數(shù)為多項式時間算法。通?？紤]度量空間下的TSP，一般值得是點與點之間的距離，必須滿足三個條件：點到自身的距離，對稱性，三角不等式。在度量空間中，TSP可以找到近似比，常數(shù)為多項式時間算法。度量空間下的TSP不存在多項式時間，近似方案是一種特殊的近似算法，在多項式中可以達到近似值[2]。

3 斯坦納樹問題

網(wǎng)絡設計中，該問題屬于基礎性問題，在大規(guī)模的集成電路的設計中，斯坦納樹問題在給定的賦權聯(lián)通圖中，對于指定的頂點進行連續(xù)的子圖的求解，經(jīng)過一般假設連通的費用較小，指定的點為終端，其他頂點為斯坦納點。不同的度量空間下有不同的變形，在直線距離下給定點集的最短連通網(wǎng)絡。

4 設施選址問題

對于供應鏈管理和倉庫選擇，該問題是組合優(yōu)化領域中的熱點問題，研究具有很強的應用價值。在給定的若干位置中，選擇已經(jīng)建立的設施，使得顧客的需求得到滿足。連接的費用如果是非負的可以確定簡單的結構，給定設施的地址的集合，給定的顧客地址的集合以及顧客到開設設施的服務費用，在不同地址進行費用的開設，非度量的無容量限制，確定的地質(zhì)用于開設設施，則對稱的度量可以無容量地限制而不能直接應用于實際，設施的選址問題，最終顧客的開設的費用和連接的費用的和最小盡管無容量設施選址問題需要經(jīng)過算法設計，但是在解決實際問題上，其理論依據(jù)和算法思想等，是無容量限制的。而且，設施選址的領域還牽扯到帶容量限制的設施選址，和帶懲罰的設施選址問題等均為無容量限制的[3]。

5 計算復雜性理論

對于問題進行資源的定量分析，包括時間空間等，在算法復雜度的相互關系和基本性質(zhì)的問題上，經(jīng)過計算復雜性的分析，得到了關于計算機科學和應用數(shù)學相關領域的重大深遠的影響意義。

計算復雜性理論的歷史回溯，是在上世紀60年代提出的，具有空間的復雜性和時間性。經(jīng)過層級定理的證明，運行時間將多項式進行了規(guī)模性的輸入，得到的算法是有效的。包括中藥的組合優(yōu)化，有效的多項式時間算法，最大權匹配等等，計算復雜性理論的基礎被用來表示非確定型和確定型圖靈機模型，奠定了計算復雜性理論的基礎，用來表示時間的可解的問題。上世紀70年代進行可滿足性問題的組合優(yōu)化問題的判定，在NP問題上，歸類到完備類。NP中的任何問題在多項式內(nèi)，都進行了等價的時間可解。除了個別的案例之外，每個組合優(yōu)化的問題都被多項式的時間設定為完備的NP，使得PSHIFOU DENGYU泥皮這一難題受到矚目。

6 多面體組合

采用線性代數(shù)和多面體以及方法進行組合優(yōu)化的問題，是復雜性和組合優(yōu)化算法結合的有力的工具。運用高效的多項式時間算法，最大關系是組合的原始對偶的最小最大定理。組合的技術不僅被用來證明是組合優(yōu)化問題的多項式時間的可解性，經(jīng)過多方面的緊密交織和多面體的性質(zhì)加以導出，在算法上利用不等式解決了相應的組合優(yōu)化的問題，還可以對多面體的線性不等式系統(tǒng)進行刻畫，最終形成了多面體的組合研究的特征[4]。

對多面體進行匹配，也被用來為不少NP難的組合優(yōu)化的問題進行設計算法的驗證，例如履旅行商、設施選址問題等等。

例如在覆蓋類型和裝填的問題上。一個基本的框架就是逆阻和阻斷的多面體理論的討論，典型運用和研究較為廣泛，在多面體組合中發(fā)揮核心作用的對偶理論，采用不等式樣系統(tǒng)進行表達，包含了迭代建立定義多面體側面的不等式系統(tǒng)，得到了逆阻的多面體的性質(zhì)，對于定理和算法能夠導出，能夠對多面體的特征使得多面體完整的線性刻畫經(jīng)過證明是最小、最大關系的驗證途徑，建立多面體側面和頂點的極性、相應線性的對偶整數(shù)型，多面體組合的中心任務，為分離問題涉及算法的識別性的可行解的系統(tǒng)，非可行解和多面體的超平面系統(tǒng)。

7 擬陣

隨著擬陣分解定理的運用和建立，在發(fā)展促進中形成算法設計。這是一個基于某個有限集合的，滿足特定公例的獨立集系統(tǒng)，能夠被貪婪算法解決，形成組合優(yōu)化問題的結構特征，廣泛的擬陣的應用，混合矩陣論、網(wǎng)絡編碼等，次模型和擬陣被優(yōu)化界設定為重要課題，成為了次模優(yōu)化的重要基石。經(jīng)過定理分析和識別，產(chǎn)生了多項式時間算法，對于組合優(yōu)化等學科領域產(chǎn)生了深遠的影響。

8 結束語

組合優(yōu)化在信息科學技術的基礎上，通過數(shù)學理論和方法，與網(wǎng)絡互聯(lián)，逐步地將簡單的P和NP-難進行了兩級的劃分，最終回到了代價和算法的精度的平衡問題上。通過對精確算法的實用性的研究，保證了算法的精確度，降低了指數(shù)的復雜性，促使人們能夠對問題的計算的有效性進行深入的探討，使得多面體理論、復雜性思想和統(tǒng)計方法顯現(xiàn)出較大的作用。

參考文獻：

[1]陳兆盟，吳文祥，劉小明，等.車道擁擠收費與信號控制組合優(yōu)化模型研究[J].交通運輸系統(tǒng)工程與信息，2017（5）：29-35.

[2]吳曉進.函數(shù)最優(yōu)極值問題的組合優(yōu)化求解[J].內(nèi)蒙古師范大學學報（自然科學漢文版），2017（6）：800-802，806.

[3]朱學謙.海外石油項目多目標組合優(yōu)化研究[J].河南科學，2017（12）：2041-2047.

[4]楊麗麗，袁浩浩.基于組合優(yōu)化理論的協(xié)同過濾推薦算法[J].現(xiàn)代電子技術，2018（1）：139-142.