Traveling Salesman को कैसे मास्टर करें
TLDR: Traveling Salesman आपको हर शहर को एक बार और एक बार से अधिक नहीं, और सबसे छोटी संभव लूप का उपयोग करके घर वापस लौटने के लिए कहता है। शहरों को क्रम में टैप करें, जब सभी रूट पर हों, तो चेक दबाएं और केवल तब जीतें जब आपका दूरी सही ऑप्टिमम से मिलती है। जब आप हार जाते हैं, तो खेल आपको ऑप्टिमल रूट दिखाता है, इसलिए उसे अध्ययन करें - स्वयम्-क्रॉसिंग रूट्स लगभग हमेशा दोषी होते हैं, और उन्हें अनक्रॉस करने से टूर को छोटा कर दिया जाता है।
आप वास्तव में क्या हल कर रहे हैं
Traveling Salesman एक छोटा सा संस्करण है, जो कंप्यूटर विज्ञान के सबसे प्रसिद्ध समस्याओं में से एक है। आप एक बिखरे हुए शहरों के नक्शे पर घर के चिह्न से शुरू करते हैं। आपका काम बहुत आसान है और वास्तव में मुश्किल है: हर शहर को एक बार और एक बार से अधिक नहीं, फिर घर वापस लौटें, सबसे छोटी संभव कुल दूरी का उपयोग करें। कोई सूत्र, कोई शॉर्टकट नहीं है - आप सीधे ज्यामिति के बारे में सोचना चाहिए और पूरी रूट्स को एक दूसरे के खिलाफ तुलना करना चाहिए जब तक कि आप उसे नहीं पाते जो हरगिज नहीं हराया जा सकता।
खेल आपको वास्तविक समय में अपनी वर्तमान टूर की दूरी बताता है जब आप टैप करते हैं। जब सभी शहरों का दौरा किया जाता है, तो चेक दबाएं। अगर आपका लूप सही ऑप्टिमल हल से मिलता है, तो आप जीतते हैं और आगे बढ़ते हैं। अगर यह लंबा है, तो आप दोनों रूट्स को अपने साथ दिखा देते हैं ताकि आप देख सकें कि आप कहाँ गलत गए।
खेल को ताजा रखने वाला ट्विस्ट है वृद्धि। हर कुछ स्तरों के बाद, नक्शे में एक और शहर आता है। पांच शहर छह शहर बन जाते हैं, फिर सात। प्रत्येक जोड़ना छोटा लगता है, लेकिन संभव क्रमों की संख्या द्रामेटिक रूप से बढ़ जाती है। जो आप स्तर एक पर आँखों से देख सकते थे, स्तर दस पर एक वास्तविक ऑप्टिमाइजेशन चुनौती बन जाती है।
पूरी तरह से नियम
नक्शे का अध्ययन करने से शुरू करें। आप घर के चिह्न (आपका शुरू और अंतिम बिंदु) और उसके चारों ओर बिखरे हुए शहर देखेंगे। आपका रूट हमेशा घर से शुरू होता है और घर पर समाप्त होता है - आप केवल घर के शहरों को टैप करते हैं, जो लूप बनाते हैं।
शहरों को आप उन्हें दौरे करने के क्रम में टैप करें। रूट खुद को एक लाइन के रूप में खींचता है जो प्रत्येक टैप को जोड़ता है। दूरी गिनती आपके चल रहे कुल के साथ लाइव अपडेट होती है। अगर आप गलती करते हैं, तो गलत शहर को रूट से हटाने के लिए Undo का उपयोग करें, या पूरी रूट को मिटाने और फिर से शुरू करने के लिए Clear का उपयोग करें।
जब हर शहर टैप किया जाता है, तो चेक दबाएं। खेल आपका लूप को वास्तविक ऑप्टिमम से तुलना करता है जो हर संभव क्रम को जांचकर कंप्यूट किया जाता है। अगर वे मिलते हैं, तो आप जीतते हैं। अगर आपका लंबा है, तो आप दोनों रूट्स को एक साथ दिखा देते हैं ताकि आप देख सकें कि आप कहाँ गलत गए।
नियम कड़े हैं: हर शहर एक बार, लूप घर पर वापस बंद होना चाहिए, और आपका दूरी ऑप्टिमम से मिलना चाहिए ताकि जीत सकें। कोई अंशिक क्रेडिट या “काफी करीब” नहीं है।
सबसे महत्वपूर्ण पैटर्न: स्वयम्-क्रॉसिंग रूट्स
सिखने का सबसे महत्वपूर्ण चीज यह है कि आप कैसे स्वयम्-क्रॉसिंग रूट्स को पहचानें और उन्हें टालें। अधिकांश गैर-ऑप्टिमल टूर्स इसलिए विफल होते हैं क्योंकि पथ खुद को क्रॉस करता है। जब आपकी रूट के दो खंड एक दूसरे को काटते हैं, तो आप दूरी को बर्बाद कर रहे हैं - और उन्हें अनक्रॉस करने से टूर को छोटा करने के लिए लगभग हमेशा होता है।
यह इसलिए है: चार शहरों को एक खराब वर्ग के रूप में चित्रित करें। अगर आप उन्हें एक X के रूप में बनाते हैं - जहां रूट ऊपर से बाएं से नीचे दाएं, फिर ऊपर से दाएं से नीचे बाएं जाता है - तो वे दो खंड क्रॉस होते हैं। ऑप्टिमल टूर परिमार में जाता है: ऊपर बाएं, ऊपर दाएं, नीचे दाएं, नीचे बाएं। वही शहर, कोई क्रॉसिंग नहीं, छोटी कुल दूरी।
जब खेल आपको हारने के बाद ऑप्टिमल रूट दिखाता है, तो पहले देखें कि आपकी रूट कहाँ खुद को क्रॉस कर रही है। ऑप्टिमल हल उन क्रॉसिंग्स को उलझा देगा। अक्सर, आपकी क्रम में दो शहरों को बदलने से एक क्रॉसिंग को पूरी तरह से हटा दिया जाता है और आपका दूरी ऑप्टिमम तक पहुंच जाता है।
हर हार के बाद, आपकी रूट में क्रॉसिंग्स की गिनती करें, पहले ऑप्टिमल रूट को देखें। आप कितने इंटरसेक्शंस देख सकते हैं? ऑप्टिमल रूट ने सभी को हटा दिया होगा। फिर पहचानें कि कौन सा शहर स्वाप सबसे बुरे क्रॉसिंग को हटा देगा। यह तुलना है जहां सबसे ज्यादा सीखने का समय होता है - जीत से, बल्कि निदान हार से।
परिमार चलना। नए नक्शे पर, पहले मानसिक रूप से बाहरी सीमा को ट्रेस करें - शहर जो कॉन्वेक्स हल (बाहरी आकार) बनाते हैं। ऑप्टिमल रूट अक्सर इस परिमार को अनुसरण करता है, बाहरी शहरों को घड़ी की सुई या विपरीत घड़ी की सुई के क्रम में दौरे करते हुए, फिर किसी भी अंदरूनी शहरों को गैप में डालते हुए जहां वे कम अतिरिक्त दूरी का कारण बनते हैं। अपने टूर को किनारे से शुरू करें, फिर अंदरूनी शहरों को गैप में डालें जहाँ वे कम अतिरिक्त दूरी का कारण बनते हैं।
व्यवस्थित रूट निर्माण
शहरों को अराजक रूप से टैप करने और आशा करने से मत भूलें। रूट को कदम दर कदम बनाएं, स्थानीय फैसलों को बनाएं जो वापसी को कम करते हैं।
घर से शुरू करें और पूछें: मुझे पहले किस शहर को दौरा करना चाहिए? अक्सर यह सबसे करीब का शहर होता है, या एक दिशा में स्थित जो आपको नक्शे को बिना वापसी के सफाई करने देता है। इसे टैप करें।
हर शहर से पूछें - कौन सा अनदेखा शहर यहाँ से यात्रा करने के लिए अतिरिक्त दूरी को कम करता है? यह लालची रणनीति (हमेशा सबसे करीब या सबसे समझदारी के अगले ठहराव पर जाना) अक्सर ऑप्टिमम को नहीं देता, लेकिन यह एक सकारात्मक शुरुआती टूर बनाता है जिसे आप फिर से सुधार सकते हैं।
जब आपका पहला प्रयास रूट है, तो उसे मानसिक रूप से चलाएं। दूरी कहाँ बेकार लगती है? क्या एक लंबा खंड है जो नक्शे के पार फैला हुआ है जहां दो शहर जो दूर हैं, आपके टूर में पड़ोसी हैं? क्या दो शहरों को बदलने से एक क्रॉसिंग या उस लंबी छलांग को हटा दिया जा सकता है? ये छोटे स्थानीय सुधार अक्सर एक अच्छे टूर को ऑप्टिमल में बदल देते हैं।
निकटतम पड़ोसी, फिर सुधार करें। शहरों को लालची तरीके से टैप करें, हमेशा सबसे करीब अनदेखे ठहराव पर जाएं। अपनी दूरी नोट करें। फिर रूट को मानसिक रूप से चलाएं और एक क्रॉसिंग, एक वापसी, या एक असमर्थता पाएं। उस असमर्थता में शामिल दो शहरों को बदलें, रूट को बदलने के साथ फिर से टैप करें, और देखें कि क्या यह सुधार करता है। ऑप्टिमम से मिलने तक या स्पष्ट सुधार खत्म होने तक दोहराएं।
लालची नहीं है ऑप्टिमल। निकटतम पड़ोसी रणनीति प्राकृतिक लगती है लेकिन अक्सर दूरी को छोड़ देती है। शुरुआती स्तर इसे क्षमा कर सकते हैं, लेकिन जब शहरों की संख्या बढ़ती है, तो लालची टूर्स लगातार कम होते हैं। निकटतम पड़ोसी को एक तेज शुरुआती बिंदु के रूप में उपयोग करें, फिर सुधार करें - इसे अंतिम उत्तर के रूप में भरोसा नहीं करें।
आम गलतियाँ और उन्हें टालने के तरीके
अराजक क्रम में टैप करने और आशा करने। नक्शे की ज्यामिति महत्वपूर्ण है। पास-पास शहरों को आपका टूर में लगातार दिखाई देना चाहिए। क्लस्टर्स को एक समूह के रूप में दौरा करें, फिर अगले क्लस्टर पर जाएं। एक अराजक क्रम में अक्सर महंगे लंबे छलांग शामिल होते हैं जो एक ज्यामिति-आधारित क्रम से बचा जाता है।
एक हार के बाद अपने पहले टूर पर जमा होना। जब आप हार जाते हैं, तो केवल एक शहर को Undo करके और फिर से टैप करने से मत भूलें। खेल द्वारा दिखाए गए ऑप्टिमल रूट का अध्ययन करें। यह आपकी से कहाँ मूल रूप से अलग है? यह क्रम सिद्धांत किसे अनुसरण करता है जो आपका नहीं था? यह मेटा-दृष्टिकोण - पूरी रणनीतियों की तुलना, नहीं केवल एक-एक शहर - जहां वास्तविक सुधार होता है।
एक बहुत लंबा खंड एक संकेत है, एक संयोग नहीं। अगर आपके टूर में एक खंड है जो नक्शे के अधिकांश हिस्से में फैला हुआ है, तो यह लगभग हमेशा एक गलत क्रम का संकेत देता है। ऑप्टिमल रूट में कोई एक खंड नहीं होना चाहिए जो अन्य खंडों से बहुत लंबा हो - दूरी संतुलित लगनी चाहिए। एक अकेला लंबा छलांग अक्सर दो शहरों को संकेत करता है जो आपके टूर में पड़ोसी हैं जब वे नहीं होना चाहिए।
पांच शहरों के बाद एक बार में बंद होने का एहसास। Undo और Clear का स्वतंत्र रूप से उपयोग करें। अगर रूट पांच शहरों के बाद गलत लगता है, तो इसे मिटाएं और एक अलग शुरुआती दिशा का प्रयास करें। इटरेशन संघर्ष करने से तेज है।
एक यादगार सूत्र खोजने की कोशिश करना। हर नक्शा अलग है। “हमेशा घड़ी की सुई के क्रम में जाएं” या “हमेशा ऊपर से शुरू करें” अलग नक्शों पर काम नहीं करेगा। ऑप्टिमल रणनीति इस विशेष ज्यामिति पर निर्भर करती है। खुद को हर नए नक्शे को नया पढ़ने के लिए प्रशिक्षित करें, नहीं किसी याद की गई नियम का पालन करें।
किसी भी टैप करने से पहले 10 सेकंड नक्शे का अध्ययन करें। क्लस्टर्स कहाँ हैं? कौन सा शहर सबसे अलग है? नक्शे का रूखा आकार क्या है - यह फैला हुआ है या संकुचित? क्या एक शहर है जो सभी से दूर है और एक महंगे डिटूर के लिए आवश्यक है? ये अवलोकन आपकी पहली कुछ टैप्स को मार्गदर्शित करते हैं और अक्सर आपको ऑप्टिमल रूट तक ले जाते हैं पहले कि आप किसी दूरी को समर्पित करें।
जब कठिनाई बढ़ती है
शुरुआती स्तर में चार या पांच शहर होते हैं। संभव क्रमों की संख्या छोटी है। इस स्तर पर आप अक्सर टैप करने से पहले जवाब देख सकते हैं - बस नक्शे को स्कैन करें, सबसे प्राकृतिक लूप पहचानें, और इसे कार्यान्वित करें।
स्तर छह या सात पर, एक छठा शहर आता है। संभव रूट्स की संख्या द्रामेटिक रूप से बढ़ जाती है। आँखों से देखना भरोसा करने योग्य नहीं रहता। यह है जहां रणनीतिक कौशल आवश्यक होता है। आप ज्यामिति के बारे में सोचना चाहिए, क्रॉसिंग को पहचानना चाहिए, और रणनीतियों की तुलना करना चाहिए, नहीं केवल अंदाज लगाना।
हर कुछ स्तरों के बाद, एक और शहर जोड़ा जाता है। स्तर बारह से पंद्रह तक, आप सात या आठ शहरों का प्रबंधन कर रहे हैं। संभव रूट्स की संख्या लाखों में है। आप सभी को मानसिक रूप से जांच नहीं सकते। आप संरचनात्मक रूप से सोचना चाहिए - पैटर्न का उपयोग करें, स्पेशल इंस्टिंक्ट पर भरोसा करें, और प्रत्येक नक्शे को एक समस्या के रूप में समाधान करें जो हल करने के लिए है, नहीं एक क्रम को याद रखने के लिए।
बड़े नक्शों पर विभाजित और जीतें। शहरों को मानसिक रूप से क्लस्टर्स या क्षेत्रों में विभाजित करें। प्रत्येक क्षेत्र में एक दक्ष उप-टूर बनाएं, फिर क्षेत्रों को उस क्रम में जोड़ें जो अंतर-क्षेत्र दूरी को कम करता है। छोटे उप-समस्याओं को हल करने और फिर उन्हें मिलाने का एक भरोसा करने वाला तरीका है जब शहरों की संख्या छह या सात से अधिक हो जाती है।
अभ्यास रूटीन
हर सप्ताह तीन केंद्रित सत्र, लगभग 10 मिनट प्रत्येक, काफी हैं तेजी से सुधार को बनाना।
सत्र 1 - ज्यामिति अवलोकन। तीन राउंड खेलें बिना दौड़ने। किसी भी शहर को टैप करने से पहले, 15 सेकंड नक्शे के आकार को खुद से वर्णित करें: “शहर एक खराब ओवल बनाते हैं, एक अलग शहर बाएं है।” उस आकार को अपने टूर को मार्गदर्शित करने दें। नक्शे संरचना को पढ़ने का अभ्यास करें पहले कि आप किसी दूरी को समर्पित करें।
सत्र 2 - क्रॉसिंग हटाना। तीन राउंड खेलें। हर हार के बाद, एक पूर्ण मिनट अपने रूट को ऑप्टिमल से तुलना करें। अपने टूर में हर क्रॉसिंग की गिनती करें। पूछें: कौन सा एक स्वाप सबसे बुरे क्रॉसिंग को हटा देगा? यह जागरूक विश्लेषण है जहां लंबे समय के लिए इंस्टिंक्ट बनता है।
सत्र 3 - गति और स्थिरता। पांच राउंड खेलें और तीन में से तीन जीतने का प्रयास करें। राउंड तीन तक, आप सुधार को महसूस करेंगे - रूट निर्माण तेज है, क्रॉसिंग को पहचानना अधिक प्राकृतिक है, और आपका दूरी अधिक बार ऑप्टिमल से करीब है।
प्रगति का प्रतीक। आप सुधार कर रहे हैं जब आप एक राउंड में पहली कोशिश में जीतते हैं - जब आप नक्शे की ज्यामिति से ऑप्टिमल रूट को भविष्यवाणी कर सकते हैं और इसे बिना फीडबैक रिवील के कार्यान्वित कर सकते हैं। शुरुआती खिलाड़ी अक्सर हार जाते हैं; मध्यम खिलाड़ी अधिकांश राउंड जीतते हैं लेकिन उच्च शहरों की संख्या पर अभी भी कम होते हैं; उन्नत खिलाड़ी स्तर दस और उससे आगे तक लगातार जीतते हैं।
एक मानसिक पैटर्न लॉग बनाएं। हर राउंड के बाद नोट करें कि क्या काम किया: “परिमार पहले यहाँ सफल रहा” या “अलग शहर ऊपर बाएं को अंतिम में दौरा करना चाहिए था।” समय के साथ, ये अवलोकन एक साथ मिलकर एक स्पेशल इंस्टिंक्ट बनाते हैं जो सभी भविष्य के नक्शों पर लागू होता है, चाहे वे पहले कभी नहीं देखे गए हों।
अंतिम विचार
Traveling Salesman एक कौशल को प्रशिक्षित करता है जो खेलों से बहुत दूर तक पहुंचता है: स्पेशल व्यवस्था और ऑप्टिमाइजेशन के बारे में सोचने की क्षमता बिना किसी सूत्र के। आप इंजीनियरों द्वारा डिलीवरी रूट्स को डिजाइन करने, सर्जनों द्वारा ऑपरेटिंग स्टेप्स को क्रम में रखने, और वास्तुकारों द्वारा स्थानों को दक्षता से व्यवस्थित करने के लिए उसी सोच का उपयोग कर रहे हैं।
खेल आपके साथ बढ़ता है। शुरुआती राउंड्स आपको बुनियादी चीजें सिखाते हैं - शहरों को टैप करें, क्रॉसिंग को पहचानें, अपनी दूरी जांचें। बाद के राउंड्स गहन सोचने की मांग करते हैं - कई रोकों को संतुलित करना, पूरी तस्वीर को देखना, जब संभवताओं की संख्या बढ़ जाती है, तो स्पेशल इंस्टिंक्ट पर भरोसा करना।
जहाँ आप हैं, वहीं से शुरू करें। अपने क्षमता के किनारे पर बैठने वाले राउंड खेलें। हर हार से सीखने का समय लेना। ऑप्टिमल रूट हमेशा वहां है, उसे देखने के लिए प्रतीक्षा कर रहा है। आपका काम खुद को इसे तेजी से देखने के लिए प्रशिक्षित करना है।
ट्रैवलिंग सेल्समैन
सबसे छोटा मार्ग खोजें जो हर शहर में एक बार जाए · क्लासिक ट्रैवलिंग सेल्समैन समस्या
अभी खेलें - यह मुफ़्त हैकिसी खाते की ज़रूरत नहीं। किसी भी डिवाइस पर काम करता है।
