क्रिस्टोफ़ाइड्स एल्गोरिथ्म: Difference between revisions
m (7 revisions imported from alpha:क्रिस्टोफ़ाइड्स_एल्गोरिथ्म) |
No edit summary |
||
| Line 47: | Line 47: | ||
==बाहरी संबंध== | ==बाहरी संबंध== | ||
* [https://xlinux.nist.gov/dads/HTML/christofides.html NIST Christofides Algorithm Definition] | * [https://xlinux.nist.gov/dads/HTML/christofides.html NIST Christofides Algorithm Definition] | ||
[[Category:1976 कंप्यूटिंग में]] | |||
[[Category:CS1 English-language sources (en)]] | |||
[[Category: | [[Category:CS1 русский-language sources (ru)]] | ||
[[Category:Created On 25/06/2023]] | [[Category:Created On 25/06/2023]] | ||
[[Category:Vigyan Ready]] | [[Category:Machine Translated Page]] | ||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:ग्राफ़ एल्गोरिदम]] | |||
[[Category:ट्रैवलिंग सेल्समैन की समस्या]] | |||
[[Category:फैले पेड़]] | |||
[[Category:सन्निकटन एल्गोरिदम]] | |||
Latest revision as of 12:00, 14 July 2023
क्रिस्टोफ़ाइड्स कलन विधि या क्रिस्टोफ़ाइड्स-सेरड्यूकोव एल्गोरिदम ट्रैवलिंग सेल्समैन की समस्या के अनुमानित समाधान खोजने के लिए एल्गोरिदम है, ऐसे उदाहरणों पर जहां दूरियां मीट्रिक स्पेस बनाती हैं (वे सममित हैं और त्रिकोण असमानता का पालन करती हैं)।[1] यह सन्निकटन एल्गोरिदम है जो गारंटी देता है कि इसका समाधान इष्टतम समाधान लंबाई के 3/2 के कारक के अन्दर होता है, और इसका नाम निकोस क्रिस्टोफ़ाइड्स और अनातोली आई. सेरड्यूकोव के नाम पर रखा गया है, जिन्होंने 1976 में स्वतंत्र रूप से इसकी खोज की थी।[2][3][4]
यह एल्गोरिदम अभी भी सर्वश्रेष्ठ बहुपद समय सन्निकटन एल्गोरिदम के रूप में खड़ा है, जिसकी सामान्य मीट्रिक स्पेसों पर ट्रैवलिंग सेल्समैन समस्या के लिए संबंधित वैज्ञानिक समुदाय द्वारा गहन समीक्षा की गई है। चूँकि, जुलाई 2020 में, कार्लिन, क्लेन और घरान ने प्रीप्रिंट जारी किया था जिसमें उन्होंने उपन्यास सन्निकटन एल्गोरिथ्म प्रस्तुत किया था और प्रमाणित किया कि इसका सन्निकटन अनुपात 1.5 - 10−36 है।. उनकी विधि क्रिस्टोफाइड्स एल्गोरिथ्म के समान सिद्धांतों का पालन करती है, किन्तु न्यूनतम फैले हुए ट्री के स्पेस पर सावधानीपूर्वक चुने गए यादृच्छिक वितरण से यादृच्छिक रूप से चुने गए ट्री का उपयोग करती है।[5][6] यह पेपर कंप्यूटिंग के सिद्धांत पर संगोष्ठी या स्टॉक'21 में प्रकाशित हुआ था [7] जहां इसे सर्वश्रेष्ठ पेपर का पुरस्कार मिला था।[8]
एल्गोरिथम
माना G = (V,w) ट्रैवलिंग सेल्समैन समस्या का उदाहरण बनें। वह है, G सेट पर पूरा ग्राफ है V शीर्षों का, और फ़ंक्शन w के प्रत्येक किनारे पर गैर-नकारात्मक वास्तविक भार G निर्दिष्ट करता है त्रिभुज असमानता के अनुसार, प्रत्येक तीन शीर्षों के लिए u, v, और x, ऐसा ही w(uv) + w(vx) ≥ w(ux) होना चाहिए .
फिर एल्गोरिथ्म को छद्मकोड में निम्नानुसार वर्णित किया जा सकता है।[1]
- G. का न्यूनतम स्पैनिंग ट्री T बनाएं
- माना O विषम डिग्री (ग्राफ सिद्धांत) के साथ शीर्षों T का सेट बनें हाथ मिलाने की प्रमेयिका द्वारा, O में शीर्षों की संख्या सम है।
- न्यूनतम वजन का सही मिलान खोजें M से शीर्षों द्वारा दिए गए प्रेरित उपग्राफ O में .
- किनारों M और T को मिला लें कनेक्टेड मल्टीग्राफ बनाने के लिए H जिसमें प्रत्येक शीर्ष की डिग्री सम है।
- H में यूलेरियन परिपथ बनाएं .
- बार-बार शीर्षों (शॉर्टकटिंग) को छोड़ कर पिछले चरण में पाए गए परिपथ को हैमिल्टनियन परिपथ में बनाएं।
चरण 5 और 6 से आवश्यक नहीं कि केवल ही परिणाम मिले। इस तरह अनुमानी कई अलग-अलग रास्ते दे सकता है।
अनुमान अनुपात
एल्गोरिथम द्वारा उत्पादित समाधान की निवेश इष्टतम के 3/2 के अन्दर है। इसे सिद्ध करने के लिए, मान लीजिए कि C सबसे अच्छा ट्रैवलिंग सेल्समैन टूर है। C से एक किनारे को हटाने पर एक स्पैनिंग ट्री बनता है, जिसका वजन कम से कम न्यूनतम स्पैनिंग ट्री के सामान्य होना चाहिए, जिसका अर्थ है कि w(T) ≤ w(C)। इसके बाद, C के चारों ओर चक्रीय क्रम में O के शीर्षों को क्रमांकित करें, और C को पथों के दो सेटों में विभाजित करें: वे जिनमें चक्रीय क्रम में पहले पथ शीर्ष पर एक विषम संख्या होती है और वे जिनमें पहले पथ शीर्ष पर एक सम संख्या होती है . पथों का प्रत्येक सेट O के पूर्ण मिलान से मेल खाता है जो प्रत्येक पथ के दो समापन बिंदुओं से मेल खाता है, और इस मिलान का भार पथों के भार के सामान्य है। चूंकि पथों के ये दो सेट C के किनारों को विभाजित करते हैं, इसलिए दो सेटों में से एक का वजन C के वजन का अधिकतम आधा होता है, और त्रिभुज असमानता के कारण इसके संगत मिलान का वजन C के वजन का अधिकतम आधा होता है। इस प्रकार न्यूनतम-वजन पूर्ण मिलान का कोई बड़ा वजन नहीं हो सकता है, इसलिए w(M) ≤ w(C)/2 T और M का वजन जोड़ने पर यूलर टूर का वजन अधिकतम 3w(C)/2 हो जाता है। त्रिभुज असमानता के कारण, शॉर्टकटिंग से वजन नहीं बढ़ता है, इसलिए आउटपुट का वजन भी अधिकतम 3w(C)/2 होता है।[1]
निचली सीमा
ट्रैवलिंग सेल्समैन समस्या के लिए ऐसे इनपुट उपस्थित हैं जो क्रिस्टोफ़ाइड्स एल्गोरिदम को एक समाधान खोजने के लिए प्रेरित करते हैं जिसका सन्निकटन अनुपात सही विधि से 3/2 के निकट है। इनपुट का ऐसा एक वर्ग n शीर्षों के एक पथ द्वारा बनता है, जिसमें पथ किनारों का भार 1 होता है, साथ में किनारों का एक सेट जो शीर्षों को जोड़ता है, पथ में दो चरणों की दूरी पर भार 1 + ε के साथ एक संख्या ε के लिए शून्य के निकट चुना जाता है किन्तु सकारात्मक संपूर्ण ग्राफ़ के शेष सभी किनारों की दूरियाँ इस उपग्राफ़ में सबसे छोटे पथों द्वारा दी गई हैं। फिर न्यूनतम स्पैनिंग ट्री पथ द्वारा दिया जाएगा, लंबाई n − 1, और केवल दो विषम शीर्ष पथ समापन बिंदु होंगे, जिनके पूर्ण मिलान में लगभग n/2 वजन के साथ एक एकल किनारा होता है। ट्री का मिलन और मिलान एक चक्र है, जिसमें कोई संभावित शॉर्टकट नहीं है, और वजन लगभग 3n/2 है। चूँकि, इष्टतम समाधान पथ के अंतिम बिंदुओं पर पड़ने वाले दो भार-1 किनारों के साथ वजन 1 + ε के किनारों का उपयोग करता है, और कुल वजन (1 + ε)(n − 2) + 2 है, जो छोटे के लिए n के निकट ε का मान है. इसलिए हमें 3/2 का अनुमानित अनुपात प्राप्त होता है।[9]
उदाहरण
 |
दिया गया: पूरा ग्राफ़ जिसके किनारों का भार त्रिभुज असमानता का पालन करता है |
 |
न्यूनतम स्पैनिंग ट्री T की गणना करें |
 |
शीर्षों के समुच्चय की गणना करें O विषम डिग्री के साथ T में |
 |
केवल O के शीर्षों का उपयोग करके G का उपग्राफ़ बनाइए |
 |
इस सबग्राफ में न्यूनतम-वजन वाले पूर्ण मिलान वाले एम का निर्माण करें |
 |
यूलेरियन मल्टीग्राफ बनाने के लिए मैचिंग और स्पैनिंग ट्री T ∪ M को एकजुट करें |
 |
यूलर दौरे की गणना करें
यहां टूर A->B->C->A->D->E->A होती है। A->B->C->A->E->D->A भी समान रूप से मान्य है। |
 |
एल्गोरिथम का आउटपुट देते हुए, बार-बार आने वाले शीर्षों को हटाएँ।
यदि वैकल्पिक टूर का उपयोग किया गया होता, जिससे शॉर्टकट C से E तक जा रहा होता, जिसके परिणामस्वरूप एक छोटा मार्ग होता (A->B->C->E->D->A) यदि यह एक यूक्लिडियन ग्राफ है मार्ग A->B->C->D->E->A में प्रतिच्छेदी रेखाएँ हैं जो सिद्ध है कि यह सबसे छोटा मार्ग नहीं है। |
संदर्भ
- ↑ 1.0 1.1 1.2 Goodrich, Michael T.; Tamassia, Roberto (2015), "18.1.2 The Christofides Approximation Algorithm", Algorithm Design and Applications, Wiley, pp. 513–514.
- ↑ Christofides, Nicos (1976), Worst-case analysis of a new heuristic for the travelling salesman problem (PDF), Report 388, Graduate School of Industrial Administration, CMU, archived (PDF) from the original on July 21, 2019
- ↑ van Bevern, René; Slugina, Viktoriia A. (2020), "A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem", Historia Mathematica, 53: 118–127, arXiv:2004.02437, doi:10.1016/j.hm.2020.04.003, S2CID 214803097
- ↑ Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF), Upravlyaemye Sistemy (in русский), 17: 76–79
- ↑ Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis (2020-08-30). "मीट्रिक टीएसपी के लिए ए (थोड़ा सा) बेहतर सन्निकटन एल्गोरिदम". arXiv:2007.01409 [cs.DS].
- ↑ Klarreich, Erica (8 October 2020). "कंप्यूटर वैज्ञानिकों ने ट्रैवलिंग सेल्सपर्सन का रिकॉर्ड तोड़ा". Quanta Magazine (in English). Retrieved 2020-10-10.
- ↑ Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis (2021-06-15), "A (slightly) improved approximation algorithm for metric TSP", Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, New York, NY, USA: Association for Computing Machinery, pp. 32–45, arXiv:2007.01409, doi:10.1145/3406325.3451009, ISBN 978-1-4503-8053-9, retrieved 2022-04-20
- ↑ "ACM SIGACT - STOC सर्वश्रेष्ठ पेपर पुरस्कार". www.sigact.org. Retrieved 2022-04-20.
- ↑ Bläser, Markus (2008), "Metric TSP", in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms}, Springer-Verlag, pp. 517–519, ISBN 9780387307701.
