團隊與事件組織問題是經(jīng)典的組合優(yōu)化問題,在運籌學領域早已進行了廣泛的研究。但是,隨著網(wǎng)絡通信的高速發(fā)展以及各種社交平臺的流行,社交網(wǎng)絡背景下的團隊與事件組織問題再次引起了眾多研究人員的注意。由于與社交網(wǎng)絡的結合,使得社交網(wǎng)絡中的團隊與事件組織問題與傳統(tǒng)版本的問題不同,從而其不能再簡單地借助針對集合覆蓋或背包問題等經(jīng)典問題的近似算法來解決。因此,在充分調研、結合現(xiàn)實情景的基礎上,我們首次正式定義了基于社交網(wǎng)絡的團隊組織收益通信比最大化問題、基于社交網(wǎng)絡的事件組織滿意度最大化問題和基于社交網(wǎng)絡的旅行規(guī)劃效用最大化問題。隨后,我們證明了這三個問題都是NP難問題,并且基于社交網(wǎng)絡的團隊組織收益通信比最大化問題和基于社交網(wǎng)絡的事件組織滿意度最大化問題不存在多項式時間近似方案。為了解決基于社交網(wǎng)絡的團隊組織收益通信比最大化問題,我們設計了專家啟發(fā)式和項目啟發(fā)式兩個算法;關于基于社交網(wǎng)絡的事件組織滿意度最大化問題,我們設計了滿意度增益啟發(fā)式算法和前向檢驗優(yōu)化啟發(fā)式算法;針對基于社交網(wǎng)絡的旅行規(guī)劃效用最大化問題,我們則設計了效用啟發(fā)式算法和相似度啟發(fā)式算法。最后,我們在仿真和真實數(shù)據(jù)集上進行了大量的實... 

【文章來源】：中國科學技術大學安徽省 211工程院校 985工程院校

【文章頁數(shù)】：88 頁

【學位級別】：碩士

【部分圖文】：

圖４．１社交網(wǎng)絡圖模型的最小度的影響??

宄改變最小度的值對我們的實驗結果的影響。我們設定用戶數(shù)（即節(jié)點數(shù)）為??５００，事件數(shù)為５０，冪律指數(shù)為１．５，最小度ｄｗｉ？依次為１，５，１０，１００和２００。??從圖４．１（ａ）中我們可以看出邊的數(shù)量隨著最小度的增大而增加，其原因是顯而易??見的，當最小度增大時，圖的稠密程度無疑會增加。在我們接下來的實驗中，我??們設置＝?１０表不稀疏圖，＝?１〇〇表不稠密圖。我們用Ｂａｓｅ表不基準??算法，用Ｇｒｅｅｄｙ表示滿意度增益啟發(fā)式算法，用ＬＡＧ表示前向檢驗優(yōu)化啟發(fā)式??算法。??？１０＊?？？＊???????????Ｌ３?２８０??ｐ｜?Ｉ?＾??１??６?／／?＊？?Ｈ??，?ｒ?ｍ?Ｉ??Ｅ，?／?＾?ｌ＂??／?ｌｎ?ｉ??／?１００?＇?Ｉ??，／?�！唬�?ＥＬ」ＥＬ?０．．?Ｑ－?５０?ｊ?：?！?ｊ?Ｊ??０?１?６?１０?１００?ａｏｏ?１?６?１０?１００?Ｊ００??０?３０?４０?？０?８０?１００?１３０?１４０?＞４０?１８０?ａｏｏ??????｜ＢＢＢＭ？８ｓ〇ｗｄｙＥＣＬＡＱ?｜?｜ａＢＢ－ｔＢ５ＱｗｒｉｙＬ［ｉＩＡＯ?｜??（ａ）邊－最小度?（ｂ）總滿意度－最小度?（ｃ）后悔率－最小度??圖４．１社交網(wǎng)絡圖模型的最小度的影響??如圖４．１（ｂ）所示，隨著最小度的增大，安排的總體滿意度成比例增加。而我??們的Ｇｒｅｅｄｙ和ＬＡＧ算法明顯比Ｂａｓｅ更優(yōu)。從圖４．１（ｃ）中可以看出

Ｇｒｅｅｄｙ（ｓ）?１．９５?２．１３?２．５４?２．６?３．２２??ＬＡＧ（ｓ）?１．５３?１．５７?１．０８?１．５８?１．４３??安排總體滿意度．從圖４．２（ａ）中，我們可以觀察到在稀疏圖中隨著冪律指數(shù)??從１增加到３．５，由于社交網(wǎng)絡圖Ｇ?＝?（［／，扔變得愈發(fā)稀疏，所以安排的總體滿??意度持續(xù)下降。特別的是，當冪律指數(shù)大于２．５時，Ｇｒｅｅｄｙ和ＬＡＧ兩個算法得??到的結果幾乎沒有差別。所以，在之后的實驗中為了更好得比較兩個算法的差??另ＩＪ，我們將冪律指數(shù)設置為１．５。而在圖４．３（ａ）中，可以看到在稠密圖中安排的??總體滿意度隨著冪律指數(shù)的變化沒有那么明顯。??后悔率．從圖４．２（ｂ）中，我們可以發(fā)現(xiàn)在稀疏圖中，ＬＡＧ算法的后悔率比??Ｇｒｅｅｄｙ算法的后悔率低了?５％到８％左右。而且隨著社交網(wǎng)絡圖愈發(fā)稀疏，其差??距愈發(fā)明顯。不過在稠密圖中，我們發(fā)現(xiàn)兩個算法的后悔率大小差異不大。??運行時間．從表４．３和表４．４中


本文編號：3471043