बिटोनिक टूर
कम्प्यूटेशनल ज्यामिति में, यूक्लिडियन प्लेन या यूक्लिडीयन समष्टि में बिंदु (ज्यामिति) साइटों के एक समुच्चय का बिटोनिक टूर एक सवृत बहुभुज श्रृंखला है जिसमें प्रत्येक साइट इसके शीर्षों में से एक कोने रूप में होती है, जैसे कि कोई भी ऊर्ध्वाधर रेखा (ज्यामिति) श्रृंखला को अधिकतम दो बार पार करती है।
इष्टतम बिटोनिक टूर
इष्टतम बिटोनिक टूर न्यूनतम कुल लंबाई का बिटोनिक टूर है। यह बहुपद समय एल्गोरिदम तैयार करने के लिए गतिशील प्रोग्रामिंग में एक मानक अभ्यास है जो इष्टतम बिटोनिक टूर का निर्माण करता है।[1][2] हालाँकि इस तरह से इसे हल करने की सामान्य विधि में समय लगता है , समय के साथ एक तेज़ एल्गोरिदम ज्ञात है।[3]
इष्टतम बिटोनिक टूर के निर्माण की समस्या का श्रेय प्रायः जॉन एल. बेंटले को दिया जाता है, जिन्होंने 1990 में ट्रैवलिंग सेल्समैन की समस्या के लिए कई अनुमानों की एक प्रयोगात्मक तुलना प्रकाशित की थी;[4] हालाँकि, बेंटले के प्रयोगों में बिटोनिक टूर सम्मिलित नहीं हैं। बिटोनिक टूर समस्या का वर्णन करने वाला पहला प्रकाशन 1990 का एक नया प्रकाशन प्रतीत होता है, थॉमस एच. कॉर्मेन, चार्ल्स ई. लेइसर्सन और रॉन रिवेस्ट द्वारा लिखित पाठ्यपुस्तक एल्गोरिदम का परिचय का पहला संस्करण, जिसमें बेंटले को समस्या के प्रवर्तक के रूप में सूचीबद्ध किया गया है।
गुण
इष्टतम बिटोनिक टूर में कोई स्व-क्रॉसिंग नहीं है, क्योंकि त्रिकोण असमानता के कारण क्रॉस करने वाले किसी भी दो किनारों को कम पूर्ण लंबाई के साथ किनारों की एक अनक्रॉस जोड़ी द्वारा प्रतिस्थापित किया जा सकता है। इसलिए, यह इनपुट का बहुभुजीकरण बनाता है।
जब अन्य दौरों से तुलना की जाती है जो बिटोनिक नहीं हो सकते हैं, इष्टतम बिटोनिक टूर वह है जो क्षैतिज गति की पूर्ण मात्रा को कम करता है, जिसमें यूक्लिडियन दूरी से संबंध टूट जाते हैं।[5]
भिन्न पूर्णांक वाले समतल में बिंदुओं के लिए -निर्देशांक और वास्तविक संख्या के साथ -निर्देशांक जो लंबाई के अंतराल के भीतर स्थित होते हैं या उससे कम, इष्टतम बिटोनिक टूर एक इष्टतम यात्रा विक्रेता टूर है।[6]
अन्य अनुकूलन मानदंड
वही गतिशील प्रोग्रामिंग एल्गोरिदम जो इष्टतम बिटोनिक टूर पाता है, का उपयोग ट्रैवलिंग सेल्समैन समस्या के अन्य वेरिएंट को हल करने के लिए किया जा सकता है जो समन्वय दिशाओं की एक निश्चित संख्या में गति के शब्दावली क्रम संयोजन को कम करता है।[5]
1993 में मेंडोज़ा, अर्जेंटीना में सूचना विज्ञान में 5वें अंतर्राष्ट्रीय ओलंपियाड में, प्रतियोगिता की समस्याओं में से एक में बिटोनिक टूर सम्मिलित थे: प्रतियोगियों को एक एल्गोरिदम तैयार करना था जो इनपुट के रूप में साइटों का एक समुच्चय और साइटों के बीच अनुमत किनारों का एक संग्रह लेता था और एक निर्माण करता था। उन किनारों का उपयोग करके बिटोनिक टूर जिसमें यथासंभव अधिक साइटें सम्मिलित थीं। इष्टतम बिटोनिक टूर की तरह, इस समस्या को गतिशील प्रोग्रामिंग द्वारा हल किया जा सकता है।[7][8]
संदर्भ
- ↑ Introduction to Algorithms, 3rd ed., T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein, MIT Press, 2009. Problem 15-3, p. 405.
- ↑ Bird, Richard S.; De Moor, Oege (1997), The Algebra of Programming, Prentice Hall, p. 213, ISBN 9780135072455.
- ↑ de Berg, Mark; Buchin, Kevin; Jansen, Bart M. P.; Woeginger, Gerhard (2016), "Fine-Grained Complexity Analysis of Two Classic TSP Variants", in Chatzigiannakis, Ioannis; Mitzenmacher, Michael; Rabani, Yuval; Sangiorgi, Davide (eds.), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 55, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 5:1–5:14, doi:10.4230/LIPIcs.ICALP.2016.5, ISBN 978-3-95977-013-2
- ↑ Bentley, Jon L. (1990), "Experiments on traveling salesman heuristics", Proc. 1st ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 91–99, ISBN 9780898712513.
- ↑ 5.0 5.1 Sourd, Francis (2010), "Lexicographically minimizing axial motions for the Euclidean TSP", Journal of Combinatorial Optimization, 19 (1): 1–15, doi:10.1007/s10878-008-9154-0, MR 2579501, S2CID 42168298.
- ↑ Alkema, Henk; de Berg, Mark; Kisfaludi-Bak, Sándor (2020), "Euclidean TSP in Narrow Strips", in Cabello, Sergio; Chen, Danny Z. (eds.), 36th International Symposium on Computational Geometry (SoCG 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 164, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 4:1–4:16, doi:10.4230/LIPIcs.SoCG.2020.4, ISBN 978-3-95977-143-6, S2CID 219554488
- ↑ IOI'93 contest problems and report.
- ↑ Guerreiro, Pedro (December 2003), The Canadian Airline Problem and the Bitonic Tour: Is This Dynamic Programming?, Departamento de Informática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa.
