文档介绍：,基于分治思想背包问题的并行算法研究湖南大学硕士学位论文堂僮史遣厶丝刍;奎凌霍昱哑丝名壁驱盗;奎直童熬援埴差望僮;信息型堂皇工程堂暄童些刍塑;盐篡扭型堂皇撞苤诠窒握童旦翅;生垒旦赖诠变筌避旦朔生主旦筌避委虽金圭靡;邙继题教援学校代号:学密级:普通号:
㈣圳肼川脚瓻.ⅢⅢⅢ●
毒婚⒈C芸冢凇!D杲饷芎笫视帽臼谌ㄊ椤日期:晁暝耭寥日日期:冢甏踉翴湖南大学学位论文原创性声明学位论文版权使用授权书闟月本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名:本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文属于⒉槐C芡拧期:本学位论文。朐谝陨舷嘤Ψ娇蚰诖颉啊獭作者签导师签
摘要背包问题是一种经典的难问题,目前还无法找到线性时间内求解该问题的算法,由于求解背包问题在优化组合、资本预算、货物装载、削减库存以及信息密码学等领域具有极为重要的应用,因此,降低求解该类问题的计算成本具有重大的理论和现实意义,并引起了各国学者的极大重视。随着并行计算技术的逐步成熟,人们将求解背包问题的重点转向并行算法的研究,当前解决背包问题的并行算法主要分为动态规划法和分治法两种思路,其中动态规划法已经成功运用到了背包问题的并行算法中,并已经涌现出大量的研究成果。不过至今为止分治法主要运用到求解子集和问题中,而基于分治思想设计求解背包问题的并行算法并没有引起同样的关注。因此,在深入研究了并行计算模型和并行分治思想后,本文给出了求解背包问题的串行二表算法和串行三表算法,并创新性的提出了两种基于模型求解背包问题的并行算法即并行三表算法和并行二表算法,并对算法进行理论上的性能分析和比较,其中并行三表算法比并行二表算法占用较少的储存空间,而并行二表算法则是迄今为止求解背包问题算法性能分析中,仅考虑背包物品规模这一个因素成本最优且完全避免内存访问冲突的并行算法。最后,本文分别基于和编程模型对背包问题并行二表算法进行了编程实验,并对实验进行反复测试,从而比较了不同多核平台环境下并行程序运行时间的差异以便分析并行算法的性能。实验结果很好的证明了基于编程模型并行二表程序在减少程序运行时间方面的可行性,且程序表现出较好的加速比和并行效率。关键词:嘲侍猓徊⑿兴惴ǎ环种畏ǎ患糁际酰籈硕士学位论文
,,琾甌簍甆甌,琻,瑃—甤甌,基于分治思想嘲侍獾牟⑿兴惴ㄑ芯...猙.
一