一種基于MapReduce模型的并行化TSP算法研究.pdf

1、TSP問(wèn)題（Traveling Salesman Problem），即旅行商問(wèn)題，是數(shù)學(xué)領(lǐng)域里面組合優(yōu)化問(wèn)題中被廣泛研究的著名問(wèn)題之一。TSP問(wèn)題在學(xué)術(shù)研究和實(shí)際生產(chǎn)需求中十分重要，同時(shí)在物理學(xué)、生物學(xué)和計(jì)算機(jī)科學(xué)等領(lǐng)域有著廣泛的應(yīng)用。TSP問(wèn)題是NP-完全問(wèn)題中很有挑戰(zhàn)性的一個(gè)問(wèn)題。目前對(duì)于TSP問(wèn)題的研究多是在單一物理機(jī)上使用順序執(zhí)行的啟發(fā)式算法求得近似解，也有少量研究初步在Hadoop平臺(tái)上基于MapReduce模型實(shí)現(xiàn)了一些諸如

2、遺傳算法和蟻群算法等新型啟發(fā)式算法，但都仍然存在不能保證算法的質(zhì)量、運(yùn)行不穩(wěn)定等問(wèn)題。本論文探索通過(guò)并行MapReduce模型高效解決TSP問(wèn)題。
　　根據(jù)以上存在的問(wèn)題，本文提出基于MapReduce模型的并行化迭代K-OPT算法：首先，本文提出一種基于MapReduce模型并行化求解最小生成樹(shù)算法，并用于構(gòu)造TSP初始化路徑；該算法充分應(yīng)用MapReduce模型中可以很容易對(duì)數(shù)據(jù)進(jìn)行排序的特點(diǎn)對(duì)圖中的所有邊的權(quán)重進(jìn)行排序，結(jié)合

3、并行化的克魯斯卡爾算法求得最小生成樹(shù)；再將其作為Christofides算法輸入求得一條可以用于迭代求解TSP問(wèn)題算法的初始化路徑，其中Christofides算法是目前TSP問(wèn)題中最好的近似算法之一，其近似比為1.5-opt。其次，以初始路徑為基礎(chǔ)，提出一種基于MapReduce模型并行化的K-OPT算法，算法利用MapReduce模型可以充分并行化運(yùn)算的特點(diǎn)，將map函數(shù)用于路徑的分發(fā)和圖的讀取，reduce函數(shù)用于問(wèn)題的求解，從集

4、群中多節(jié)點(diǎn)求得的不同迭代解中篩選出最優(yōu)解，將其作為下一次迭代的輸入。然后，通過(guò)對(duì)節(jié)點(diǎn)數(shù)規(guī)模較小的完全圖進(jìn)行基于MapReduce模型所有路徑的窮舉和對(duì)一些TSPLIB中的實(shí)例進(jìn)行基于MapReduce模型的大規(guī)模隨機(jī)路徑生成以及并行化去冗余操作，然后進(jìn)行一定的統(tǒng)計(jì)和特征分析，本文首次提出了截?cái)鄰V義Beta分布Truncated Generalized Beta distribution(TGB)作為T(mén)SP問(wèn)題中最優(yōu)路徑的概率密度函數(shù)，并