最大團(tuán)問題的熵正則化方法研究.pdf

1、最大團(tuán)問題是組合優(yōu)化中的一個(gè)經(jīng)典的NP-完全問題。此問題自被人們發(fā)現(xiàn)之后，廣為研究和應(yīng)用。但是因?yàn)閱栴}本身的復(fù)雜性，所以人們將研究的重點(diǎn)放在了問題的近似計(jì)算上，即啟發(fā)式算法，并且得到了一系列的研究成果。 最大團(tuán)問題有相當(dāng)多的等價(jià)的數(shù)學(xué)描述，并且針對不同的模型具體的研究方法也有一定的差別。本論文的研究是基于1965年Motzkin和Straus給出的一個(gè)二次連續(xù)化模型。該模型的優(yōu)點(diǎn)就是將最大團(tuán)問題的研究方法和工具推進(jìn)到了連續(xù)的領(lǐng)域

2、。在此問題模型的基礎(chǔ)上，針對該模型中因?yàn)閳D的鄰接矩陣在一般的情況下多是退化矩陣而導(dǎo)致的病態(tài)，人們進(jìn)行了一系列處理，并且得到了不錯(cuò)的結(jié)果。 對于M-S模型，它的另外一個(gè)優(yōu)點(diǎn)，或者說更為重要的是，該模型的約束條件表示為一個(gè)單純形的形式。根據(jù)該形式，我們可以運(yùn)用信息論的知識來進(jìn)行研究。正是基于此，我們給出了最大團(tuán)問題的信息論方法——熵函數(shù)方法和叉熵函數(shù)方法，以及D函數(shù)正則化方法。其中我們在第三章中給出的是熵正則化方法和叉熵正則化方法，