दक्षिण कोरिया के 81,998 बारों का सबसे छोटा पैदल मार्ग

 (math.uwaterloo.ca)
2 पॉइंट द्वारा GN⁺ 2025-04-25 | 2 टिप्पणियां | WhatsApp पर शेयर करें
  • Travelling Salesman Problem (TSP) को दक्षिण कोरिया के 81,998 बारों तक पहुंचने वाले सबसे छोटे मार्ग को खोजने की समस्या के रूप में हल किया गया, जिसमें Open Source Routing Machine (OSRM) का उपयोग किया गया
  • यह मार्ग 178 दिनों से अधिक समय लेने वाला सर्वोत्तम मार्ग है, और इसे OSRM की गणना के माध्यम से सिद्ध किया गया
  • LKH code और Concorde code का उपयोग करके cutting-plane method लागू किया गया, जिससे बड़े पैमाने की TSP समस्या हल की गई
  • गणितीय अनुकूलन और operations research संसाधन दक्षता बढ़ाने के लिए उपकरण विकसित करने पर केंद्रित हैं
  • यह शोध Roskilde University और University of Waterloo में किया गया, और इसमें IBM CPLEX Optimizer तथा Leaflet लाइब्रेरी का उपयोग हुआ

दक्षिण कोरिया के 81,998 बारों तक पहुंचने वाला सबसे छोटा मार्ग

  • Travelling Salesman Problem (TSP) को दक्षिण कोरिया के 81,998 बारों तक पहुंचने वाले सबसे छोटे मार्ग को खोजने की समस्या के रूप में हल किया गया, जिसमें Open Source Routing Machine (OSRM) का उपयोग किया गया
  • यह मार्ग 178 दिनों से अधिक समय लेने वाला सर्वोत्तम मार्ग है, और इसे OSRM की गणना के माध्यम से सिद्ध किया गया
  • LKH code और Concorde code का उपयोग करके cutting-plane method लागू किया गया, जिससे बड़े पैमाने की TSP समस्या हल की गई

बड़े पैमाने की TSP समस्या का समाधान

  • गणितीय अनुकूलन और operations research संसाधन दक्षता बढ़ाने के लिए उपकरण विकसित करने पर केंद्रित हैं
  • यह शोध Roskilde University और University of Waterloo में किया गया, और इसमें IBM CPLEX Optimizer तथा Leaflet लाइब्रेरी का उपयोग हुआ

शोध दल और आभार

  • शोध दल में William Cook, Daniel Espinoza, Marcos Goycoolea, Keld Helsgaun शामिल थे
  • शोध में IBM के CPLEX Optimizer और Leaflet लाइब्रेरी का उपयोग किया गया
  • Korean National Police Agency के डेटाबेस के माध्यम से दक्षिण कोरिया के बारों के स्थान प्राप्त किए गए

संबंधित पढ़ाई

2 टिप्पणियां

 
xguru 2025-04-25

मैंने कोरिया के 81,998 pubs को पैदल घूमने वाले सबसे छोटे रूट के 178 दिन वाले पोस्ट को Hacker News पर GeekNews अकाउंट से डाला था।
उसे बहुत वोट मिले, इसलिए वह 6 घंटे तक टॉप पर रहा, फिर लोकप्रिय पोस्ट बन गया और दोबारा GN+ में इंपोर्ट(?) हो गया।

उस पोस्ट में अंग्रेज़ी भी साथ में थी, इसलिए मैंने ऐसा करके देखा था; आगे भी जिन पोस्टों में अंग्रेज़ी शामिल होगी, उन्हें कभी-कभी Hacker News पर डालने की कोशिश करूँगा.
 
GN⁺ 2025-04-25
Hacker News की राय
  • 13.3 करोड़ edges वाला TSP solution प्रभावशाली है
    • यह tour सबसे छोटे route से 1.0038 गुना लंबा है
    • Bell Labs के probabilistic algorithm का उपयोग करने पर नतीजा कितना खराब होता, यह जानना दिलचस्प होगा
  • क्लासिक TSP approach की व्याख्या
    • सभी nodes को एक यादृच्छिक path में जोड़ें
    • path को दो जगह से काटकर तीन हिस्सों में बाँटें
    • उन तीन हिस्सों को छह संभावित तरीकों से फिर से व्यवस्थित करें और सबसे छोटा चुनें
    • सुधार न होने तक चरण 2-3 दोहराएँ
    • यह optimal result की गारंटी नहीं देता, लेकिन अधिकांश वास्तविक समस्याओं में optimal या उसके बहुत करीब होता है
  • कुल दूरी का ज़िक्र न होना अजीब है
    • उद्देश्य travel time को हल करना है, लेकिन वास्तविक travel distance जानना भी रोचक होगा
    • calories burn की गणना की जा सकती है या यह देखा जा सकता है कि route सबसे छोटी दूरी वाले path से कितना भटका
  • Ohio के आकार के देश में लगभग 82 हज़ार bars होने की बात ही चकरा देने वाली है
  • COVID के दौरान CityStrides का उपयोग करके अपने शहर की हर सड़क पर चलने का लक्ष्य बनाया था
    • यह चली गई दूरी को track करता है और बताता है कि आपने शहर का कितना प्रतिशत पैदल कवर किया है
    • इसने routes को optimize नहीं किया, लेकिन बिना दोहराव के जितनी ज़्यादा दूरी चल सकूँ, यह एक मज़ेदार मानसिक पहेली थी
    • automation tools भी मज़ेदार हो सकते हैं, लेकिन इसे हाथ से करना ही यात्रा का हिस्सा था
    • CityStrides साइट पर घूमते हुए लोगों के LifeMaps देखे जा सकते हैं
    • कुछ लोग हैरान कर देने वाली मात्रा में चलते हैं
  • 60 के दशक में Irish army का एक सवाल याद आ गया
    • "Bachelor's Walk से Collins Barracks तक bar के पास से गुज़रे बिना कैसे जाओगे?"
    • जवाब था "हर bar के अंदर जाकर"
  • इस dataset को ढूँढना प्रभावशाली है, लेकिन यह और कठिन नहीं है
    • यह traveling salesman के अंतिम record को तोड़ने और computation पूरा न कर पाने के बीच का एक सूक्ष्म संतुलन है
  • NP फिर से P जैसा लग रहा है
    • स्कूल में सीखा था कि 13 अधिकतम है, और 80 के दशक में एक professor ने इसे 15 तक बढ़ाया
    • उसके बाद 20, 20,000, और इस बार 80,000 साबित हो गया
    • World TSP page पर record 10 लाख है
    • अभी का सबसे बड़ा proven optimum 3,178,031 है
    • इसे CUDA से करना चाहिए, सामान्य C से नहीं
  • Branch-and-bound एक "textbook से निकला" algorithm है
    • अगर LP solver को black box मानें, तो यह मूल रूप से बहुत सरल है, लेकिन बहुत उपयोगी है
  • लगता है कुछ नए bars खुल गए हैं और कुछ बंद हो गए हैं
    • फिर से calculation करने का समय है