国防科技大学学报
國防科技大學學報
국방과기대학학보
JOURNAL OF NATIONAL UNIVERSITY OF DEFENSE TECHNOLOGY
2013年
6期
132-137
,共6页
肾脏调换%合作博弈%核心%稳定解%圈包装
腎髒調換%閤作博弈%覈心%穩定解%圈包裝
신장조환%합작박혁%핵심%은정해%권포장
kidney exchange%cooperative game%core%stable solution%cycle packing
用于器官移植的肾脏处于严重的短缺状态。为缓解这一问题，越来越多的国家开始实施各种形式的肾脏调换计划。肾脏调换问题一般被建模为一个合作博弈（Kidney Exchange game，KE）。其中的局中人为病人及与其配型失败的捐赠者所构成的二元组。现实中不乏拥有多个配型捐赠者失败的病人。定义了多捐赠者肾脏调换博弈（Multi-Donor Kidney Exchange game，MDKE），分析了其可行解及稳定解的结构，证明了捐赠多颗肾脏无益于参与稳定调换，将 TTC 算法、KE 稳定解的 NP 难解性以及最大覆盖稳定解的不可近似性拓展到 MDKE。实验表明引入 MDKE 效果显著。
用于器官移植的腎髒處于嚴重的短缺狀態。為緩解這一問題，越來越多的國傢開始實施各種形式的腎髒調換計劃。腎髒調換問題一般被建模為一箇閤作博弈（Kidney Exchange game，KE）。其中的跼中人為病人及與其配型失敗的捐贈者所構成的二元組。現實中不乏擁有多箇配型捐贈者失敗的病人。定義瞭多捐贈者腎髒調換博弈（Multi-Donor Kidney Exchange game，MDKE），分析瞭其可行解及穩定解的結構，證明瞭捐贈多顆腎髒無益于參與穩定調換，將 TTC 算法、KE 穩定解的 NP 難解性以及最大覆蓋穩定解的不可近似性拓展到 MDKE。實驗錶明引入 MDKE 效果顯著。
용우기관이식적신장처우엄중적단결상태。위완해저일문제，월래월다적국가개시실시각충형식적신장조환계화。신장조환문제일반피건모위일개합작박혁（Kidney Exchange game，KE）。기중적국중인위병인급여기배형실패적연증자소구성적이원조。현실중불핍옹유다개배형연증자실패적병인。정의료다연증자신장조환박혁（Multi-Donor Kidney Exchange game，MDKE），분석료기가행해급은정해적결구，증명료연증다과신장무익우삼여은정조환，장 TTC 산법、KE 은정해적 NP 난해성이급최대복개은정해적불가근사성탁전도 MDKE。실험표명인입 MDKE 효과현저。
The kidney for transplantation is in serious shortage.To alleviate this problem,more and more countries have started various kidney exchange programs.The kidney exchange problem (KE)is generally modeled as a cooperative game.Each player represents an incompatible patient-donor pair.A patient may have more than one incompatible donor in reality.In light of this,the multi-donor kidney exchange game (MDKE)was defined.The structures of MDKE's feasible solutions and stable solutions were studied.It was proved that donating multiple kidneys is useless in joining in a better stable solution.Furthermore,the TTC algorithm,the NP-hardness of a stable solution and the inapproximability of a maximum cover stable solution of KE were extended to MDKE.Experiments show the effectiveness of MDKE.
