कोरिया के 81,998 बारों तक पैदल जाने का सबसे छोटा मार्ग 178 दिन का है

xguru · 2025-04-23T09:31:02+09:00

University of Waterloo के प्रोफेसर William Cook ने Traveling Salesman Problem (TSP) का दुनिया का पहला ऐसा उदाहरण गणना किया है, जिसमें कोरिया के 81,998 बारों तक जाने वाला सबसे छोटा मार्ग निकाला गया Open Source Routing Machine (OSRM) का उपयोग करके लगभग 3.3 अरब जोड़ों के पैदल चलने के समय की गणना की गई और गणितीय रूप से यह सिद्ध किया गया कि यही सर्वोत्तम मार्ग है गणना के अनुसार, बिना रुके चलने पर कुल 15,386,177 सेकंड, यानी 178 दिन 1 घंटा 56 मिनट 17 सेकंड लगेंगे TSP optimization के लिए LKH और Concorde tools का उपयोग किया गया, और cutting-plane method लागू किया गया यह पहले के अधिकतम विज़िट मार्ग नीदरलैंड के 57,912 मार्ग से आगे निकलने वाला दुनिया का सबसे बड़ा road-based TSP solved case है कोरिया के सभी बारों तक पैदल जाने वाला Traveling Salesman Problem कोरिया में मौजूद 81,998 बारों तक जाकर फिर वापस लौटने वाला सबसे छोटा मार्ग निकाला गया दुनिया में पहली बार इतने अधिक स्थानों वाला TSP problem optimally solve किया गया बारों के बीच कुल 3,361,795,003 जोड़ों के पैदल समय की गणना OSRM - Open Source Routing Machine से की गई गणितीय रूप से इससे छोटा कोई मार्ग मौजूद नहीं है विज़िट पॉइंट्स की संख्या के आधार पर यह TSP problem अब तक का सबसे बड़ा है सबसे छोटे मार्ग में लगने वाला समय निकाले गए optimal route पर बिना रुके चलने पर कुल 15,386,177 सेकंड लगते हैं यह 178 दिन 1 घंटा 56 मिनट 17 सेकंड के बराबर है वास्तविकता में चलते हुए आराम करना या पीना होगा, इसलिए इसे ठीक-ठीक पूरा करना कठिन होगा OSRM-आधारित walking times के अनुसार यह ऐसा optimal route है जिसमें 1 सेकंड भी कम नहीं किया जा सकता TSP का ऐतिहासिक संदर्भ और नया रिकॉर्ड पिछला सबसे बड़ा रिकॉर्ड नीदरलैंड के 57,912 बिंदुओं वाले साइकिल मार्ग का था यह korea81998 route उससे भी बड़े पैमाने का TSP solution case है गणना दिसंबर 2024 से मार्च 2025 तक Roskilde University और University of Waterloo में की गई विस्तृत गणना अलग calculation page पर देखी जा सकती है मार्ग को विज़ुअलाइज़ करने का तरीका मार्ग को interactive map पर देखा जा सकता है, और इसे 7 क्षेत्रों में बाँटकर एक्सप्लोर किया जा सकता है अलग-अलग visualization modes (color distance map, grayscale आदि) उपलब्ध हैं मार्ग के कुछ high-resolution images अलग से दिए गए हैं शहरों के close-up views city pages पर उपलब्ध हैं TSP हल करने की रणनीति और गलतफहमियाँ कुछ मीडिया रिपोर्टों में कहा जाता है कि “सिर्फ 22 शहरों” के लिए भी 1000 साल लगेंगे, लेकिन उसका मतलब हर संभव मार्ग को random तरीके से आज़माना है वास्तव में advanced optimization techniques की मदद से बहुत अधिक बिंदुओं वाले cases भी solve किए जा सकते हैं korea81998 के मामले में संभावित मार्गों की संख्या 2 के बाद 367,308 शून्य लगे हुए एक संख्या के बराबर है समाधान के लिए LKH(Lin-Kernighan Heuristic) algorithm और Concorde TSP Solver - cutting-plane method का संयोजन उपयोग हुआ cutting-plane method का संक्षिप्त परिचय यह linear programming पर आधारित है सड़क के उपयोग या न उपयोग की जगह connectivity की degree को 0 से 1 के बीच के मान से व्यक्त किया जाता है चरण-दर-चरण constraints जोड़कर सबसे छोटा मार्ग निकाला जाता है विस्तृत व्याख्या Scientific American और YouTube lecture में देखी जा सकती है P बनाम NP समस्या TSP problem एक NP-complete problem है और P बनाम NP समस्या का प्रतिनिधि उदाहरण है इससे जुड़ी रोचक चर्चा प्रोफेसर Lance Fortnow के paper में दी गई है यह computer science की सबसे प्रसिद्ध अनसुलझी समस्याओं में से एक है गणितीय optimization का महत्व यह project general-purpose optimization methods के प्रयोग और विकास के लिए एक आधार है industry, commerce, medicine और environment जैसे क्षेत्रों में इसके अनुप्रयोग की संभावना बहुत अधिक है mathematical modeling सीमित संसाधनों का प्रभावी उपयोग करने का एक महत्वपूर्ण उपकरण है शोधकर्ताओं का परिचय William Cook: कनाडा, University of Waterloo Daniel Espinoza: चिली, Alicanto Labs Marcos Goycoolea: चिली, Adolfo Ibáñez University Keld Helsgaun: डेनमार्क, Roskilde University आभार IBM CPLEX Optimizer: निःशुल्क अकादमिक शोध उपयोग के लिए उपलब्ध कराने हेतु धन्यवाद नक्शा Leaflet, OpenStreetMap, Carto, Stadia Maps की मदद से बनाया गया डॉ. Eom Sang-il ने कोरिया की राष्ट्रीय पुलिस एजेंसी के डेटा पर आधारित बार-लोकेशन डेटा उपलब्ध कराया पैदल समय की गणना OSRM से की गई अन्य देशों के TSP project उदाहरण जापान: 40,426 convenience stores यूके: 49,687 बार अमेरिका: 49,603 ऐतिहासिक स्थान नीदरलैंड: 57,912 स्मारक अतिरिक्त अध्ययन सामग्री In Pursuit of the Traveling Salesman: TSP का इतिहास और अनुप्रयोग Traveling Salesman Problem: cutting-plane method के उपयोग पर अध्ययन The Golden Ticket: P vs. NP समस्या का परिचय Opt Art: TSP का उपयोग कर कलात्मक छवियाँ बनाना Approximation Algorithms: TSP approximation algorithms पर नवीनतम शोध Computational Solutions for TSP Applications: 1994 में प्रकाशित अनुप्रयोग मामलों की पुस्तक

(math.uwaterloo.ca)

23 पॉइंट द्वारा xguru 2025-04-23 | 10 टिप्पणियां | WhatsApp पर शेयर करें

University of Waterloo के प्रोफेसर William Cook ने Traveling Salesman Problem (TSP) का दुनिया का पहला ऐसा उदाहरण गणना किया है, जिसमें कोरिया के 81,998 बारों तक जाने वाला सबसे छोटा मार्ग निकाला गया
Open Source Routing Machine (OSRM) का उपयोग करके लगभग 3.3 अरब जोड़ों के पैदल चलने के समय की गणना की गई और गणितीय रूप से यह सिद्ध किया गया कि यही सर्वोत्तम मार्ग है
गणना के अनुसार, बिना रुके चलने पर कुल 15,386,177 सेकंड, यानी 178 दिन 1 घंटा 56 मिनट 17 सेकंड लगेंगे
TSP optimization के लिए LKH और Concorde tools का उपयोग किया गया, और cutting-plane method लागू किया गया
यह पहले के अधिकतम विज़िट मार्ग नीदरलैंड के 57,912 मार्ग से आगे निकलने वाला दुनिया का सबसे बड़ा road-based TSP solved case है

कोरिया के सभी बारों तक पैदल जाने वाला Traveling Salesman Problem

कोरिया में मौजूद 81,998 बारों तक जाकर फिर वापस लौटने वाला सबसे छोटा मार्ग निकाला गया
दुनिया में पहली बार इतने अधिक स्थानों वाला TSP problem optimally solve किया गया
बारों के बीच कुल 3,361,795,003 जोड़ों के पैदल समय की गणना OSRM - Open Source Routing Machine से की गई
गणितीय रूप से इससे छोटा कोई मार्ग मौजूद नहीं है
विज़िट पॉइंट्स की संख्या के आधार पर यह TSP problem अब तक का सबसे बड़ा है

सबसे छोटे मार्ग में लगने वाला समय

निकाले गए optimal route पर बिना रुके चलने पर कुल 15,386,177 सेकंड लगते हैं
यह 178 दिन 1 घंटा 56 मिनट 17 सेकंड के बराबर है
वास्तविकता में चलते हुए आराम करना या पीना होगा, इसलिए इसे ठीक-ठीक पूरा करना कठिन होगा
OSRM-आधारित walking times के अनुसार यह ऐसा optimal route है जिसमें 1 सेकंड भी कम नहीं किया जा सकता

TSP का ऐतिहासिक संदर्भ और नया रिकॉर्ड

पिछला सबसे बड़ा रिकॉर्ड नीदरलैंड के 57,912 बिंदुओं वाले साइकिल मार्ग का था
यह korea81998 route उससे भी बड़े पैमाने का TSP solution case है
गणना दिसंबर 2024 से मार्च 2025 तक Roskilde University और University of Waterloo में की गई
विस्तृत गणना अलग calculation page पर देखी जा सकती है

मार्ग को विज़ुअलाइज़ करने का तरीका

मार्ग को interactive map पर देखा जा सकता है, और इसे 7 क्षेत्रों में बाँटकर एक्सप्लोर किया जा सकता है
अलग-अलग visualization modes (color distance map, grayscale आदि) उपलब्ध हैं
मार्ग के कुछ high-resolution images अलग से दिए गए हैं
शहरों के close-up views city pages पर उपलब्ध हैं

TSP हल करने की रणनीति और गलतफहमियाँ

कुछ मीडिया रिपोर्टों में कहा जाता है कि “सिर्फ 22 शहरों” के लिए भी 1000 साल लगेंगे, लेकिन उसका मतलब हर संभव मार्ग को random तरीके से आज़माना है
वास्तव में advanced optimization techniques की मदद से बहुत अधिक बिंदुओं वाले cases भी solve किए जा सकते हैं
korea81998 के मामले में संभावित मार्गों की संख्या 2 के बाद 367,308 शून्य लगे हुए एक संख्या के बराबर है
समाधान के लिए LKH(Lin-Kernighan Heuristic) algorithm और Concorde TSP Solver - cutting-plane method का संयोजन उपयोग हुआ

cutting-plane method का संक्षिप्त परिचय

यह linear programming पर आधारित है
सड़क के उपयोग या न उपयोग की जगह connectivity की degree को 0 से 1 के बीच के मान से व्यक्त किया जाता है
चरण-दर-चरण constraints जोड़कर सबसे छोटा मार्ग निकाला जाता है
विस्तृत व्याख्या Scientific American और YouTube lecture में देखी जा सकती है

P बनाम NP समस्या

TSP problem एक NP-complete problem है और P बनाम NP समस्या का प्रतिनिधि उदाहरण है
इससे जुड़ी रोचक चर्चा प्रोफेसर Lance Fortnow के paper में दी गई है
यह computer science की सबसे प्रसिद्ध अनसुलझी समस्याओं में से एक है

गणितीय optimization का महत्व

यह project general-purpose optimization methods के प्रयोग और विकास के लिए एक आधार है
industry, commerce, medicine और environment जैसे क्षेत्रों में इसके अनुप्रयोग की संभावना बहुत अधिक है
mathematical modeling सीमित संसाधनों का प्रभावी उपयोग करने का एक महत्वपूर्ण उपकरण है

शोधकर्ताओं का परिचय

William Cook: कनाडा, University of Waterloo
Daniel Espinoza: चिली, Alicanto Labs
Marcos Goycoolea: चिली, Adolfo Ibáñez University
Keld Helsgaun: डेनमार्क, Roskilde University

आभार

IBM CPLEX Optimizer: निःशुल्क अकादमिक शोध उपयोग के लिए उपलब्ध कराने हेतु धन्यवाद
नक्शा Leaflet, OpenStreetMap, Carto, Stadia Maps की मदद से बनाया गया
डॉ. Eom Sang-il ने कोरिया की राष्ट्रीय पुलिस एजेंसी के डेटा पर आधारित बार-लोकेशन डेटा उपलब्ध कराया
पैदल समय की गणना OSRM से की गई

अन्य देशों के TSP project उदाहरण

जापान: 40,426 convenience stores
यूके: 49,687 बार
अमेरिका: 49,603 ऐतिहासिक स्थान
नीदरलैंड: 57,912 स्मारक

अतिरिक्त अध्ययन सामग्री

In Pursuit of the Traveling Salesman: TSP का इतिहास और अनुप्रयोग
Traveling Salesman Problem: cutting-plane method के उपयोग पर अध्ययन
The Golden Ticket: P vs. NP समस्या का परिचय
Opt Art: TSP का उपयोग कर कलात्मक छवियाँ बनाना
Approximation Algorithms: TSP approximation algorithms पर नवीनतम शोध
Computational Solutions for TSP Applications: 1994 में प्रकाशित अनुप्रयोग मामलों की पुस्तक

10 टिप्पणियां

ep6tri 2025-04-24

अंग्रेज़ी पेज https://www.math.uwaterloo.ca/tsp/korea/index.html है।
यह टूर निश्चित रूप से अवास्तविक है। ऐसा लगता है कि मुख्यभूमि से Jeju-do या Ulleungdo जाते समय जहाज़ से जाने वाले समुद्री मार्गों को इसमें शामिल नहीं किया गया है। यह चित्र देखिए: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png

मकसद शायद यात्रा में लगने वाले अनुमानित समय की बिल्कुल सटीक गणना करना नहीं, बल्कि इस बात को महत्व देना है कि TSP को वास्तविक दुनिया के डेटा के साथ हल करके दिखाया गया।

skshin 2025-04-23

द्वीपों तक आना-जाना कैसे होगा? पैदल?

halfenif 2025-04-23

walking and ferry लिखा हुआ है, तो लगता है कि फेरी से भी जाते हैं।

woalsdnd 2025-04-23

जो जगहें रीयल-टाइम में खुलती और बंद हो जाती हैं, उनका क्या किया जाए?

majorika 2025-04-23

> मुझे मार्च 2024 में Daejeon स्थित KAIST में TSP पर एक लेक्चर देने का कार्यक्रम था, और मैं Daejeon TSP टूर के लिए एक स्थानीय डेटा सेट खोज रहा था। दिसंबर 2023 में डॉ. Eom Sang-il ने मुझे ईमेल करके लिखा, "क्या आपको National Police Agency द्वारा बनाया गया देशभर के bar का डेटा सेट चाहिए? नवीनतम फ़ाइल 1,000 won की है और इसमें 90,680 एंट्री हैं।" वाह। पहले यह जाँच लेने के बाद कि 1,000 won 1 डॉलर से कम है या नहीं (यह देख लेना अच्छा था कि exchange rate उलटी तो नहीं हो गई), मैंने जवाब दिया, "धन्यवाद!"

https://www.math.uwaterloo.ca/tsp/korea/sk_data.html

kimjoin2 2025-04-23

वाह, इसके पीछे ऐसी पृष्ठभूमि थी। संकलन और साझा करने के लिए धन्यवाद

kimjoin2 2025-04-23

मैं यह भी जानना चाहता हूँ कि कोरिया को ही चुनने की वजह क्या थी 👀

firea32 2025-04-28

शायद इसमें यह बात भी एक कारण रही होगी कि 1000 won में अच्छी क्वालिटी का डेटा मिल सकता था :)