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

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

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

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