Geek
器官捐赠中的数学：肾脏供受体之间的配对问题
[-]
人类是对称的有机体——包括我们身体内的很多器官也是左右对称。不过我们身体中的许多重要器官都只有一个(比如心脏)或者两个器官都需要才能运行得最好(比如肺)。肾是稀有的例外，你的身体里只要有一个肾就行了。这种情况允许人们靠捐赠而来的肾脏活着，这样捐赠者和受捐者都能靠一个肾脏活下来。
但可惜的是，经常有人需要肾脏移植、也有亲属愿意为他捐赠时却因为组织配对失败(强行将不配对的肾脏移植到病人体内会引起他免疫系统的排斥)而没法做手术。也有一些罕见的个体愿意为陌生人捐赠一个肾脏，因此医学界开始做能将供受体配对的“捐赠链”。
新的问题来了：有这么多移植体和受捐体，怎样才能以最大效率将他们配对呢？在以前这是NP困难问题。现在一些研究人员已经研发出了能解决这一问题的算法。
医院典型的捐赠链模式由一个愿意将肾脏捐给陌生人的不相关捐赠者开启。接着是供受体配对，结局有可能是配对不成功。捐赠链越长，捐赠者和受捐者之间配对成功的可能性越大，受捐者身上出现排斥反应的机会越小。
现在研究人员提出的新算法首先与“整数规划”(integer programming)这个术语有关，这种算法从一个不配对的捐赠者开始计算，然后列出所有可能的项，之后再查看这些可能项与受捐者之间的匹配程度。研究人员还将肾脏捐赠问题归类为旅行商问题(即一名旅行商打算拜访一张城市列表中的所有城市，每座城市只去一次，最后回到出发地，怎样走出最短路线的问题)。使用这种为这位旅行商修正过的算法之后，他们为肾脏捐赠专门研发了一种算法。
他们决定不使用过往数据，即那些已经配对成功了的人的医疗记录。于是他们另外收集了许多潜在的捐赠者和受捐者的数据。一般说来，旅行商算法比循环算法更好，即便捐赠链的潜在长度没有限制，它也能在一个合理的时间内给出答案。
这种算法已经同时配对了几百对供受体，肾脏捐赠问题也不再是我们以前所认为的NP难题了。研究人员的算法已经被医疗体系采用了，这说明学点数学在探讨现实问题上确实有些帮助。
本文译自 arstechnica，由 肌肉桃 编辑发布。