基于聚類分析的背包問(wèn)題求解方法研究及其應(yīng)用.pdf

1、背包問(wèn)題是組合優(yōu)化學(xué)科中一個(gè)經(jīng)典而著名的問(wèn)題，它的研究?jī)r(jià)值不言而喻，吸引了眾多專家學(xué)者從各個(gè)角度開(kāi)展對(duì)其的研究工作，各種算法設(shè)計(jì)思想也應(yīng)運(yùn)而生。由于背包問(wèn)題的NP完全性，如何在算法的時(shí)間效率和求解精度上取得有效的平衡，成為背包問(wèn)題算法設(shè)計(jì)主要的考慮因素。數(shù)據(jù)挖掘是近幾年信息領(lǐng)域發(fā)展最快的技術(shù)之一。由于數(shù)據(jù)挖掘具有強(qiáng)大的發(fā)現(xiàn)有用知識(shí)的功能，可以利用它來(lái)發(fā)現(xiàn)背包問(wèn)題解的相似的狀態(tài)空間，然后進(jìn)行約減，從而克服背包問(wèn)題的NP困難性。 本

2、文研究了背包問(wèn)題的背景、國(guó)內(nèi)外研究現(xiàn)狀和發(fā)展趨勢(shì)，分析了背包問(wèn)題的性質(zhì)、各種形式的數(shù)學(xué)模型和算法設(shè)計(jì)策略。在完成以上的基礎(chǔ)工作后，提出自己的理論創(chuàng)新，構(gòu)建了基于聚類分析的背包問(wèn)題求解模型，并將其應(yīng)用于求解0/1背包問(wèn)題、子集和問(wèn)題和多維背包問(wèn)題。在實(shí)驗(yàn)部分，評(píng)估了模型的性能，發(fā)現(xiàn)模型具有良好的性能和穩(wěn)定的近似比，并且在時(shí)間效率和求解精度兩者之間能夠找到一個(gè)比較有效的平衡點(diǎn)。本文的創(chuàng)新點(diǎn)如下： (1)在掌握數(shù)據(jù)挖掘核心技術(shù)和理念的

3、基礎(chǔ)上，根據(jù)對(duì)背包問(wèn)題特性的分析，將經(jīng)典的背包問(wèn)題和新興的數(shù)據(jù)挖掘技術(shù)有機(jī)地結(jié)合起來(lái)，在背包問(wèn)題節(jié)點(diǎn)擴(kuò)展的過(guò)程中引入集中性和多樣性策略，提出了一個(gè)基于聚類分析的背包問(wèn)題求解模型； (2)基于聚類分析的背包問(wèn)題求解模型具有良好的可擴(kuò)展性，它可以根據(jù)不同的求解實(shí)例采用適合情況的模塊。在減少背包問(wèn)題解的狀態(tài)空間的過(guò)程中，模型可以實(shí)現(xiàn)無(wú)監(jiān)督自動(dòng)學(xué)習(xí)，去掉比較相似的狀態(tài)空間，為狀態(tài)空間的擴(kuò)展創(chuàng)造有利的條件；通過(guò)二分法的使用，進(jìn)一步優(yōu)化了模