肾脏交换问题的参数算法和复杂度研究

论文摘要

肾脏交换是指拥有不相容供体的患者互相交换供体肾脏以获得相容肾脏的一种供体肾移植的方法。自1986年首次提出以来,因为在这种方式下患者有更多的机会获得与之相容的肾脏,随着肾脏交换的普及,越来越多的肾脏病人得以救治。随着时代的发展和科学技术的不断进步,参与肾脏交换的患者规模越来越大,这导致寻找患者与捐赠者之间的最优匹配变得愈发困难。事实上,肾脏交换的核心问题是在肾脏交换病人捐赠者兼容性图中找出最大点不相交环和链的集合,这是一个NP难问题。出于某些原因,环上的肾脏移植手术必须同时进行,而链上的肾脏移植手术可以不同时进行。由于人力资源的限制,通常研究者们会限制环和链的最大长度,链的长度往往比环的长度大的多。本文主要从精确算法和参数算法的角度对上述问题进行研究。首先,本文研究了经典肾脏交换模型下的两个基本计算问题——环和链长度带约束的肾脏交换问题和长度不带约束的肾脏交换问题,分别设计参数算法,并分析时间复杂度。特别的,本文给出了第一个O（2nn3）时间的精确算法,此算法是基于动态规划和子集卷积的单精度指数时间算法,同时也是一个框架型算法,适用于一类型肾脏交换问题及其变种问题的求解。对于无长度约束的肾脏交换问题,本文证明了以兼容性图中顶点“类型”数为参数是参数可算的,并给出一个O（20（θ2）θ2θ2+n（n+m））时间的FPT算法。随着时代的发展,肾脏交换问题有了新的需求,本文还对这一新需求进行建模,建立肾脏交换问题的新模型,并在新模型下进行NP性分析和算法求解。本文证明了新模型下的第一类肾脏交换问题和第二类肾脏交换问题是NP-完全的,并设计了两个参数算法,同时分析时间复杂度。第一个参数算法以待救治病人总数为参数,是基于动态规划和彩色编码技术的随机参数算法。第二个参数算法以救治病人数L为参数,也是通过动态规划和彩色编码技术得到的随机参数算法。

论文目录

文章来源

类型: 硕士论文

作者: 王泫钡

导师: 肖鸣宇

关键词: 肾脏交换问题,环和链,最大长度限制,参数算法,时间复杂度分析

来源: 电子科技大学

年度: 2019

分类: 基础科学,医药卫生科技

专业: 数学,泌尿科学

单位: 电子科技大学

分类号: R692;O221.3

总页数: 70

文件大小: 2515K

下载量: 17

相关论文文献

• [1].职教校企合作不对等交换问题实证研究[J]. 中国职业技术教育 2015(35)
• [2].关于线性变换的可交换问题的一些讨论[J]. 北华大学学报(自然科学版) 2010(04)
• [3].土地自由交易是核心[J]. 中国企业家 2012(23)
• [4].关于求导次序的可交换问题[J]. 高等函授学报(自然科学版) 2008(02)
• [5].基于活动重叠的随机活动网络时间费用模型仿真研究[J]. 系统仿真学报 2012(03)
• [6].史密森学会与晚清时期中美两国间出版物交换问题探析[J]. 历史教学问题 2016(02)
• [7].工作流环境下组件的开发[J]. 电子设计工程 2012(22)
• [8].在VC++中如何与VFP进行数据通迅[J]. 福建电脑 2008(01)
• [9].MIS设计中设计模式的应用[J]. 软件导刊 2009(12)
• [10].宁夏建立城乡要素平等交换机制研究[J]. 新丝路(下旬) 2015(10)
• [11].高职教育校企合作促进法中交换制度的建立——“社会交换”理论对校企合作立法的启示[J]. 职教论坛 2013(05)
• [12].特征交换框架下奇异特征的处理[J]. 计算机工程 2011(01)
• [13].XML数据访问与数据传输优化[J]. 科学之友 2011(16)
• [14].交换的复杂性问题研究——本质、模型及意义[J]. 自然辩证法研究 2013(02)
• [15].对C语言函数参数传递的探讨——以交换问题为例[J]. 通化师范学院学报 2013(04)
• [16].实现中国梦 基础在“三农”——把农村建设成为农民幸福生活的美好家园[J]. 人民论坛 2013(30)
• [17].学习对象的整体教育观——再利用问题之未来方向[J]. 远程教育杂志 2013(02)

标签：肾脏交换问题论文;  环和链论文;  最大长度限制论文;  参数算法论文;  时间复杂度分析论文;