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

【文章來(lái)源】：中國(guó)科學(xué)技術(shù)大學(xué)安徽省 211工程院校 985工程院校

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

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

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

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


本文編號(hào)：3471043