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

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

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