Optimal kidney exchange
इष्टतम गुर्दा विनिमय (ओ. के. ई.) एक अनुकूलन समस्या है जिसका सामना गुर्दा युग्मित दान कार्यक्रमों (जिसे गुर्दा विनिमय कार्यक्रम भी कहा जाता है) द्वारा किया जाता है। इस तरह के कार्यक्रमों में रोगी-दाता जोड़े के बड़े डेटाबेस होते हैं, जहां दाता रोगी की मदद करने के लिए एक गुर्दा दान करने के लिए तैयार होता है, लेकिन चिकित्सा असंगतता के कारण ऐसा नहीं कर सकता है। केंद्र ऐसे जोड़े के बीच आदान-प्रदान की व्यवस्था करने का प्रयास करते हैं। उदाहरण के लिए, जोड़ी ए में दाता जोड़ी बी में रोगी को दान करता है, जोड़ी बी में दाता जोड़ी सी में रोगी को दान करता है, और जोड़ी सी में दाता जोड़ी ए में रोगी को दान करता है। ओ. के. ई. समस्या का उद्देश्य इस तरह के आदान-प्रदान की एक इष्टतम व्यवस्था खोजना है। "इष्टतम" का आम तौर पर मतलब है कि प्रत्यारोपण की संख्या यथासंभव अधिक है, लेकिन अन्य उद्देश्य भी हो सकते हैं। इस अनुकूलन समस्या में एक महत्वपूर्ण बाधा यह है कि एक दाता केवल तभी गुर्दा देता है जब उसके रोगी को एक संगत गुर्दा प्राप्त होता है, ताकि कोई भी जोड़ी भाग लेने से गुर्दा न खोए। इस आवश्यकता को कभी-कभी व्यक्तिगत तर्कसंगतता कहा जाता है। ओ. के. ई. समस्या के कई रूप हैं, जो प्रत्येक विनिमय के स्वीकृत आकार, वस्तुनिष्ठ कार्य और अन्य कारकों में भिन्न होते हैं। परिभाषाएँ इनपुट ओ. के. ई. के एक उदाहरण को आमतौर पर निर्देशित ग्राफ के रूप में वर्णित किया जाता है। प्रत्येक नोड एक रोगी-दाता जोड़ी का प्रतिनिधित्व करता है। जोड़ी ए से जोड़ी बी तक एक निर्देशित चाप का मतलब है कि जोड़ी ए में दाता जोड़ी बी में रोगी के साथ चिकित्सकीय रूप से संगत है (संगतता दाता और रोगी के रक्त के प्रकार के साथ-साथ उनके रक्त में विशेष एंटीजन जैसे अन्य कारकों के आधार पर निर्धारित की जाती है)। संगतता ग्राफ में एक निर्देशित चक्र एक संभावित विनिमय का प्रतिनिधित्व करता है। आकार 2 का एक निर्देशित चक्र (जैसे। ए-> बी-> ए) एक संभावित जोड़ीदार विनिमय का प्रतिनिधित्व करता है-जोड़े की एक जोड़ी के बीच एक विनिमय। ओ. के. ई. का एक अधिक सामान्य संस्करण दूसरे प्रकार के नोड्स पर भी विचार करता है, जो परोपकारी दाताओं का प्रतिनिधित्व करते हैं-दाता जो एक रोगी के साथ जोड़े नहीं हैं, और किसी भी संगत रोगी को गुर्दा दान करने के लिए तैयार हैं। अल्ट्रूस्टिक डोनर नोड्स में केवल आउटगोइंग आर्क्स होते हैं। परोपकारी दाताओं के साथ, न केवल चक्रों के साथ, बल्कि जंजीरों के साथ भी आदान-प्रदान की व्यवस्था करना संभव है, जो एक परोपकारी दाता से शुरू होता है। ग्राफ में चापों में भार हो सकते हैं, जैसे कि शामिल प्रत्यारोपण की सफलता की संभावना। उनकी प्राथमिकताएँ भी हो सकती हैं, जैसे कि निर्धारित। चिकित्सा की तात्कालिकता से या जब तक रोगी प्रत्यारोपण कतार में प्रतीक्षा कर चुका होता है। आउटपुट एक ओ. के. ई. का आउटपुट जोड़ीदार-असंगत निर्देशित चक्रों का एक समूह है (और संभवतः निर्देशित श्रृंखलाएं, यदि परोपकारी दाता उपलब्ध हैं)। ओ. के. ई. में सबसे सरल उद्देश्य गुर्दा प्राप्त करने वाले रोगियों की संख्या को अधिकतम करना है। अन्य सामान्य उद्देश्य हैंः गुर्दे के आदान-प्रदान के भारित योग को अधिकतम करनाः ग्राफ में प्रत्येक किनारे का एक वजन होता है, और लक्ष्य एक ऐसा आदान-प्रदान खोजना है जो विनिमय में उपयोग किए जाने वाले सभी किनारों पर भार के योग को अधिकतम करता है। प्रत्यारोपण उम्मीदवारों की जीवन प्रत्याशा को अधिकतम करना, या उनकी गुणवत्ता-समायोजित जीवन प्रत्याशा। अनियंत्रित चक्र की लंबाई प्रारंभ में, विनिमय चक्रों की लंबाई पर किसी भी सीमा के बिना समस्या का अध्ययन किया गया था। रोथ, सोनमेज़ और अनवर ने पेरेटो-इष्टतम और प्रोत्साहन-संगत तरीके से विनिमय चक्र खोजने के लिए शीर्ष व्यापार चक्र तंत्र के विस्तार के आधार पर एक तंत्र प्रस्तुत किया। अब्राहम, ब्लम और सैंडहोल्म बताते हैं कि, असीम चक्र लंबाई के साथ, बहुपद समय में अधिकतम-कार्डिनलिटी और अधिकतम-वजन का आदान-प्रदान पाया जा सकता है। उदाहरण के लिए, मूल निर्देशित ग्राफ G को देखते हुए, एक अधिकतम-कार्डिनलिटी विनिमय का पता लगाने के लिए, एक दिशाहीन द्विदलीय ग्राफ H (X + Y, E) का निर्माण करें जिसमेंः G में प्रत्येक जोड़ी j में दो नोड्स हैंः xj (दाता का प्रतिनिधित्व) और yj (रोगी का प्रतिनिधित्व)। वे वजन 1 के किनारे से जुड़े हुए हैं। G में प्रत्येक किनारे i-> j के लिए, H में 1 + 1/n वजन का एक किनारा xi-- yj जोड़ें। एच में अधिकतम वजन का मिलान ज्ञात कीजिए। जी में प्रत्येक अधिकतम कार्डिनलिटी का आदान-प्रदान एच में अधिकतम वजन के मिलान से मेल खाता है। ध्यान दें कि वजन इस बात की गारंटी देता है कि एच में प्रत्येक अधिकतम वजन का मिलान सही है, ताकि प्रत्येक रोगी या तो एक संगत दाता या अपने स्वयं के दाता से मेल खा सके। इसलिए कोई भी दाता तब तक गुर्दा नहीं देता जब तक कि उसके रोगी को गुर्दा नहीं मिल जाता, जो व्यक्तिगत तर्कसंगतता की आवश्यकता को पूरा करता है। इस एल्गोरिदम को अधिकतम वजन के आदान-प्रदान तक विस्तारित करना और परोपकारी दाताओं को शामिल करना आसान है। जोड़ीदार गुर्दे का आदान-प्रदान 2004 में न्यू इंग्लैंड में एक गुर्दे के आदान-प्रदान कार्यक्रम को लागू करने की दिशा में चर्चा में, यह पाया गया कि, तार्किक रूप से, केवल जोड़ीदार आदान-प्रदान ही संभव हैं। ऐसा इसलिए है क्योंकि एक एक्सचेंज में सभी संचालन एक साथ किए जाने चाहिए। इस आवश्यकता का उद्देश्य व्यक्तिगत तर्कसंगतता बाधा को सुनिश्चित करना है-इस जोखिम से बचने के लिए कि एक दाता अपने रोगी को गुर्दा मिलने के बाद दान करने से इनकार कर देता है। आकार k के एक विनिमय चक्र के लिए 2k एक साथ संचालन की आवश्यकता होती है। उस समय, 4 से अधिक एक साथ संचालन की व्यवस्था करना व्यावहारिक नहीं था, इसलिए चक्रों का आकार 2 तक सीमित था। इस सेटिंग में, निर्देशित संगतता ग्राफ को एक अनिर्दिष्ट ग्राफ में कम करना संभव है, जहां जोड़े ए और बी जुड़े हुए हैं यदि और केवल अगर ए-> बी और बी-> ए। अधिकतम-कार्डिनलिटी जोड़ीदार विनिमय का पता लगाना उस अप्रत्यक्ष ग्राफ में अधिकतम कार्डिनलिटी मिलान का पता लगाने के बराबर है। इसके अलावा, जब केवल जोड़ीदार आदान-प्रदान की अनुमति होती है, तो एक मिलान पारेटो-कुशल होता है यदि और केवल तभी जब इसमें अधिकतम कार्डिनलिटी हो। इसलिए, इस तरह का आदान-प्रदान बहुपद समय में पाया जा सकता है। रोथ, सोनमेज़ और अनवर सरल अधिकतम-कार्डिनलिटी विनिमय के दो विस्तारों का अध्ययन करते हैंः रोगियों या प्रत्यारोपण पर प्राथमिकता श्रेणी को देखते हुए, बहुपद समय में एक प्राथमिकता मिलान खोजना संभव है-एक मिलान जो सभी अधिकतम-कार्डिनलिटी मिलानों के बीच, उच्च-प्राथमिकता वाले रोगियों की संख्या को अधिकतम करता है। इसके अलावा, इन एल्गोरिदम को इस अर्थ में प्रोत्साहन-संगत बनाया जा सकता है कि प्रत्येक रोगी प्रणाली में अधिक से अधिक दाताओं को लाकर और अधिक से अधिक गुर्दों को स्वीकार करने के लिए सहमत होकर मिलान किए जाने की अपनी संभावना को अधिकतम करता है। प्रमाण ग्राफ सिद्धांत से अवधारणाओं का उपयोग करते हैं, जैसे कि गैलाई-एडमंड्स अपघटन। एक यादृच्छिक विनिमय खोजना संभव है, जहाँ सभी अधिकतम-कार्डिनलिटी मिलानों में से यादृच्छिक रूप से एक मिलान का चयन किया जाता है। समतावादी तंत्र का उद्देश्य गुर्दा प्राप्त करने के लिए रोगी की सबसे छोटी संभावना को अधिकतम करना है। समतावादी तंत्र उसी अर्थ में प्रोत्साहन-संगत है जैसे प्राथमिकता तंत्र। लंबाई के चक्र k बाद के वर्षों में, रसद सुधारों ने बड़ी संख्या में एक साथ संचालन के निष्पादन की अनुमति दी। तदनुसार, तीन या अधिक जोड़े वाले विनिमय चक्रों को संभव बनाया गया। अधिकतम-कार्डिनलिटी विनिमय का पता लगाने को ग्राफ सैद्धांतिक शब्दों में, अधिकतम चक्र पैकिंग कहा जाता है। किसी भी निश्चित k ≤ 3 के लिए अधिकतम k लंबाई के चक्रों के साथ अधिकतम चक्र पैकिंग एक एनपी-हार्ड कम्प्यूटेशनल समस्या है (इसे हाइपरग्राफ में 3-आयामी मिलान की समस्या से कम करके साबित किया जा सकता है)। अब्राहम, ब्लम और सैंडहोल्म अधिकतम साइकिल पैकिंग के लिए दो तकनीकें प्रस्तुत करते हैंः कॉलम पीढ़ी और बाधा पीढ़ी। वे बताते हैं कि स्तंभ पीढ़ी बहुत बेहतर होती है। उनके एल्गोरिदम को युग्मित गुर्दा दान के लिए गठबंधन में लागू किया गया है। बीरो, मैनलोव और रिज़ी इस समस्या को हल करने के लिए दो तरीकों का सुझाव देते हैं, भले ही किनारों पर भार हो (इस मामले में इसे अधिकतम-वजन चक्र पैकिंग कहा जाता है): अधिकतम-वजन स्वतंत्र सेट के लिए ज्ञात सन्निकटन एल्गोरिदम के आधार पर एक सन्निकटन एल्गोरिदम; एक सटीक एल्गोरिदम, जो चक्रों के हाइपरग्राफ को एक ग्राफ में बदलने के सभी तरीकों की व्यवस्थित रूप से जाँच करता है। एल्गोरिथ्म समय पर चलता है, जहाँ s प्रत्येक 3-चक्र से एक चाप वाले सेट का आकार है। लंबाई k के चक्रों और असीम लंबाई की श्रृंखलाओं का उपयोग पारस्परिक दाताओं के आदान-प्रदान की एक श्रृंखला शुरू करने के लिए किया जा सकता है, जो कि एक चक्र नहीं है। ऐसी श्रृंखला में, ऑपरेशन को एक साथ करने की आवश्यकता नहीं होती हैः प्रत्येक रोगी को यह गारंटी देना संभव है कि उसके दाता द्वारा गुर्दा देने से पहले उसे गुर्दा प्राप्त हो। यदि कोई दाता दोषपूर्ण है, तो यह श्रृंखला को तोड़ देता है, लेकिन यह उन रोगियों को नुकसान नहीं पहुंचाता है जिनके दाता ने पहले ही गुर्दा दे दिया है, इसलिए यह व्यक्तिगत तर्कसंगतता को नहीं तोड़ता है। एंडरसन, एशलागी, गामार्निक और रोथ अधिकतम के और असीम लंबाई की श्रृंखलाओं पर लंबाई के चक्रों में अधिकतम-कार्डिनलिटी पैकिंग खोजने के लिए दो एल्गोरिदम प्रस्तुत करते हैंः एक पूर्णांक रैखिक प्रोग्रामिंग और बाधा पीढ़ी पर आधारित है; दूसरा यात्रा विक्रेता समस्या के समाधान पर आधारित है। अनिश्चित प्रत्यारोपण ओ. के. ई. में प्रारंभिक सैद्धांतिक कार्यों ने माना कि, एक बार आदान-प्रदान का एक सेट निर्धारित हो जाने के बाद, उन सभी को निष्पादित किया जाएगा। व्यवहार में, हालांकि, प्रत्यारोपण रद्द किया जा सकता है। उदाहरण के लिए, प्रत्यारोपण से ठीक पहले की गई चिकित्सा जांच से पता चल सकता है कि दाता रोगी के साथ असंगत है, भले ही डेटाबेस में वे संगत के रूप में पंजीकृत हों। इसलिए, नए कार्यों का उद्देश्य प्रत्यारोपण की अपेक्षित संख्या को अधिकतम करना है। उदाहरण के लिए, एल्वेलोस, क्लिमेंटोवा और वियाना इस समस्या के लिए एक शाखा-और-मूल्य एल्गोरिदम प्रस्तुत करते हैं। आगे गुर्दे के आदान-प्रदान के लिए पूर्णांक-प्रोग्रामिंग मॉडल का संदर्भ दिया गया है। संदर्भ अनुकूलन एल्गोरिदम और तरीके अंग दान