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

病人捐贈(zèng)者對(duì)PDP-1

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

本文編號(hào)：2705256