基于序列的物品分配问题的算法研究

发布时间：2021-01-07 03:41

　　基于序列的分配方式是一个简单且应用广泛的资源分配方式。分配机构需要把一系列不可分割的物品分配给多个代理人,代理人对物品有偏好,分配过程是代理人根据给出的序列依次选择物品且只能选择剩余的物品。该分配方式不具备防策略性,即代理人可以通过谎报自己对物品的偏好来获得更好的效用。因此研究者提出了基于序列的物品分配的操纵问题,研究代理人如何采取策略,给出一个使自己效益达到最大的物品偏好。该问题在只有两个代理人（一个是操控者,一个是非操控者）时是多项式可解的,也被证明了当代理人个数为输入的时候是NP难的。那么对于常数个代理人,哪怕只有三个代理人的时候,该问题的计算复杂性并不清楚,成为了一个重要的公开难题。本文最重要的一项贡献就是解决了这个公开难题,给出了一个算法,该算法在任何常数个代理人时都是多项式运行时间。在算法设计中,我们提出了两个重要的概念:关键问题和不变性。关键问题与原问题有相同的最优解,但是关键问题可以利用贪心算法快速解决。解决原始问题则可以转换成寻找与原始问题具有相同最优解的关键问题。我们定义了问题的支配关系,提供了搜索关键问题的空间,与原始问题有相同最优解的关键问题一定在原始问题支配的... 

【文章来源】：电子科技大学四川省 211工程院校 985工程院校 教育部直属院校

【文章页数】：65 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第一章 绪论
    1.1 研究工作的背景与意义
    1.2 基于序列的物品分配问题的国内外研究历史与现状
    1.3 本文的主要贡献与创新
    1.4 本论文的结构安排
第二章 基于序列的物品分配模型
    2.1 代理人的偏好
    2.2 代理人的序列
    2.3 基于序列的物品分配模型的操纵问题
    2.4 本章小结
第三章 基于序列的物品分配问题模型的精确算法
    3.1 最优解问题介绍
    3.2 关键问题
    3.3 暴力搜索
    3.4 不变性
    3.5 动态规划算法
        3.5.1 动态规划介绍
        3.5.2 最优解问题的动态规划算法
    3.6 记忆化搜索
    3.7 本章小结
第四章 基于序列的物品分配问题模型的近似算法
    4.1 近似算法介绍
    4.2 基于贪心策略的近似算法
    4.3 近似率
    4.4 近似率的紧致性
    4.5 本章小结
第五章 实验测试
    5.1 实验准备
        5.1.1 对比算法介绍
        5.1.2 实验数据
        5.1.3 参数、环境和指标
    5.2 暴力搜索和记忆化搜索的对比
        5.2.1 平衡序列的实验结果
        5.2.2 极端序列的实验结果
    5.3 近似算法实验
    5.4 本章小结
第六章 全文总结与展望
    6.1 全文总结
    6.2 后续工作展望
致谢
参考文献
攻读硕士学位期间取得的成果



本文编号：2961837