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

《基于抽象论辩理论的稳定匹配问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据stablematchin2oroblems⑧Auth。f，ssign咖豫堡垒烂Supervisor’ssignature：ExtemalReviewers：ExamingCommitteeChairperson：ExamingCommitteeMembers：Dateoforaldefence：吣9㈣9哪4吣，I㈣0咖9叭2眦Y万方数据浙江大学研究生学位论文独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得逝鎏盘鲎或其他教育机构的学位或证书而使用过

2、的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：铝而谨签字日期：汐／降f,El舌Et学位论文版权使用授权书本学位论文作者完全了解逝姿盘堂有权保留并向国家有关部门或机构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堑鎏盘堂可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：导师签名：签字日期：扫中年￡月6日签字日期沙形年彳月‘日万方数据浙江大学博士学位论文致谢回顾五年的在校学>--j经历，很庆幸自己能够进入

3、语言与认知研究中心这个跨学科的研究平台。初进校时热烈的学术小组活动和讨论还历历在目，不仅听闻各种语言、逻辑、认知现象，还有很多前沿的问题以及跨学科的研究视角和方法。良好的平台为我们的学术研究提供了可靠的保障，丰富的课程和活动也为我们的研究选题提供了更多的参考。入学之后，选题一直是我的困扰，一是因为逻辑底子薄弱，二是不清楚哪个选题具有价值，三是不明确自己的兴趣以及自己能做的研究。作为从英语跨专业到逻辑学的我，很幸运地能在裘江杰老师的课上学习基础逻辑，引领我进入了逻辑的大门。在对选题完全没有方向的时候，非常感谢中心的金立老师和徐慈华老师给予的建议和帮助。尤其感谢我的导师——黄华新教授悉心的

4、教导，使我一步一步往更好的方向前进。从一开始内心的迷茫和不确定，到现在的论文完稿，每一步都离不开黄老师适时的引导和监督。无论是学>-7上还是生活上，我都有很多需要向导师学习的：严以律己，治学严谨，待人真诚，为人谦逊，谈吐幽默。黄老师真正给了我严师慈父的感觉。另外，不得不说导师的课上得非常好，无论是语言学还是逻辑学，这些在一般人眼中很是抽象枯燥的课。却让人觉得这么贴切生活，这么生动有趣。希望我成为高校教师以后，也能让学生喜欢我的课。特别感谢语言与逻辑小组的所有成员。尤其是廖备水老师，引导我进入论辩理论的领域，为我的研究把握方向；耐心地跟我讨论、逐字逐句地为我修改文章。廖老师在学术上的以身

5、作则和对学生的严格要求培养了我做学术的好习惯，也提高了我的学术能力。感谢我的师弟应腾对我学习和生活上的关心与帮助，总是给我家人的感觉。感谢家人这么多年的支持、宽容和体谅，让我顺利走完人生中最重要的一段旅程。最后，谨以此文献给我可爱的宝宝。万方数据浙江大学博士学位论文摘要稳定匹配问题(简称为SM)一直是数学、运筹学、经济学和社会学等领域研究的热点问题。稳定匹配问题通常以矩阵形式出现，因此多以组合数学的方法进行计算，比较依赖数组的顺序特性，适合求解性别优先的单个稳定匹配结果。图论也是求解稳定匹配较常用的理论之一，主要从稳定匹配问题的结构着手，通过求解符合某些特点的二分图来计算稳定匹配结果。

6、无论是从组合数学的角度还是从图论的角度，对稳定匹配问题的研究都缺少系统的形式化刻画，并且求解过程高度抽象。传统的研究无法高效地判断单个配对的状态，因为一个配对必须在某个稳定匹配中才是稳定配对，因此我们必须计算出完整的稳定匹配才能判断单个配对的状态。此外，稳定匹配问题具有非单调性，而已有的研究着重分析新加入的对象以及原有对象所获得的匹配更好或者更差。不能很好地处理稳定匹配问题的动态计算问题。论辩理论可以很好地解决上述问题。稳定匹配问题是一个在冲突的信息中进行选择——评估一一再选择一一再评估的过程，可以用抽象论辩框架对其进行刻画。与组合数学和图论的方法相比，基于论辩的分析更贴合我们的日常推

7、理过程。我们将每一个配对抽象为论证，将对象间互相的偏好度抽象为论证间的二元攻击关系，因此计算稳定匹配时可以从任何一个论证入手，而不必依赖原有的顺序特征。抽象论辩框架有各种语义，而我们可以选择稳定语义和优先语义现有的算法对不同的稳定匹配问题进行求解，如基于回答集编程的方法(ASP)，基于加标的方法(MC)，基于强连通分量的方法(SCC)和基于绝对被驳斥论证的方法(MSR)。论辩语义可以计算出所有稳定匹配结果，并且所求得的结果是无性别差异的(当然，