关于带冲突装箱问题的若干优化算法研究

摘要

装箱问题是一个经典的组合优化问题，早在70年代初就受到不少学者的关注。然而随着计算机科学和生产技术的不断发展，经典的装箱问题远远不能满足人们生产、生活的需要，随之产生了许多新的模型。带冲突的装箱问题即在此背景下应运而生。与经典的装箱问题不同，物品间存在一个冲突关系，且相互冲突的物品不能被放在同一个箱中。本文将要详细讨论三个模型下带冲突装箱问题、带冲突开放式装箱问题和怠惰官僚排序博弈。
　　首先，研究了带冲突装箱问题的三个模型：赋权图下的带冲突装箱问题、有向图下的带冲突装箱问题、在线情形下的带冲突装箱问题。赋权图下带冲突装箱问题即为相互冲突的物品可以装入一个箱中但有容忍度限制。提出改进的：First Kt算法，证明了用经典装箱算法解决此问题都不存在常数界的近似比。有向图下带冲突装箱问题主要研究物品间冲突是单向的，得到了有向图为树状时：First Fit算法近似比为3/2，若采用Next Fit算法时其近似比为1.7。针对完美图的某些特殊子图提出了在线算法LFF且给出了其相应的竞争比。
　　其次，研究了开放式装箱问题的一个变形，即带冲突开放式装箱问题，其为开放式装箱问题和图着色问题的一般化。指出对于一般形式带冲突开放式装箱问题Krst Fit，Next Fit等经典算法不存在常数近似比，因此，给出了一个渐进近似比为3的近似算法IFF。然而，当冲突图限定为二部图时近似比可改进为2。另外，考虑了尺寸有向的开放式装箱问题且证明了FFD的渐进近似比不大于3/2。
　　最后，在怠惰官僚排序博弈中，研究了两个博弈方的三种不同模型。探讨了纳什均衡存在条件且给定了相应的适值函数，针对单台机和多台机两种情况分别设计了伪多项式的动态规划算法，并且证明了敌对的怠惰官僚排序博弈的最坏均衡近似比为1+a然而，自私的怠惰官僚排序博弈和混合的怠惰官僚排序博弈的最坏均衡近似比均不大于1+ a。

目录

封面

声明

中文摘要

英文摘要

目录

第一章绪论

1.1 研究背景

1.2 带冲突装箱问题的研究意义及国内外研究现状

1.3 带冲突开放式装箱问题的研究意义及国内外研究现状

1.4 怠惰官僚排序博弈意义

1.5 文章结构

第二章基础知识

2.1 组合优化简介

2.2 装箱问题的几种算法

2.3 算法评价标准

2.4 各种图定义

第三章带冲突装箱问题

3.1 赋权图下的带冲突装箱问题

3.2 有向图下的带冲突装箱问题

3.3 在线情形下的带冲突装箱问题

3.4 本章小结

第四章带冲突开放式装箱问题

4.1 引言

4.2 一般形式的带冲突开放式装箱问题

4.3 在线算法

4.4 尺寸-有向的开放式装箱问题

4.5 “特定最后物品”约束的开放式装箱问题

4.6 本章小结

第五章怠惰官僚排序博弈

5.1 引言

5.2 模型和符号

5.3 纳什均衡的存在性

5.4 寻找纳什均衡的算法

5.5 最坏均衡近似比

5.6 本章小结

第六章总结与展望

6.1 总结

6.2 展望

参考文献

发表论文和科研情况说明

致谢