学位论文 > 优秀研究生学位论文题录展示

一个执行率为2.7687的两维调和算法

作　者: 韩鑫
导　师: 曹桂琴；郭禾
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 装箱问题调和算法渐进最坏性能比 NP困难问题近似算法调度问题在线算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2002年
下　载: 36次
引　用: 0次
阅　读: 论文下载

内容摘要

本文研究两维空间上的在线(On-line)装箱问题(Bin packing problem)。装箱问题是计算机科学理论和组合优化领域的基本问题之一。简单的说，两维空间上的在线装箱问题就是，把由矩形项目组成的输入队列，用一种在线方式，装入固定形状大小的箱子里，求最少需要多少个箱子。在现实中，它有很多实际的应用。例如，调度问题，内存分配，新闻的排版问题，卡车的装货问题，通信网络中包的路由问题，以及大规模集成电路(VLSI)芯片设计问题等。因此，装箱问题的研究有它的实际应用价值。众所周知，它是一个NP-困难问题。因此，探求该问题的近似解是研究的主要目的。目前，对该问题的研究有各种算法，主要有Harmonic和ROUND算法，本文针对Harmonic和ROUND算法存在的问题，提出一种算法RTDH(Refined Two Dimensional HARMONIC)，做了相应的分析，并且给出了该算法的最坏性能比是2.7687的证明，这个结果刷新了目前最好的结果2.85958。

全文目录

前言  6-7
第一章简介  7-11
  1．1 问题的定义  7-8
  1．2 最坏性能比的定义  8-9
  1．3 研究现状  9
  1．4 本文的研究  9-11
第二章算法描述  11-20
  2．1 项目的分类  11-14
  2．2 RTDH算法基本描述  14
  2．3 A-项目的装箱处理  14-16
    2．3．1 A-项目中类型1的处理方法  15-16
  2．4 较大项目的装箱  16-20
    2．4．1 α-，β-，γ-和δ-项目装箱算法  16-20
第三章算法的分析及其最坏性能比的证明  20-55
  3．1 关于不同类型项目的H-值  21
  3．2 关于不同类型项目的H╱S值  21-26
  3．3 最坏性能比的上界  26-55
第四章总结与展望  55-56
致谢  56-57
参考文献  57

一个执行率为2.7687的两维调和算法

内容摘要

全文目录

相似论文