基于聚類分析的背包問題求解方法研究及其應用.pdf

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

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

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