विभाजन शोधन

From alpha
Jump to navigation Jump to search

एल्गोरिदम के डिजाइन में, विभाजन शोधन एक डेटा संरचना के रूप में एक सेट के विभाजन का प्रतिनिधित्व करने के लिए एक तकनीक है जो विभाजन को अपने सेटों को बड़ी संख्या में छोटे सेटों में विभाजित करके परिष्कृत करने की अनुमति देता है। इस अर्थ में अलग करना सेट डेटा स्ट्रक्चर | यूनियन-फाइंड डेटा स्ट्रक्चर के लिए दोहरी है, जो विभाजन को अलग-अलग सेटों में भी बनाए रखता है, लेकिन जिसमें ऑपरेशन सेट के जोड़े को मिलाते हैं। विभाजन परिशोधन के कुछ अनुप्रयोगों में, जैसे कि लेक्सिकोग्राफ़िक चौड़ाई-प्रथम खोजविसंधित-सेट डेटा संरचना विभाजन में सेट पर ऑर्डरिंग भी बनाए रखती है।

विभाजन परिशोधन ग्राफ़ सिद्धांत और परिमित ऑटोमेटन पर कई कुशल एल्गोरिदम का एक प्रमुख घटक है, जिसमें डीएफए न्यूनीकरण , समानांतर शेड्यूलिंग के लिए कॉफ़मैन-ग्राहम कलन विधि और ग्राफ़ की लेक्सिकोग्राफ़िक चौड़ाई-पहली खोज शामिल है।[1][2][3]


डेटा संरचना

एक विभाजन शोधन एल्गोरिथम असंयुक्त सेट के एक परिवार को बनाए रखता है Si. एल्गोरिदम की शुरुआत में, इस परिवार में डेटा संरचना में सभी तत्वों का एक सेट होता है। एल्गोरिदम के प्रत्येक चरण में, एक सेट X एल्गोरिथ्म और प्रत्येक सेट के लिए प्रस्तुत किया गया है Si जिस परिवार में सदस्य हैं X दो सेटों में विभाजित है, इंटरसेक्शन (सेट थ्योरी) Si ∩ X और पूरक (सेट सिद्धांत) Si \ X.

निम्नलिखित सूचनाओं का प्रतिनिधित्व करने वाली डेटा संरचनाओं को बनाए रखते हुए इस तरह के एक एल्गोरिथ्म को कुशलता से लागू किया जा सकता है:[4][5]

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

परिशोधन ऑपरेशन करने के लिए, एल्गोरिथम दिए गए सेट के तत्वों के माध्यम से लूप करता है X. ऐसे प्रत्येक तत्व के लिए x, यह सेट पाता है Si उसमें सम्मिलित है x, और जाँचता है कि क्या दूसरा सेट for Si ∩ X प्रारंभ किया जा चुका है। यदि नहीं, तो यह दूसरा सेट बनाता है और जोड़ता है Si एक सूची के लिए L उन सेटों का जो ऑपरेशन द्वारा विभाजित होते हैं। फिर, चाहे कोई नया सेट बना हो या नहीं, एल्गोरिथम हटा देता है x से Si और इसे जोड़ता है Si ∩ X. प्रतिनिधित्व में जिसमें सभी तत्वों को एक ही सरणी में संग्रहीत किया जाता है, चल रहा है x एक सेट से दूसरे सेट में अदला-बदली करके किया जा सकता है x के अंतिम तत्व के साथ Si और उसके बाद के अंत सूचकांक को घटाना Si और नए सेट का प्रारंभ सूचकांक। अंत में, के सभी तत्वों के बाद X इस तरह से संसाधित किया गया है, एल्गोरिदम लूप करता है L, प्रत्येक वर्तमान सेट को अलग करना Si दूसरे सेट से जो इससे अलग हो गया है, और इन दोनों सेटों को रिफाइनमेंट ऑपरेशन द्वारा नवगठित होने की रिपोर्ट करता है।

इस तरह से एकल शोधन कार्य करने का समय है O(|X|), सेट के परिवार में तत्वों की संख्या से स्वतंत्र और डेटा संरचना में सेट की कुल संख्या से भी स्वतंत्र। इस प्रकार, परिशोधन के अनुक्रम का समय प्रत्येक शोधन चरण में एल्गोरिथम को दिए गए सेट के कुल आकार के समानुपाती होता है।

अनुप्रयोग

विभाजन परिशोधन का एक प्रारंभिक अनुप्रयोग एक एल्गोरिथम द्वारा किया गया था Hopcroft (1971) डीएफए न्यूनीकरण के लिए। इस समस्या में, एक नियतात्मक परिमित automaton इनपुट के रूप में दिया जाता है, और यथासंभव कुछ राज्यों के साथ समकक्ष automaton खोजना चाहिए। होपक्रॉफ्ट का एल्गोरिदम इनपुट ऑटोमेटन के राज्यों के सबसेट में विभाजन को बनाए रखता है, संपत्ति के साथ कि अलग-अलग सबसेट में किन्हीं भी दो राज्यों को आउटपुट ऑटोमेटन के विभिन्न राज्यों में मैप किया जाना चाहिए। प्रारंभ में, दो उपसमुच्चय होते हैं, एक में ऑटोमेटन के सभी स्वीकार करने वाले राज्य होते हैं और शेष राज्यों में से एक होता है। प्रत्येक चरण में उपसमुच्चय में से एक Si और इनपुट प्रतीकों में से एक x ऑटोमेटन का चयन किया जाता है, और राज्यों के सबसेट को उन राज्यों में परिष्कृत किया जाता है जिनके लिए एक संक्रमण लेबल किया जाता है x की ओर ले जाएगा Si, और जिन राज्यों के लिए a x-संक्रमण कहीं और ले जाएगा। जब एक सेट Si जो पहले से ही चुना जा चुका है, एक शोधन द्वारा विभाजित किया गया है, दो परिणामी सेटों में से केवल एक (दो में से छोटा) को फिर से चुने जाने की आवश्यकता है; इस प्रकार, प्रत्येक राज्य सेट में भाग लेता है X के लिए O(s log n) शोधन चरण और समग्र एल्गोरिथ्म में समय लगता है O(ns log n), कहां n प्रारंभिक राज्यों की संख्या है और s वर्णमाला का आकार है।[6] विभाजन परिशोधन द्वारा लागू किया गया था Sethi (1976) समानांतर शेड्यूलिंग के लिए कॉफ़मैन-ग्राहम एल्गोरिथम के कुशल कार्यान्वयन में। सेठी ने दिखाया कि इसका उपयोग रैखिक समय में दिए गए निर्देशित अचक्रीय ग्राफ के लेक्सिकोग्राफिक ऑर्डर टोपोलॉजिकल सॉर्ट के निर्माण के लिए किया जा सकता है; यह लेक्सिकोग्राफिक टोपोलॉजिकल ऑर्डरिंग कॉफ़मैन-ग्राहम एल्गोरिथम के प्रमुख चरणों में से एक है। इस एप्लिकेशन में, असम्बद्ध सेट के तत्व इनपुट ग्राफ और सेट के शिखर हैं X विभाजन को परिशोधित करने के लिए उपयोग किए जाने वाले वर्टिकल के पड़ोसियों के सेट हैं। चूँकि सभी शीर्षों के पड़ोसियों की कुल संख्या ग्राफ़ में केवल किनारों की संख्या है, एल्गोरिथ्म किनारों की संख्या, इसके इनपुट आकार में रैखिक समय लेता है।[7] विभाजन परिशोधन भी लेक्सिकोग्राफ़िक चौड़ाई-प्रथम खोज में एक महत्वपूर्ण कदम बनाता है, कॉर्डल ग्राफ ़ की मान्यता में अनुप्रयोगों के साथ एक ग्राफ़ खोज एल्गोरिदम और ग्राफ़ के कई अन्य महत्वपूर्ण वर्ग। फिर से, असम्बद्ध सेट तत्व वर्टिकल और सेट हैं X पड़ोस (ग्राफ सिद्धांत) का प्रतिनिधित्व करते हैं, इसलिए एल्गोरिदम रैखिक समय लेता है।[8][9]


यह भी देखें

संदर्भ

  1. ↑ Paige, Robert; Tarjan, Robert E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, MR 0917035.
  2. ↑ Habib, Michel; Paul, Christophe; Viennot, Laurent (1999), "Partition refinement techniques: an interesting algorithmic tool kit", International Journal of Foundations of Computer Science, 10 (2): 147–170, doi:10.1142/S0129054199000125, MR 1759929.
  3. ↑ Habib, Michel; Paul, Christophe; Viennot, Laurent (1998), "A synthesis on partition refinement: a useful routine for strings, graphs, Boolean matrices and automata", in Morvan, Michel; Meinel, Christoph; Krob, Daniel (eds.), STACS 98: 15th Annual Symposium on Theoretical Aspects of Computer Science Paris, France, February 25–27, 1998, Proceedings (PDF), Lecture Notes in Computer Science, vol. 1373, Springer-Verlag, pp. 25–38, doi:10.1007/BFb0028546, ISBN 978-3-540-64230-5, MR 1650757.
  4. ↑ Valmari, Antti; Lehtinen, Petri (2008), "Efficient minimization of DFAs with partial transition functions", in Albers, Susanne; Weil, Pascal (eds.), 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Leibniz International Proceedings in Informatics (LIPIcs), vol. 1, Dagstuhl, Germany: Schloss Dagstuhl: Leibniz-Zentrum fuer Informatik, pp. 645–656, arXiv:0802.2826, doi:10.4230/LIPIcs.STACS.2008.1328, ISBN 978-3-939897-06-4, MR 2873773
  5. ↑ Knuutila, Timo (2001), "Re-describing an algorithm by Hopcroft", Theoretical Computer Science, 250 (1–2): 333–363, doi:10.1016/S0304-3975(99)00150-4, ISSN 0304-3975
  6. ↑ Hopcroft, John (1971), "An n log n algorithm for minimizing states in a finite automaton", Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York: Academic Press, pp. 189–196, MR 0403320.
  7. ↑ Sethi, Ravi (1976), "Scheduling graphs on two processors", SIAM Journal on Computing, 5 (1): 73–82, doi:10.1137/0205005, MR 0398156.
  8. ↑ Rose, D. J.; Tarjan, R. E.; Lueker, G. S. (1976), "Algorithmic aspects of vertex elimination on graphs", SIAM Journal on Computing, 5 (2): 266–283, doi:10.1137/0205021.
  9. ↑ Corneil, Derek G. (2004), "Lexicographic breadth first search – a survey", in Hromkovič, Juraj; Nagl, Manfred; Westfechtel, Bernhard (eds.), Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer-Verlag, pp. 1–19, doi:10.1007/978-3-540-30559-0_1.
Retrieved from "https://alpha.indicwiki.in/index.php?title=विभाजन_शोधन&oldid=86436"