【摘要】：腎臟交換是指擁有不相容供體的患者互相交換供體腎臟以獲得相容腎臟的一種供體腎移植的方法。自1986年首次提出以來,因?yàn)樵谶@種方式下患者有更多的機(jī)會獲得與之相容的腎臟,隨著腎臟交換的普及,越來越多的腎臟病人得以救治。隨著時代的發(fā)展和科學(xué)技術(shù)的不斷進(jìn)步,參與腎臟交換的患者規(guī)模越來越大,這導(dǎo)致尋找患者與捐贈者之間的最優(yōu)匹配變得愈發(fā)困難。事實(shí)上,腎臟交換的核心問題是在腎臟交換病人捐贈者兼容性圖中找出最大點(diǎn)不相交環(huán)和鏈的集合,這是一個NP難問題。出于某些原因,環(huán)上的腎臟移植手術(shù)必須同時進(jìn)行,而鏈上的腎臟移植手術(shù)可以不同時進(jìn)行。由于人力資源的限制,通常研究者們會限制環(huán)和鏈的最大長度,鏈的長度往往比環(huán)的長度大的多。本文主要從精確算法和參數(shù)算法的角度對上述問題進(jìn)行研究。首先,本文研究了經(jīng)典腎臟交換模型下的兩個基本計(jì)算問題——環(huán)和鏈長度帶約束的腎臟交換問題和長度不帶約束的腎臟交換問題,分別設(shè)計(jì)參數(shù)算法,并分析時間復(fù)雜度。特別的,本文給出了第一個O(2nn3)時間的精確算法,此算法是基于動態(tài)規(guī)劃和子集卷積的單精度指數(shù)時間算法,同時也是一個框架型算法,適用于一類型腎臟交換問題及其變種問題的求解。對于無長度約束的腎臟交換問題,本文證明了以兼容性圖中頂點(diǎn)“類型”數(shù)為參數(shù)是參數(shù)可算的,并給出一個O(20(θ2)θ2θ2+n(n+m))時間的FPT算法。隨著時代的發(fā)展,腎臟交換問題有了新的需求,本文還對這一新需求進(jìn)行建模,建立腎臟交換問題的新模型,并在新模型下進(jìn)行NP性分析和算法求解。本文證明了新模型下的第一類腎臟交換問題和第二類腎臟交換問題是NP-完全的,并設(shè)計(jì)了兩個參數(shù)算法,同時分析時間復(fù)雜度。第一個參數(shù)算法以待救治病人總數(shù)為參數(shù),是基于動態(tài)規(guī)劃和彩色編碼技術(shù)的隨機(jī)參數(shù)算法。第二個參數(shù)算法以救治病人數(shù)L為參數(shù),也是通過動態(tài)規(guī)劃和彩色編碼技術(shù)得到的隨機(jī)參數(shù)算法。
【圖文】：

病人捐贈者對PDP-1

PDP-1 和 PDP-2 進(jìn)行交換的過程，他們是環(huán)式交換，構(gòu)成一個 2 元環(huán)：圖 2-2 兩個病人捐贈者對腎臟交換示意圖由圖2-2，，PDP-1的捐贈者與PDP-2的病人相容，同時，PDP-2的捐贈者與PDP-1的病人相容，因此這兩個病人捐贈者對可以互相交換腎臟，從而使得病人 1 和病人 2 都可以得到救治，這就是腎臟交換的環(huán)式交換過程，特別的，這是這個環(huán)式交換的大小為 2，是 2 元環(huán)式交換。隨著越來越多的病人捐贈者對的參加，環(huán)式交換的長度也會不斷增加[69]，又因?yàn)榫栀浾邲]有法律義務(wù)捐贈自己的腎臟
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：R692;O221.3

【參考文獻(xiàn)】

相關(guān)期刊論文 前5條

1 蔣生元;;南亞成為“賣腎集市” 全球最大腎移植黑市探秘[J];世界博覽;2015年21期

2 高嘉元;嚴(yán)玉澄;;代謝組學(xué)技術(shù)在腎臟病研究中的應(yīng)用[J];中國中西醫(yī)結(jié)合腎病雜志;2011年05期

3 唐策善;梁維發(fā);;二分圖最大匹配問題的分布式算法[J];計(jì)算機(jī)工程與應(yīng)用;1990年Z1期

4 戴一奇;求最大匹配的一個新算法[J];數(shù)學(xué)研究與評論;1988年04期

5 劉毅;蔡曉青;張明慧;鄭塵非;徐玉蘭;王綠萍;梅曉蓉;;溫州市2002-2011年維持性血液透析患者透析登記報(bào)告及分析[J];中華腎臟病雜志;2013年09期

相關(guān)碩士學(xué)位論文 前1條

1 張偉超;基于MFI理論的橋梁動態(tài)稱重系統(tǒng)移動荷載識別研究[D];湖南大學(xué);2018年

本文編號：2705256