क्रिस्टोफ़ाइड्स एल्गोरिथ्म: Difference between revisions

Latest revision as of 12:00, 14 July 2023

क्रिस्टोफ़ाइड्स कलन विधि या क्रिस्टोफ़ाइड्स-सेरड्यूकोव एल्गोरिदम ट्रैवलिंग सेल्समैन की समस्या के अनुमानित समाधान खोजने के लिए एल्गोरिदम है, ऐसे उदाहरणों पर जहां दूरियां मीट्रिक स्पेस बनाती हैं (वे सममित हैं और त्रिकोण असमानता का पालन करती हैं)।^[1] यह सन्निकटन एल्गोरिदम है जो गारंटी देता है कि इसका समाधान इष्टतम समाधान लंबाई के 3/2 के कारक के अन्दर होता है, और इसका नाम निकोस क्रिस्टोफ़ाइड्स और अनातोली आई. सेरड्यूकोव के नाम पर रखा गया है, जिन्होंने 1976 में स्वतंत्र रूप से इसकी खोज की थी।^[2]^[3]^[4]

यह एल्गोरिदम अभी भी सर्वश्रेष्ठ बहुपद समय सन्निकटन एल्गोरिदम के रूप में खड़ा है, जिसकी सामान्य मीट्रिक स्पेसों पर ट्रैवलिंग सेल्समैन समस्या के लिए संबंधित वैज्ञानिक समुदाय द्वारा गहन समीक्षा की गई है। चूँकि, जुलाई 2020 में, कार्लिन, क्लेन और घरान ने प्रीप्रिंट जारी किया था जिसमें उन्होंने उपन्यास सन्निकटन एल्गोरिथ्म प्रस्तुत किया था और प्रमाणित किया कि इसका सन्निकटन अनुपात 1.5 - 10⁻³⁶ है।. उनकी विधि क्रिस्टोफाइड्स एल्गोरिथ्म के समान सिद्धांतों का पालन करती है, किन्तु न्यूनतम फैले हुए ट्री के स्पेस पर सावधानीपूर्वक चुने गए यादृच्छिक वितरण से यादृच्छिक रूप से चुने गए ट्री का उपयोग करती है।^[5]^[6] यह पेपर कंप्यूटिंग के सिद्धांत पर संगोष्ठी या स्टॉक'21 में प्रकाशित हुआ था ^[7] जहां इसे सर्वश्रेष्ठ पेपर का पुरस्कार मिला था।^[8]

एल्गोरिथम

माना $G = (V, w)$ ट्रैवलिंग सेल्समैन समस्या का उदाहरण बनें। वह है, $G$ सेट पर पूरा ग्राफ है $V$ शीर्षों का, और फ़ंक्शन $w$ के प्रत्येक किनारे पर गैर-नकारात्मक वास्तविक भार $G$ निर्दिष्ट करता है त्रिभुज असमानता के अनुसार, प्रत्येक तीन शीर्षों के लिए $u$ , $v$ , और $x$ , ऐसा ही $w (uv) + w (vx) \geq w (ux)$ होना चाहिए .

फिर एल्गोरिथ्म को छद्मकोड में निम्नानुसार वर्णित किया जा सकता है।^[1]

$G$ . का न्यूनतम स्पैनिंग ट्री $T$ बनाएं
माना $O$ विषम डिग्री (ग्राफ सिद्धांत) के साथ शीर्षों $T$ का सेट बनें हाथ मिलाने की प्रमेयिका द्वारा, $O$ में शीर्षों की संख्या सम है।
न्यूनतम वजन का सही मिलान खोजें $M$ से शीर्षों द्वारा दिए गए प्रेरित उपग्राफ $O$ में .
किनारों $M$ और $T$ को मिला लें कनेक्टेड मल्टीग्राफ बनाने के लिए $H$ जिसमें प्रत्येक शीर्ष की डिग्री सम है।
$H$ में यूलेरियन परिपथ बनाएं .
बार-बार शीर्षों (शॉर्टकटिंग) को छोड़ कर पिछले चरण में पाए गए परिपथ को हैमिल्टनियन परिपथ में बनाएं।

चरण 5 और 6 से आवश्यक नहीं कि केवल ही परिणाम मिले। इस तरह अनुमानी कई अलग-अलग रास्ते दे सकता है।

अनुमान अनुपात

एल्गोरिथम द्वारा उत्पादित समाधान की निवेश इष्टतम के 3/2 के अन्दर है। इसे सिद्ध करने के लिए, मान लीजिए कि $C$ सबसे अच्छा ट्रैवलिंग सेल्समैन टूर है। $C$ से एक किनारे को हटाने पर एक स्पैनिंग ट्री बनता है, जिसका वजन कम से कम न्यूनतम स्पैनिंग ट्री के सामान्य होना चाहिए, जिसका अर्थ है कि $w (T) \leq w (C)$ । इसके बाद, $C$ के चारों ओर चक्रीय क्रम में $O$ के शीर्षों को क्रमांकित करें, और $C$ को पथों के दो सेटों में विभाजित करें: वे जिनमें चक्रीय क्रम में पहले पथ शीर्ष पर एक विषम संख्या होती है और वे जिनमें पहले पथ शीर्ष पर एक सम संख्या होती है . पथों का प्रत्येक सेट $O$ के पूर्ण मिलान से मेल खाता है जो प्रत्येक पथ के दो समापन बिंदुओं से मेल खाता है, और इस मिलान का भार पथों के भार के सामान्य है। चूंकि पथों के ये दो सेट $C$ के किनारों को विभाजित करते हैं, इसलिए दो सेटों में से एक का वजन $C$ के वजन का अधिकतम आधा होता है, और त्रिभुज असमानता के कारण इसके संगत मिलान का वजन $C$ के वजन का अधिकतम आधा होता है। इस प्रकार न्यूनतम-वजन पूर्ण मिलान का कोई बड़ा वजन नहीं हो सकता है, इसलिए $w (M) \leq w (C)/2$ $T$ और $M$ का वजन जोड़ने पर यूलर टूर का वजन अधिकतम 3w(C)/2 हो जाता है। त्रिभुज असमानता के कारण, शॉर्टकटिंग से वजन नहीं बढ़ता है, इसलिए आउटपुट का वजन भी अधिकतम 3w(C)/2 होता है।^[1]

निचली सीमा

ट्रैवलिंग सेल्समैन समस्या के लिए ऐसे इनपुट उपस्थित हैं जो क्रिस्टोफ़ाइड्स एल्गोरिदम को एक समाधान खोजने के लिए प्रेरित करते हैं जिसका सन्निकटन अनुपात सही विधि से 3/2 के निकट है। इनपुट का ऐसा एक वर्ग $n$ शीर्षों के एक पथ द्वारा बनता है, जिसमें पथ किनारों का भार $1$ होता है, साथ में किनारों का एक सेट जो शीर्षों को जोड़ता है, पथ में दो चरणों की दूरी पर भार $1 + ε$ के साथ एक संख्या $ε$ के लिए शून्य के निकट चुना जाता है किन्तु सकारात्मक संपूर्ण ग्राफ़ के शेष सभी किनारों की दूरियाँ इस उपग्राफ़ में सबसे छोटे पथों द्वारा दी गई हैं। फिर न्यूनतम स्पैनिंग ट्री पथ द्वारा दिया जाएगा, लंबाई $n - 1$ , और केवल दो विषम शीर्ष पथ समापन बिंदु होंगे, जिनके पूर्ण मिलान में लगभग $n /2$ वजन के साथ एक एकल किनारा होता है। ट्री का मिलन और मिलान एक चक्र है, जिसमें कोई संभावित शॉर्टकट नहीं है, और वजन लगभग $3 n /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.

बाहरी संबंध

NIST Christofides Algorithm Definition

[gt-1] 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.

[2] 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

[3] 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

[4] Serdyukov, Anatoliy I. (1978), "О некоторых экстремальных обходах в графах" [On some extremal walks in graphs] (PDF), Upravlyaemye Sistemy (in русский), 17: 76–79

[5] Karlin, Anna R.; Klein, Nathan; Gharan, Shayan Oveis (2020-08-30). "मीट्रिक टीएसपी के लिए ए (थोड़ा सा) बेहतर सन्निकटन एल्गोरिदम". arXiv:2007.01409 [cs.DS].

[6] Klarreich, Erica (8 October 2020). "कंप्यूटर वैज्ञानिकों ने ट्रैवलिंग सेल्सपर्सन का रिकॉर्ड तोड़ा". Quanta Magazine (in English). Retrieved 2020-10-10.

[7] 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

[8] "ACM SIGACT - STOC सर्वश्रेष्ठ पेपर पुरस्कार". www.sigact.org. Retrieved 2022-04-20.

[9] Bläser, Markus (2008), "Metric TSP", in Kao, Ming-Yang (ed.), Encyclopedia of Algorithms}, Springer-Verlag, pp. 517–519, ISBN 9780387307701.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
-'''क्रिस्टोफ़ाइड्स [[कलन विधि]]''' या '''क्रिस्टोफ़ाइड्स-सेरड्यूकोव एल्गोरिदम''' [[ट्रैवलिंग सेल्समैन की समस्या]] के अनुमानित समाधान खोजने के लिए एल्गोरिदम है, ऐसे उदाहरणों पर जहां दूरियां [[मीट्रिक स्थान]] बनाती हैं (वे सममित हैं और त्रिकोण असमानता का पालन करती हैं)।<ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|pages=513–514|chapter=18.1.2 The Christofides Approximation Algorithm}}.</ref> यह सन्निकटन एल्गोरिदम है जो गारंटी देता है कि इसका समाधान इष्टतम समाधान लंबाई के 3/2 के कारक के भीतर होगा, और इसका नाम [[निकोस क्रिस्टोफ़ाइड्स]] और अनातोली आई. सेरड्यूकोव के नाम पर रखा गया है, जिन्होंने 1976 में स्वतंत्र रूप से इसकी खोज की थी।<ref>{{citation|last=Christofides|first=Nicos|author-link=Nicos Christofides|year=1976|title=Worst-case analysis of a new heuristic for the travelling salesman problem|others=Report 388|institution=Graduate School of Industrial Administration, CMU|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf|archive-url=https://web.archive.org/web/20190721172134/https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf|url-status=live|archive-date=July 21, 2019}}</ref><ref>{{citation|last1=van Bevern|first1=René|last2=Slugina|first2=Viktoriia A.|year=2020|title=A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem|journal=Historia Mathematica|volume=53|pages=118–127|doi=10.1016/j.hm.2020.04.003|arxiv=2004.02437|s2cid=214803097}}</ref><ref>{{citation|last=Serdyukov|first=Anatoliy I.|date=1978|title=О некоторых экстремальных обходах в графах|trans-title = On some extremal walks in graphs|language=ru|url=http://nas1.math.nsc.ru/aim/journals/us/us17/us17_007.pdf|journal=Upravlyaemye Sistemy|volume=17|pages=76–79}}</ref>
+'''क्रिस्टोफ़ाइड्स [[कलन विधि]]''' या '''क्रिस्टोफ़ाइड्स-सेरड्यूकोव एल्गोरिदम''' [[ट्रैवलिंग सेल्समैन की समस्या]] के अनुमानित समाधान खोजने के लिए एल्गोरिदम है, ऐसे उदाहरणों पर जहां दूरियां [[मीट्रिक स्थान|मीट्रिक स्पेस]] बनाती हैं (वे सममित हैं और त्रिकोण असमानता का पालन करती हैं)।<ref name="gt">{{citation|title=Algorithm Design and Applications|first1=Michael T.|last1=Goodrich|author1-link=Michael T. Goodrich|first2=Roberto|last2=Tamassia|author2-link=Roberto Tamassia|publisher=Wiley|year=2015|pages=513–514|chapter=18.1.2 The Christofides Approximation Algorithm}}.</ref> यह सन्निकटन एल्गोरिदम है जो गारंटी देता है कि इसका समाधान इष्टतम समाधान लंबाई के 3/2 के कारक के अन्दर होता है, और इसका नाम [[निकोस क्रिस्टोफ़ाइड्स]] और अनातोली आई. सेरड्यूकोव के नाम पर रखा गया है, जिन्होंने 1976 में स्वतंत्र रूप से इसकी खोज की थी।<ref>{{citation|last=Christofides|first=Nicos|author-link=Nicos Christofides|year=1976|title=Worst-case analysis of a new heuristic for the travelling salesman problem|others=Report 388|institution=Graduate School of Industrial Administration, CMU|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf|archive-url=https://web.archive.org/web/20190721172134/https://apps.dtic.mil/dtic/tr/fulltext/u2/a025602.pdf|url-status=live|archive-date=July 21, 2019}}</ref><ref>{{citation|last1=van Bevern|first1=René|last2=Slugina|first2=Viktoriia A.|year=2020|title=A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem|journal=Historia Mathematica|volume=53|pages=118–127|doi=10.1016/j.hm.2020.04.003|arxiv=2004.02437|s2cid=214803097}}</ref><ref>{{citation|last=Serdyukov|first=Anatoliy I.|date=1978|title=О некоторых экстремальных обходах в графах|trans-title = On some extremal walks in graphs|language=ru|url=http://nas1.math.nsc.ru/aim/journals/us/us17/us17_007.pdf|journal=Upravlyaemye Sistemy|volume=17|pages=76–79}}</ref>
-यह एल्गोरिदम अभी भी सर्वश्रेष्ठ बहुपद समय सन्निकटन एल्गोरिदम के रूप में खड़ा है, जिसकी सामान्य मीट्रिक स्थानों पर ट्रैवलिंग सेल्समैन समस्या के लिए संबंधित वैज्ञानिक समुदाय द्वारा गहन समीक्षा की गई है। हालाँकि, जुलाई 2020 में, कार्लिन, क्लेन और घरान ने प्रीप्रिंट जारी किया जिसमें उन्होंने उपन्यास सन्निकटन एल्गोरिथ्म पेश किया और दावा किया कि इसका सन्निकटन अनुपात 1.5 - 10 है।<sup>−36</sup>. उनकी विधि क्रिस्टोफाइड्स एल्गोरिथ्म के समान सिद्धांतों का पालन करती है, लेकिन न्यूनतम फैले हुए पेड़ के स्थान पर सावधानीपूर्वक चुने गए यादृच्छिक वितरण से यादृच्छिक रूप से चुने गए पेड़ का उपयोग करती है।<ref>{{cite arXiv|last1=Karlin|first1=Anna R.|author1-link=Anna Karlin|last2=Klein|first2=Nathan|last3=Gharan|first3=Shayan Oveis|date=2020-08-30|title=मीट्रिक टीएसपी के लिए ए (थोड़ा सा) बेहतर सन्निकटन एल्गोरिदम|class=cs.DS|eprint=2007.01409}}</ref><ref>{{Cite web|last=Klarreich|first=Erica|author-link=Erica Klarreich|title=कंप्यूटर वैज्ञानिकों ने ट्रैवलिंग सेल्सपर्सन का रिकॉर्ड तोड़ा|url=https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/|access-date=2020-10-10|website=Quanta Magazine|date=8 October 2020|language=en}}</ref> यह पेपर कंप्यूटिंग के सिद्धांत पर संगोष्ठी|STOC'21 में प्रकाशित हुआ था<ref>{{Citation |last=Karlin |first=Anna R. |title=A (slightly) improved approximation algorithm for metric TSP |date=2021-06-15 |url=https://doi.org/10.1145/3406325.3451009 |work=Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing |pages=32–45 |place=New York, NY, USA |publisher=Association for Computing Machinery |doi=10.1145/3406325.3451009 |isbn=978-1-4503-8053-9 |access-date=2022-04-20 |last2=Klein |first2=Nathan |last3=Gharan |first3=Shayan Oveis|arxiv=2007.01409 }}</ref> जहां इसे सर्वश्रेष्ठ पेपर का पुरस्कार मिला।<ref>{{Cite web |title=ACM SIGACT - STOC सर्वश्रेष्ठ पेपर पुरस्कार|url=https://www.sigact.org/prizes/best_paper.html |access-date=2022-04-20 |website=www.sigact.org}}</ref>
+यह एल्गोरिदम अभी भी सर्वश्रेष्ठ बहुपद समय सन्निकटन एल्गोरिदम के रूप में खड़ा है, जिसकी सामान्य मीट्रिक स्पेसों पर ट्रैवलिंग सेल्समैन समस्या के लिए संबंधित वैज्ञानिक समुदाय द्वारा गहन समीक्षा की गई है। चूँकि, जुलाई 2020 में, कार्लिन, क्लेन और घरान ने प्रीप्रिंट जारी किया था जिसमें उन्होंने उपन्यास सन्निकटन एल्गोरिथ्म प्रस्तुत किया था और प्रमाणित किया कि इसका सन्निकटन अनुपात 1.5 - 10<sup>−36</sup> है।. उनकी विधि क्रिस्टोफाइड्स एल्गोरिथ्म के समान सिद्धांतों का पालन करती है, किन्तु न्यूनतम फैले हुए ट्री के स्पेस पर सावधानीपूर्वक चुने गए यादृच्छिक वितरण से यादृच्छिक रूप से चुने गए ट्री का उपयोग करती है।<ref>{{cite arXiv|last1=Karlin|first1=Anna R.|author1-link=Anna Karlin|last2=Klein|first2=Nathan|last3=Gharan|first3=Shayan Oveis|date=2020-08-30|title=मीट्रिक टीएसपी के लिए ए (थोड़ा सा) बेहतर सन्निकटन एल्गोरिदम|class=cs.DS|eprint=2007.01409}}</ref><ref>{{Cite web|last=Klarreich|first=Erica|author-link=Erica Klarreich|title=कंप्यूटर वैज्ञानिकों ने ट्रैवलिंग सेल्सपर्सन का रिकॉर्ड तोड़ा|url=https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/|access-date=2020-10-10|website=Quanta Magazine|date=8 October 2020|language=en}}</ref> यह पेपर कंप्यूटिंग के सिद्धांत पर संगोष्ठी या स्टॉक'21 में प्रकाशित हुआ था <ref>{{Citation |last=Karlin |first=Anna R. |title=A (slightly) improved approximation algorithm for metric TSP |date=2021-06-15 |url=https://doi.org/10.1145/3406325.3451009 |work=Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing |pages=32–45 |place=New York, NY, USA |publisher=Association for Computing Machinery |doi=10.1145/3406325.3451009 |isbn=978-1-4503-8053-9 |access-date=2022-04-20 |last2=Klein |first2=Nathan |last3=Gharan |first3=Shayan Oveis|arxiv=2007.01409 }}</ref> जहां इसे सर्वश्रेष्ठ पेपर का पुरस्कार मिला था।<ref>{{Cite web |title=ACM SIGACT - STOC सर्वश्रेष्ठ पेपर पुरस्कार|url=https://www.sigact.org/prizes/best_paper.html |access-date=2022-04-20 |website=www.sigact.org}}</ref>
+== एल्गोरिथम                                                                    ==
+माना {{math|1=''G'' = (''V'',''w'')}} ट्रैवलिंग सेल्समैन समस्या का उदाहरण बनें। वह है, {{mvar|G}} सेट पर [[पूरा ग्राफ]] है {{mvar|V}} शीर्षों का, और फ़ंक्शन {{mvar|w}} के प्रत्येक किनारे पर गैर-नकारात्मक वास्तविक भार {{mvar|G}} निर्दिष्ट करता है त्रिभुज असमानता के अनुसार, प्रत्येक तीन शीर्षों के लिए {{mvar|u}}, {{mvar|v}}, और {{mvar|x}}, ऐसा ही {{math|''w''(''uv'') + ''w''(''vx'') ≥ ''w''(''ux'')}} होना चाहिए .
-== एल्गोरिथम ==
+फिर एल्गोरिथ्म को [[छद्मकोड]] में निम्नानुसार वर्णित किया जा सकता है।<ref name="gt"/>
-होने देना {{math|1=''G'' = (''V'',''w'')}} ट्रैवलिंग सेल्समैन समस्या का उदाहरण बनें। वह है, {{mvar|G}} सेट पर [[पूरा ग्राफ]]़ है {{mvar|V}} शीर्षों का, और फ़ंक्शन {{mvar|w}} के प्रत्येक किनारे पर गैर-नकारात्मक वास्तविक भार निर्दिष्ट करता है {{mvar|G}}.
-त्रिभुज असमानता के अनुसार, प्रत्येक तीन शीर्षों के लिए {{mvar|u}}, {{mvar|v}}, और {{mvar|x}}, ऐसा ही होना चाहिए {{math|''w''(''uv'') + ''w''(''vx'') ≥ ''w''(''ux'')}}.
-फिर एल्गोरिथ्म को [[छद्मकोड]] में निम्नानुसार वर्णित किया जा सकता है।<ref name="gt"/># [[न्यूनतम फैलाव वाला पेड़]] बनाएं {{mvar|T}} का {{mvar|G}}.
+# {{mvar|G}}. का न्यूनतम स्पैनिंग ट्री {{mvar|T}} बनाएं
-# होने देना {{mvar|O}} विषम [[डिग्री (ग्राफ सिद्धांत)]] के साथ शीर्षों का सेट बनें {{mvar|T}}. हाथ मिलाने की प्रमेयिका द्वारा, {{mvar|O}} में शीर्षों की संख्या सम है।
+#माना {{mvar|O}} विषम [[डिग्री (ग्राफ सिद्धांत)]] के साथ शीर्षों {{mvar|T}} का सेट बनें हाथ मिलाने की प्रमेयिका द्वारा, {{mvar|O}} में शीर्षों की संख्या सम है।
-# न्यूनतम वजन का सही मिलान खोजें {{mvar|M}} से शीर्षों द्वारा दिए गए प्रेरित उपग्राफ में {{mvar|O}}.
+# न्यूनतम वजन का सही मिलान खोजें {{mvar|M}} से शीर्षों द्वारा दिए गए प्रेरित उपग्राफ {{mvar|O}} में .
-#किनारों को मिला लें {{mvar|M}} और {{mvar|T}} कनेक्टेड [[मल्टीग्राफ]] बनाने के लिए {{mvar|H}} जिसमें प्रत्येक शीर्ष की डिग्री सम है।
+#किनारों {{mvar|M}} और {{mvar|T}} को मिला लें कनेक्टेड [[मल्टीग्राफ]] बनाने के लिए {{mvar|H}} जिसमें प्रत्येक शीर्ष की डिग्री सम है।
-# में [[यूलेरियन सर्किट]] बनाएं {{mvar|H}}.
+# {{mvar|H}} में [[यूलेरियन सर्किट|यूलेरियन परिपथ]] बनाएं .
-# बार-बार शीर्षों (शॉर्टकटिंग) को छोड़ कर पिछले चरण में पाए गए सर्किट को [[हैमिल्टनियन सर्किट]] में बनाएं।
+# बार-बार शीर्षों (शॉर्टकटिंग) को छोड़ कर पिछले चरण में पाए गए परिपथ को [[हैमिल्टनियन सर्किट|हैमिल्टनियन परिपथ]] में बनाएं।
-चरण 5 और 6 से जरूरी नहीं कि केवल ही परिणाम मिले। इस तरह अनुमानी कई अलग-अलग रास्ते दे सकता है।
+चरण 5 और 6 से आवश्यक नहीं कि केवल ही परिणाम मिले। इस तरह अनुमानी कई अलग-अलग रास्ते दे सकता है।
-==अनुमान अनुपात ==
+==अनुमान अनुपात                                                                      ==
+एल्गोरिथम द्वारा उत्पादित समाधान की निवेश इष्टतम के 3/2 के अन्दर है। इसे सिद्ध करने के लिए, मान लीजिए कि {{mvar|C}} सबसे अच्छा ट्रैवलिंग सेल्समैन टूर है। {{mvar|C}} से एक किनारे को हटाने पर एक स्पैनिंग ट्री बनता है, जिसका वजन कम से कम न्यूनतम स्पैनिंग ट्री के सामान्य होना चाहिए, जिसका अर्थ है कि {{math|''w''(''T'') ≤ ''w''(''C'')}}। इसके बाद, {{mvar|C}} के चारों ओर चक्रीय क्रम में {{mvar|O}} के शीर्षों को क्रमांकित करें, और {{mvar|C}} को पथों के दो सेटों में विभाजित करें: वे जिनमें चक्रीय क्रम में पहले पथ शीर्ष पर एक विषम संख्या होती है और वे जिनमें पहले पथ शीर्ष पर एक सम संख्या होती है . पथों का प्रत्येक सेट {{mvar|O}} के पूर्ण मिलान से मेल खाता है जो प्रत्येक पथ के दो समापन बिंदुओं से मेल खाता है, और इस मिलान का भार पथों के भार के सामान्य है। चूंकि पथों के ये दो सेट {{mvar|C}} के किनारों को विभाजित करते हैं, इसलिए दो सेटों में से एक का वजन {{mvar|C}} के वजन का अधिकतम आधा होता है, और त्रिभुज असमानता के कारण इसके संगत मिलान का वजन {{mvar|C}} के वजन का अधिकतम आधा होता है। इस प्रकार न्यूनतम-वजन पूर्ण मिलान का कोई बड़ा वजन नहीं हो सकता है, इसलिए {{math|''w''(''M'') ≤ ''w''(''C'')/2}} {{mvar|T}} और {{mvar|M}} का वजन जोड़ने पर यूलर टूर का वजन अधिकतम 3w(C)/2 हो जाता है। त्रिभुज असमानता के कारण, शॉर्टकटिंग से वजन नहीं बढ़ता है, इसलिए आउटपुट का वजन भी अधिकतम 3w(C)/2 होता है।<ref name="gt"/>
+==निचली सीमा                                                                           ==
-एल्गोरिथम द्वारा उत्पादित समाधान की लागत इष्टतम के 3/2 के भीतर है।
+ट्रैवलिंग सेल्समैन समस्या के लिए ऐसे इनपुट उपस्थित हैं जो क्रिस्टोफ़ाइड्स एल्गोरिदम को एक समाधान खोजने के लिए प्रेरित करते हैं जिसका सन्निकटन अनुपात सही विधि से 3/2 के निकट है। इनपुट का ऐसा एक वर्ग {{mvar|n}} शीर्षों के एक पथ द्वारा बनता है, जिसमें पथ किनारों का भार {{math|1}} होता है, साथ में किनारों का एक सेट जो शीर्षों को जोड़ता है, पथ में दो चरणों की दूरी पर भार {{math|1 + ''ε''}} के साथ एक संख्या {{math|''ε''}} के लिए शून्य के निकट चुना जाता है किन्तु सकारात्मक संपूर्ण ग्राफ़ के शेष सभी किनारों की दूरियाँ इस उपग्राफ़ में सबसे छोटे पथों द्वारा दी गई हैं। फिर न्यूनतम स्पैनिंग ट्री पथ द्वारा दिया जाएगा, लंबाई {{math|''n'' &minus; 1}}, और केवल दो विषम शीर्ष पथ समापन बिंदु होंगे, जिनके पूर्ण मिलान में लगभग {{math|''n''/2}} वजन के साथ एक एकल किनारा होता है। ट्री का मिलन और मिलान एक चक्र है, जिसमें कोई संभावित शॉर्टकट नहीं है, और वजन लगभग {{math|3''n''/2}} है। चूँकि, इष्टतम समाधान पथ के अंतिम बिंदुओं पर पड़ने वाले दो भार-{{math|1}} किनारों के साथ वजन {{math|1 + ''ε''}} के किनारों का उपयोग करता है, और कुल वजन {{math|(1 + ''ε'')(''n'' &minus; 2) + 2}} है, जो छोटे के लिए {{mvar|n}} के निकट {{math|''ε''}} का मान है. इसलिए हमें 3/2 का अनुमानित अनुपात प्राप्त होता है।<ref>{{citation|title=Encyclopedia of Algorithms}|editor-first=Ming-Yang|editor-last=Kao|publisher=Springer-Verlag|year=2008|isbn=9780387307701|chapter-url=https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA517|pages=517–519|chapter=Metric TSP|first=Markus|last=Bläser}}.</ref>
-इसे साबित करने के लिए आइए {{mvar|C}} इष्टतम ट्रैवलिंग सेल्समैन टूर बनें। से किनारा हटाना {{mvar|C}} फैले हुए पेड़ का उत्पादन करता है, जिसका वजन कम से कम न्यूनतम फैले हुए पेड़ के बराबर होना चाहिए, जिसका अर्थ है {{math|''w''(''T'') ≤ ''w''(''C'')}}.
+== उदाहरण                                                                                                                                                                                              ==
-इसके बाद, शीर्षों को क्रमांकित करें {{mvar|O}} चारों ओर चक्रीय क्रम में {{mvar|C}}, और विभाजन {{mvar|C}} पथों के दो सेटों में: वे जिनमें चक्रीय क्रम में पहले पथ शीर्ष पर विषम संख्या होती है और वे जिनमें पहले पथ शीर्ष पर सम संख्या होती है।
-पथों का प्रत्येक सेट पूर्ण मिलान से मेल खाता है {{mvar|O}} जो प्रत्येक पथ के दो समापन बिंदुओं से मेल खाता है, और इस मिलान का भार अधिकतम पथों के भार के बराबर है।
-चूँकि पथों के ये दो सेट किनारों को विभाजित करते हैं {{mvar|C}}, दो सेटों में से का वजन अधिकतम आधा होता है {{mvar|C}}, और त्रिभुज असमानता के कारण इसके संगत मिलान का भार भी अधिक से अधिक आधा होता है {{mvar|C}}.
-न्यूनतम-वजन वाले पूर्ण मिलान का कोई बड़ा वजन नहीं हो सकता है, इसलिए {{math|''w''(''M'') ≤ ''w''(''C'')/2}}.
-का वजन जोड़ना {{mvar|T}} और {{mvar|M}} अधिक से अधिक यूलर दौरे को महत्व देता है {{math|3''w''(''C'')/2}}. त्रिकोण असमानता के लिए धन्यवाद, शॉर्टकटिंग से वजन नहीं बढ़ता है,
-इसलिए आउटपुट का भार भी अधिकतम होता है {{math|3''w''(''C'')/2}}.<ref name="gt"/>
-==निचली सीमा==
-ट्रैवलिंग सेल्समैन समस्या के लिए ऐसे इनपुट मौजूद हैं जो क्रिस्टोफ़ाइड्स एल्गोरिदम को समाधान खोजने के लिए प्रेरित करते हैं जिसका सन्निकटन अनुपात मनमाने ढंग से 3/2 के करीब है। ऐसा ही वर्ग है
-इनपुट पथ (ग्राफ़ सिद्धांत) द्वारा बनते हैं {{mvar|n}} शीर्ष, पथ के किनारों पर भार होता है {{math|1}}, वजन के साथ पथ में दो कदम दूर शीर्षों को जोड़ने वाले किनारों के सेट के साथ {{math|1 + ''ε''}}
-एक संख्या के लिए {{math|''ε''}}शून्य के करीब लेकिन सकारात्मक चुना गया। संपूर्ण ग्राफ़ के सभी शेष किनारों में इस उपग्राफ़ में सबसे छोटी पथ समस्याओं द्वारा दी गई दूरियाँ हैं।
-फिर न्यूनतम फैले हुए पेड़ की लंबाई, पथ द्वारा दी जाएगी {{math|''n'' &minus; 1}}, और केवल दो विषम शीर्ष पथ समापन बिंदु होंगे, जिनके पूर्ण मिलान में लगभग वजन वाला किनारा होता है {{math|''n''/2}}.
-पेड़ का मिलन और मिलान चक्र है, जिसमें कोई संभावित शॉर्टकट नहीं है, और वजन लगभग है {{math|3''n''/2}}. हालाँकि, इष्टतम समाधान वजन के किनारों का उपयोग करता है {{math|1 + ''ε''}}दो वजन सहित-{{math|1}} किनारे पथ के अंतिम बिंदुओं पर आपतित होते हैं,
-और कुल वजन है {{math|(1 + ''ε'')(''n'' &minus; 2) + 2}}, के करीब {{mvar|n}} के छोटे मानों के लिए {{math|''ε''}}. इसलिए हमें 3/2 का अनुमानित अनुपात प्राप्त होता है।<ref>{{citation|title=Encyclopedia of Algorithms}|editor-first=Ming-Yang|editor-last=Kao|publisher=Springer-Verlag|year=2008|isbn=9780387307701|chapter-url=https://books.google.com/books?id=i3S9_GnHZwYC&pg=PA517|pages=517–519|chapter=Metric TSP|first=Markus|last=Bläser}}.</ref>
-== उदाहरण ==
 {| class="wikitable"
 |-
-|[[File:Metrischer Graph mit 5 Knoten.svg|200px]]|| Given: complete graph whose edge weights obey the triangle inequality
+|[[File:Metrischer Graph mit 5 Knoten.svg|200px]]|| दिया गया: पूरा ग्राफ़ जिसके किनारों का भार त्रिभुज असमानता का पालन करता है
 |-
-|[[File:Christofides MST.svg|200px]] || Calculate [[minimum spanning tree]] {{mvar|T}}
+|[[File:Christofides MST.svg|200px]] || न्यूनतम स्पैनिंग ट्री {{mvar|T}} की गणना करें
 |-
-|[[File:V'.svg|200px]] || Calculate the set of vertices {{mvar|O}} with odd degree in {{mvar|T}}
+|[[File:V'.svg|200px]] || शीर्षों के समुच्चय की गणना करें O विषम डिग्री के साथ T में
 |-
-|[[File:G V'.svg|200px]] || Form the subgraph of {{mvar|G}} using only the vertices of {{mvar|O}}
+|[[File:G V'.svg|200px]] || केवल O के शीर्षों का उपयोग करके G का उपग्राफ़ बनाइए
 |-
-|[[File:Christofides Matching.svg|200px]] || Construct a minimum-weight perfect matching {{mvar|M}} in this subgraph
+|[[File:Christofides Matching.svg|200px]] || इस सबग्राफ में न्यूनतम-वजन वाले पूर्ण मिलान वाले एम का निर्माण करें
 |-
-|[[File:TuM.svg|200px]] || Unite matching and spanning tree {{math|''T'' &cup; ''M''}} to form an Eulerian multigraph
+|[[File:TuM.svg|200px]] || यूलेरियन मल्टीग्राफ बनाने के लिए मैचिंग और स्पैनिंग ट्री T ∪ M को एकजुट करें
 |-
-|[[File:Eulertour.svg|200px]] || Calculate Euler tour<br><br>Here the tour goes A->B->C->A->D->E->A. Equally valid is A->B->C->A->E->D->A.
+|[[File:Eulertour.svg|200px]] || यूलर दौरे की गणना करें
+यहां टूर A->B->C->A->D->E->A होती है। A->B->C->A->E->D->A भी समान रूप से मान्य है।
 |-
-|[[File:Eulertour bereinigt.svg|200px]] || Remove repeated vertices, giving the algorithm's output.<br><br>If the alternate tour would have been used, the shortcut would be going from C to E which results in a shorter route (A->B->C->E->D->A) if this is an euclidean graph as the route A->B->C->D->E->A has intersecting lines which is proven not to be the shortest route.
+|[[File:Eulertour bereinigt.svg|200px]] || एल्गोरिथम का आउटपुट देते हुए, बार-बार आने वाले शीर्षों को हटाएँ।
+यदि वैकल्पिक टूर का उपयोग किया गया होता, जिससे शॉर्टकट C से E तक जा रहा होता, जिसके परिणामस्वरूप एक छोटा मार्ग होता (A->B->C->E->D->A) यदि यह एक यूक्लिडियन ग्राफ है मार्ग A->B->C->D->E->A में प्रतिच्छेदी रेखाएँ हैं जो सिद्ध है कि यह सबसे छोटा मार्ग नहीं है।
 |}
+== संदर्भ                                                                                                                                                                                                          ==
-== संदर्भ ==
 {{reflist|30em}}
 ==बाहरी संबंध==
 * [https://xlinux.nist.gov/dads/HTML/christofides.html NIST Christofides Algorithm Definition]
-[[Category: 1976 कंप्यूटिंग में]] [[Category: ट्रैवलिंग सेल्समैन की समस्या]] [[Category: ग्राफ़ एल्गोरिदम]] [[Category: फैले पेड़]] [[Category: सन्निकटन एल्गोरिदम]]
-[[Category: Machine Translated Page]]
+[[Category:1976 कंप्यूटिंग में]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:CS1 русский-language sources (ru)]]
 [[Category:Created On 25/06/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:ग्राफ़ एल्गोरिदम]]
+[[Category:ट्रैवलिंग सेल्समैन की समस्या]]
+[[Category:फैले पेड़]]
+[[Category:सन्निकटन एल्गोरिदम]]

Anonymous

Search

क्रिस्टोफ़ाइड्स एल्गोरिथ्म: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 12:00, 14 July 2023

Contents

एल्गोरिथम

अनुमान अनुपात

निचली सीमा

उदाहरण

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

क्रिस्टोफ़ाइड्स एल्गोरिथ्म: Difference between revisions

Latest revision as of 12:00, 14 July 2023

एल्गोरिथम

अनुमान अनुपात

निचली सीमा

उदाहरण

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories