基于分治思想0-1背包問題的并行算法研究.pdf

1、0-1背包問題是一種經(jīng)典的NP難問題，目前還無法找到線性時(shí)間內(nèi)求解該問題的算法，由于求解0-1背包問題在優(yōu)化組合、資本預(yù)算、貨物裝載、削減庫存以及信息密碼學(xué)等領(lǐng)域具有極為重要的應(yīng)用，因此，降低求解該類問題的計(jì)算成本具有重大的理論和現(xiàn)實(shí)意義，并引起了各國(guó)學(xué)者的極大重視。
　　 隨著并行計(jì)算技術(shù)的逐步成熟，人們將求解0-1背包問題的重點(diǎn)轉(zhuǎn)向并行算法的研究，當(dāng)前解決0-1背包問題的并行算法主要分為動(dòng)態(tài)規(guī)劃法和分治法兩種思路，其中動(dòng)態(tài)規(guī)

2、劃法已經(jīng)成功運(yùn)用到了0-1背包問題的并行算法中，并已經(jīng)涌現(xiàn)出大量的研究成果。不過至今為止分治法主要運(yùn)用到求解子集和問題中，而基于分治思想設(shè)計(jì)求解0-1背包問題的并行算法并沒有引起同樣的關(guān)注。因此，在深入研究了PRAM并行計(jì)算模型和并行分治思想后，本文給出了求解0-1背包問題的串行二表算法和串行三表算法，并創(chuàng)新性的提出了兩種基于EREW PRAM模型求解0-1背包問題的并行算法即并行三表算法和并行二表算法，并對(duì)算法進(jìn)行理論上的性能分析和比

3、較，其中并行三表算法比并行二表算法占用較少的儲(chǔ)存空間，而并行二表算法則是迄今為止求解0-1背包問題算法性能分析中，僅考慮背包物品規(guī)模這一個(gè)因素成本最優(yōu)且完全避免內(nèi)存訪問沖突的并行算法。
　　 最后，本文分別基于OpenMP和MPI+OpenMP編程模型對(duì)0-1背包問題并行二表算法進(jìn)行了編程實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)進(jìn)行反復(fù)測(cè)試，從而比較了不同多核平臺(tái)環(huán)境下并行程序運(yùn)行時(shí)間的差異以便分析并行算法的性能。實(shí)驗(yàn)結(jié)果很好的證明了基于OpenMP編程