基于抽象论辩理论的稳定匹配问题研究

发布时间：2017-07-30 22:00

  本文关键词：基于抽象论辩理论的稳定匹配问题研究

  更多相关文章： 稳定匹配问题 稳定婚姻问题 稳定室友问题 抽象论辩理论 论辩框架

【摘要】：稳定匹配问题(简称为SM)一直是数学、运筹学、经济学和社会学等领域研究的热点问题。稳定匹配问题通常以矩阵形式出现,因此多以组合数学的方法进行计算,比较依赖数组的顺序特性,适合求解性别优先的单个稳定匹配结果。图论也是求解稳定匹配较常用的理论之一,主要从稳定匹配问题的结构着手,通过求解符合某些特点的二分图来计算稳定匹配结果。无论是从组合数学的角度还是从图论的角度,对稳定匹配问题的研究都缺少系统的形式化刻画,并且求解过程高度抽象。传统的研究无法高效地判断单个配对的状态,因为一个配对必须在某个稳定匹配中才是稳定配对,因此我们必须计算出完整的稳定匹配才能判断单个配对的状态。此外,稳定匹配问题具有非单调性,而已有的研究着重分析新加入的对象以及原有对象所获得的匹配更好或者更差,不能很好地处理稳定匹配问题的动态计算问题。论辩理论可以很好地解决上述问题。稳定匹配问题是一个在冲突的信息中进行选择——评估——再选择——再评估的过程,可以用抽象论辩框架对其进行刻画。与组合数学和图论的方法相比,基于论辩的分析更贴合我们的日常推理过程。我们将每一个配对抽象为论证,将对象间互相的偏好度抽象为论证间的二元攻击关系,因此计算稳定匹配时可以从任何一个论证入手,而不必依赖原有的顺序特征。抽象论辩框架有各种语义,而我们可以选择稳定语义和优先语义现有的算法对不同的稳定匹配问题进行求解,如基于回答集编程的方法(ASP),基于加标的方法(MC),基于强连通分量的方法(SCC)和基于绝对被驳斥论证的方法(MSR)。论辩语义可以计算出所有稳定匹配结果,并且所求得的结果是无性别差异的(当然,对于稳定婚姻问题,男士最优和女士最优的结果也在所有的稳定匹配中)。我们可以通过提高论辩语义计算效率来提高稳定匹配的计算效率,例如,将整个论辩框架划分为多个更小的SCC,分别计算每个SCC,然后合并各个部分的语义；或者将绝对被驳斥论证——被基外延攻击的论证从计算过程中删除。我们可以用论辩争议树来判断单个配对是否稳定,是否属于所有稳定匹配。当稳定匹配问题发生变化时,例如增加匹配对象、改变偏好列表、删除配对,通过论辩框架可以对匹配结果的数量改变和内容变化进行分析,并且用论辩语义的动态计算对稳定匹配问题进行比较高效的重新求解。我们首先介绍抽象论辩理论,然后用抽象论辩框架对稳定婚姻和稳定室友问题进行了刻画：包括带完整全序偏好列表的经典稳定婚姻问题sm和经典稳定室友问题sr,带完整非全序偏好列表(又称偏序列表或无差别列表)的稳定婚姻问题smt和稳定室友问题srt,带全序不完整偏好列表的稳定婚姻问题smi和稳定室友问题sri,带非全序不完整偏好列表的稳定婚姻问题smti和稳定室友问题srti。对稳定匹配问题进行论辩形式化后,我们用论辩语义证明的方法来判断单个配对的状态；然后用稳定语义来求解sm、smt、smi、smti问题,用优先语义求解sr、 srt、sri、srti问题。最后在静态求解的基础上根据论辩动态性的研究对稳定匹配问题的动态性进行分析,主要介绍基于划分的动态计算方法和基于论证状态的计算方法。通过分析,我们证明稳定语义和优先语义的求解结果就是我们所要求取的相应的稳定匹配结果,并且如果稳定匹配结果存在,我们总是能用相应的论辩语义进行求解。对于某个配对,如果该配对相应的论证没有被轻信证成(在某个语义下),则该论证不属于任何外延,该配对也不属于任何稳定匹配。稳定匹配问题的论辩框架有其自身的特点——每个论证都与其他论证有直接或间接的关系,使得我们无法很好地划分SCC,并且使用基于加标的方法也会延长判断的过程,因此,我们用基于扩展的MSR方法：从每一个论证出发,尝试将其扩展为最大可相容集合。对于稳定匹配问题的动态性研究,我们首先以稳定婚姻问题为例分析了配对增加或删除以及偏好列表中满意度改变对稳定匹配结果造成的影响；然后介绍基于划分的动态计算方法,并在此基础上提出基于论证状态的方法,进一步缩小需要重新计算的范围。
【关键词】：稳定匹配问题 稳定婚姻问题 稳定室友问题 抽象论辩理论 论辩框架
【学位授予单位】：浙江大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：B81-0
【目录】：

• 致谢5-6
• 摘要6-8
• Abstract8-16
• 第1章 引言16-28
• 1.1 匹配问题19-21
• 1.2 已有研究存在的问题21-26
• 1.3 主要内容26-28
• 第2章 论辩理论28-43
• 2.1 基于扩展的定义29-31
• 2.2 基于加标的定义31-35
• 2.3 论辩语义的计算35-41
• 2.3.1 基于加标的方法35-38
• 2.3.2 基于ASP的算法38-40
• 2.3.3 基于SCC的算法40
• 2.3.4 基于MSR的算法40-41
• 2.4 论辩框架的动态性41-43
• 第3章 稳定匹配问题的论辩框架43-67
• 3.1 稳定婚姻问题的论辩框架43-57
• 3.1.1 sm的论辩框架44-50
• 3.1.2 smt的论辩框架50-52
• 3.1.3 smi的论辩框架52-55
• 3.1.4 smti的论辩框架55-57
• 3.2 稳定室友问题的论辩框架57-67
• 3.2.1 sr的论辩框架57-62
• 3.2.2 srt的论辩框架62-63
• 3.2.3 sri的论辩框架63-64
• 3.2.4 srti的论辩框架64-67
• 第4章 稳定匹配问题的论辩语义计算67-95
• 4.1 单个配对的稳定性判断67-77
• 4.1.1 稳定配对69-73
• 4.1.2 固定配对73-77
• 4.2 稳定匹配的求解77-95
• 4.2.1 基于矩阵旋转的方法77-79
• 4.2.2 基于MSR的计算方法79-90
• 4.2.3 基于无冲突集合扩展的方法90-95
• 第5章 稳定婚姻问题的论辩动态性95-106
• 5.1 sm问题：增加或删除配对95-98
• 5.2 sm问题：改变偏好列表98-101
• 5.3 匹配问题的动态计算101-106
• 5.3.1 基于划分的方法101-102
• 5.3.2 基于论证状态的方法102-106
• 第6章 结语106-108
• 6.1 内容回顾106
• 6.2 创新点与不足106-108
• 参考文献108-114
• 作者简历114

【相似文献】

中国重要会议论文全文数据库 前1条

1 钟仁明;何垠波;李晓玉;陈林;姜庆丰;柏森;许峰;;IGRT放疗中匹配结果与放疗精度[A];2007第六届全国放射肿瘤学学术年会论文集[C];2007年

中国硕士学位论文全文数据库 前1条

1 马素华;同构对称发布/订阅系统中Top-k算法的研究与实现[D];东北大学;2012年

，

本文编号：596207