English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng Việtरेखांकन और नेटवर्कयात्रा विक्रेता समस्या
आइए, एक बार और सोचें, नेटवर्क और मैप के बारे में। कल्पना कीजिए कि एक डिलीवरी सेवा पर जाना है
डिलीवरी ट्रक को सभी शहरों का दौरा करना है, किसी भी क्रम में। कोनिग्सबर्ग पुलों की समस्या में हम उन रास्तों को ढूंढना चाहते थे जो हर एक किनारे पर एक साथ यात्रा करते हैं। अब हम उन रास्तों को ढूंढना चाहते हैं जो हर शिखर पर एक ही बार आते हैं। इन रास्तों को हैमिल्टनियन चक्र कहा जाता है ।
संपूर्ण रेखांकन में हैमिल्टनियन चक्रों की अनगिनत अलग-अलग संभावनाएँ हैं। वास्तव में, हम किसी भी शीर्ष को वर्टेक्स शुरू करने के रूप में चुन सकते हैं और फिर किसी भी क्रम में शेष शहरों में से कोई भी चुन सकते हैं:
Diagram coming soon…
Diagram Coming Soon…
के साथ एक ग्राफ में
इसका मतलब है कि, कुल मिलाकर, वहाँ हैं ${tsnPaths(tsn1)} संभव पथ। इस उत्पाद के लिए एक आशुलिपि है ${tsn1} ! या ${tsn1} कारक ।
आप कल्पना कर सकते हैं कि दो शहरों के बीच सीधे यात्रा करना संभव नहीं हो सकता है - बिना किसी दूसरे शहर से गुजरे। उस मामले में अब हमारे पास पूरा ग्राफ नहीं है, और हैमिल्टनियन चक्रों की संख्या का पता लगाना, अगर वे बिल्कुल मौजूद हैं, तो यह और अधिक कठिन हो जाता है।
अब तक हमने इस तथ्य को नजरअंदाज कर दिया है कि कुछ शहर दूसरों की तुलना में आगे हो सकते हैं। वास्तविक जीवन में, हालांकि, यह एक बहुत ही महत्वपूर्ण विचार है: हम केवल कोई रास्ता नहीं खोजना चाहते हैं, लेकिन हम सबसे छोटा रास्ता खोजना चाहते हैं। इसे ट्रैवलिंग सेल्समैन प्रॉब्लम कहा जाता है। इसे न केवल परिवहन और रसद में, बल्कि माइक्रोचिप्स पर ट्रांजिस्टर की स्थिति, तेजी से कंप्यूटर बनाने के लिए, या
एक सरल तरीका यह होगा कि सभी संभव रास्तों को आज़माया जाए, प्रत्येक की लंबाई का पता लगाया जाए, और फिर सबसे छोटा रास्ता चुना जाए। हालाँकि हमने अभी-अभी भी, केवल साथ ही दिखाया है
दुर्भाग्य से यात्रा विक्रेता समस्या को हल करने के लिए अधिक कुशल एल्गोरिदम नहीं है। इसके बजाय, गणितज्ञों और कंप्यूटर वैज्ञानिकों ने विभिन्न एल्गोरिदम विकसित किए हैं जो अच्छे समाधान ढूंढते हैं, भले ही वे बहुत अच्छे न हों। ये एल्गोरिदम, जो केवल अनुमानित समाधान देते हैं, को Heuristics कहा जाता है।
इस नक्शे पर शहरों को फिर से व्यवस्थित करने का प्रयास करें, और देखें कि उनके बीच का सबसे छोटा रास्ता कैसे बदलता है। आप उन्हें टैप करके शहरों को निकाल सकते हैं, और आप मानचित्र पर कहीं भी (8 तक) क्लिक करके शहरों को जोड़ सकते हैं:
लालची एल्गोरिथ्म (या निकटतम पड़ोसी एल्गोरिथ्म) बहुत सरल है: आप एक यादृच्छिक शहर में शुरू करते हैं और लगातार उस निकटतम शहर में जाते हैं जिसे आपने पहले कभी नहीं देखा है। एक बार जब आप सभी शहरों का दौरा कर लेते हैं, तो आप रुक जाते हैं।
एनीमेशन जल्द ही आ रहा है ...
आप दिखा सकते हैं कि औसतन, लालची एल्गोरिथ्म का उपयोग करते हुए पाए जाने वाले मार्ग सबसे कम संभव पथ से 25% लंबे हैं।
2-ऑप्ट एल्गोरिथ्म एक यादृच्छिक संभव पथ के साथ शुरू होता है। फिर आप बार-बार दो किनारों को उठाते हैं और उन्हें चारों ओर स्वैप करते हैं यदि यह मार्ग की लंबाई कम कर देगा। जब आप किनारों की किसी भी जोड़ी को अदला-बदली करके लंबाई को कम नहीं कर सकते, तो आप रुक जाते हैं।
एनीमेशन जल्द ही आ रहा है ...
यह पता चला है कि, कंप्यूटरों के अस्तित्व में आने से बहुत पहले, प्रकृति ने विभिन्न स्थानों के बीच इष्टतम रास्तों को खोजने के लिए एक चतुर तरीका खोजा था: एंटी कॉलोनियों में।
चींटियाँ अपने घोंसले और संभव खाद्य स्रोतों के बीच सबसे कम संभव मार्गों को खोजना चाहती हैं। वे रसायनों के माध्यम से एक दूसरे के साथ संवाद कर सकते हैं जो वे अपने निशान के साथ छोड़ देते हैं, और जो अन्य चींटियों का पालन कर सकते हैं।
- चींटी कॉलोनी कई स्काउट्स को भेजती है जो शुरू में यादृच्छिक दिशाओं में यात्रा करते हैं। एक बार जब वे भोजन पा लेते हैं, तो वे फेरोमोन के निशान को पीछे छोड़ते हैं। * अन्य चींटियाँ जब किसी एक को खोजती हैं, तो उसका पीछा करती हैं, जो उन्हें भोजन की ओर ले जाती हैं। अपनी वापसी यात्रा पर वे अधिक फेरोमोन जमा करते हैं, इस प्रकार निशान को मजबूत करते हैं। * समय के साथ, फेरोमोन वाष्पित हो जाता है। एक रास्ता लंबा है, चींटियों को इसके साथ यात्रा करने में अधिक समय लगता है, और इसलिए फेरोमोन को वाष्पित होने में अधिक समय लगता है। दूसरी ओर, छोटे रास्ते, अधिक तेजी से प्रबलित हो सकते हैं, इसलिए उनकी ताकत तेजी से बढ़ जाती है।
जल्द ही आ रहा है आरेख ...
चींटी कॉलोनी सिस्टम (एसीएस) एल्गोरिदम कई "आभासी" चींटियों का उपयोग करते हुए, कंप्यूटर पर इस व्यवहार को दोहराने की कोशिश करते हैं। वे यात्रा सेल्समैन समस्या के लिए बहुत अच्छे समाधान पा सकते हैं।
एसीएस एल्गोरिदम की एक विशेष रूप से उपयोगी संपत्ति यह है कि वे लगातार चल सकते हैं और ग्राफ में बदलाव के लिए वास्तविक समय में अनुकूलित कर सकते हैं। ये परिवर्तन कार दुर्घटनाओं और सड़क नेटवर्क पर सड़क के बंद होने या कंप्यूटर नेटवर्क पर वेब सर्वर पर ट्रैफिक स्पाइक्स के कारण हो सकते हैं।
ट्रैवलिंग सेल्समैन की समस्या
तेज़ और सटीक एल्गोरिदम खोजने से कंप्यूटर विज्ञान के क्षेत्र में गंभीर प्रभाव पड़ेगा: इसका मतलब होगा कि सभी एनपी-हार्ड समस्याओं के लिए तेज़ एल्गोरिदम हैं। यह अधिकांश इंटरनेट सुरक्षा को बेकार कर देगा, जो इस तथ्य पर निर्भर करता है कि कुछ समस्याओं को कंप्यूटर के लिए बहुत मुश्किल माना जाता है।
ट्रैवलिंग सेल्समैन की समस्या को हल करने के लिए एक तेज़ एल्गोरिथम खोजने से गणित और कंप्यूटर विज्ञान में सबसे प्रसिद्ध खुली समस्याओं में से एक, पी एनपी समस्या का समाधान होगा। यह सात