क्रस्कल और प्राइम के एल्गोरिदम के अनुप्रयोग

Question

क्या कोई भी दो एल्गोरिदम, के कुछ एप्लिकेशन दे सकता है, जहां और किस अनुप्रयोग के लिए उनका उपयोग किया जा सकता है?

Answer 1

न्यूनतम स्पैनिंग पेड़ों का पहली बार विद्युत नेटवर्क को बाहर निकालने के तरीकों के लिए अध्ययन किया गया था जिससे तारों की कुल लागत कम हो जाती है। न्यूनतम स्पैनिंग पेड़ में, सभी नोड्स (घर) तारों से बिजली से जुड़े होते हैं, जिसकी न्यूनतम लागत और अनावश्यकता होती है (किसी तार को काटने से बिजली के ग्रिड को दो टुकड़ों में काट दिया जाता है)।

तब से, समस्या का अच्छी तरह से अध्ययन किया गया है और अक्सर अधिक जटिल एल्गोरिदम में एक उपराउटिन के रूप में उपयोग किया जाता है। ट्रैवलिंग सेल्समैन समस्या के अनुमानित समाधान खोजने के लिए Christofides algorithm इसे एक महत्वपूर्ण चरण में उपयोग करता है, जैसे स्टीनर पेड़ ढूंढने के लिए कुछ एल्गोरिदम करते हैं।

न्यूनतम स्पैनिंग पेड़ भी generate mazes पर उपयोग किए गए हैं। क्रस्कल और प्राइम के एल्गोरिदम दोनों इस तरह इस्तेमाल किए जाते हैं, अक्सर उच्च गुणवत्ता वाले मैज बनाते हैं।

आप न्यूनतम स्पैनिंग ट्री समस्या, इसके अनुप्रयोग, और अपने एल्गोरिदम का एक पूरा इतिहास में रुचि रखते हैं, वहाँ वास्तव में एक उत्कृष्ट कागज available here कि इन सभी को शामिल किया गया है। मैं दृढ़ता से इसे पढ़ने के सुझाव देना चाहता हूँ!

आशा है कि इससे मदद मिलती है!

Answer 2

विकिपीडिया का हवाला देते हुए:

एक उदाहरण एक केबल टीवी एक नया पड़ोस के लिए केबल बिछाने कंपनी होगी। यदि यह केवल कुछ पथों के साथ केबल को दफनाने के लिए बाध्य है, तो वहां एक ग्राफ होगा जो दर्शाता है कि कौन से बिंदु उन पथों से जुड़े हुए हैं। उनमें से कुछ पथ अधिक महंगा हो सकते हैं, क्योंकि वे लंबे समय तक हैं, या केबल को गहरा दफन करने की आवश्यकता है; इन पथों को बड़े वजन वाले किनारों द्वारा दर्शाया जाएगा। उस ग्राफ के लिए एक स्पैनिंग पेड़ उन पथों का एक सबसेट होगा जिसमें चक्र नहीं हैं लेकिन फिर भी हर घर से जुड़ते हैं। कई फैलाने वाले पेड़ संभव हो सकते हैं। न्यूनतम स्पैनिंग पेड़ सबसे कम कुल लागत वाला होगा।

स्रोत: http://en.wikipedia.org/wiki/Minimum_spanning_tree

Answer 3

सबसे पहले आप यह समझना चाहिए कि दोनों रस्मी और Kruskal एल्गोरिथ्म एक ग्राफ में Minimum spanning Tree को खोजने के लिए उपयोगी होते हैं। न्यूनतम स्पैनिंग पेड़ के प्रैक्टिकल अनुप्रयोगों में से एक, मैं सोच सकता हूं कि एक ही कंपनी के विभिन्न कार्यालयों को कम से कम लागत से जोड़ना है।

Answer 4

• टोपोलॉजी
• नक्शानवीसी
• ज्यामिति
• क्लस्टरिंग
• मार्ग एल्गोरिदम
• Mazes की पीढ़ी
• मैकेनिकल/इलेक्ट्रिकल/कंप्यूटर नेटवर्क रसायन विज्ञान में आणविक बांड की
• अध्ययन

Answer 5

क्रस्कल और प्राइम के एल्गोरिदम के अनुप्रयोग अक्सर कंप्यूटर नेटवर्किंग में आते हैं। उदाहरण के लिए, यदि आपके पास कई स्विच के साथ एक बड़ा लैन है, तो न्यूनतम स्पैनिंग पेड़ ढूंढना यह सुनिश्चित करने के लिए महत्वपूर्ण होगा कि नेटवर्क पर केवल न्यूनतम संख्या में पैकेट प्रसारित किए जाएंगे।