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

王文杰

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

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

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

1 裝箱問題

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

2 旅行商問題

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

3 斯坦納樹問題

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

4 設(shè)施選址問題

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

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

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

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

6 多面體組合

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

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

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

7 擬陣

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

8 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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