王文杰

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

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

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

1 裝箱問題

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

2 旅行商問題

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

3 斯坦納樹問題

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

4 設(shè)施選址問題

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

5 計算復(fù)雜性理論

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

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

6 多面體組合

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

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

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

7 擬陣

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

8 結(jié)束語

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

參考文獻：

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

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

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

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