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

发布时间：2020-06-09 21:05

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

病人,血型

病人捐赠者对PDP-1

示意图,病人,肾脏,环式

PDP-1 和 PDP-2 进行交换的过程，他们是环式交换，构成一个 2 元环：图 2-2 两个病人捐赠者对肾脏交换示意图由图2-2，，PDP-1的捐赠者与PDP-2的病人相容，同时，PDP-2的捐赠者与PDP-1的病人相容，因此这两个病人捐赠者对可以互相交换肾脏，从而使得病人 1 和病人 2 都可以得到救治，这就是肾脏交换的环式交换过程，特别的，这是这个环式交换的大小为 2，是 2 元环式交换。随着越来越多的病人捐赠者对的参加，环式交换的长度也会不断增加[69]，又因为捐赠者没有法律义务捐赠自己的肾脏
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：R692;O221.3

【参考文献】