DAA - इष्टतम मर्ज पैटर्न

किसी एकल सॉर्ट की गई फ़ाइल में विभिन्न लंबाई की सॉर्ट की गई फ़ाइलों का एक सेट मर्ज करें। हमें एक इष्टतम समाधान खोजने की आवश्यकता है, जहां परिणामी फ़ाइल न्यूनतम समय में उत्पन्न हो जाएगी।

यदि सॉर्ट की गई फ़ाइलों की संख्या दी गई है, तो उन्हें एक ही सॉर्ट की गई फ़ाइल में मर्ज करने के कई तरीके हैं। यह मर्ज जोड़ी वार किया जा सकता है। इसलिए, इस प्रकार के विलय को कहा जाता है2-way merge patterns।

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

विलय करने के लिए a p-record file और एक q-record file संभवतः की आवश्यकता है p + q रिकॉर्ड चाल, स्पष्ट पसंद, प्रत्येक चरण में दो छोटी फ़ाइलों को एक साथ मर्ज करें।

द्वि-मर्ज पैटर्न को बाइनरी मर्ज ट्री द्वारा दर्शाया जा सकता है। आइए हम एक सेट पर विचार करेंn छँटाई हुई फाइलें {f₁, f₂, f₃, …, f_n}। प्रारंभ में, इसके प्रत्येक तत्व को एकल नोड बाइनरी ट्री माना जाता है। इस इष्टतम समाधान को खोजने के लिए, निम्नलिखित एल्गोरिथ्म का उपयोग किया जाता है।

Algorithm: TREE (n)  
for i := 1 to n – 1 do  
   declare new node  
   node.leftchild := least (list) 
   node.rightchild := least (list) 
   node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)  
   insert (list, node);  
return least (list);

इस एल्गोरिथ्म के अंत में, रूट नोड का वजन इष्टतम लागत का प्रतिनिधित्व करता है।