DAA - รูปแบบการผสานที่เหมาะสมที่สุด

รวมชุดไฟล์ที่จัดเรียงที่มีความยาวต่างกันเป็นไฟล์เดียว เราต้องหาวิธีแก้ปัญหาที่ดีที่สุดโดยไฟล์ผลลัพธ์จะถูกสร้างขึ้นในเวลาขั้นต่ำ

หากระบุจำนวนไฟล์ที่จัดเรียงไว้มีหลายวิธีในการรวมเข้าเป็นไฟล์เดียวที่จัดเรียง การผสานนี้สามารถทำได้อย่างชาญฉลาด ดังนั้นการรวมประเภทนี้จึงเรียกว่า2-way merge patterns.

เนื่องจากการจับคู่ที่แตกต่างกันต้องใช้ระยะเวลาที่แตกต่างกันในกลยุทธ์นี้เราต้องการกำหนดวิธีที่ดีที่สุดในการรวมไฟล์จำนวนมากเข้าด้วยกัน ในแต่ละขั้นตอนจะมีการรวมลำดับที่สั้นที่สุดสองลำดับเข้าด้วยกัน

เพื่อรวมไฟล์ 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);

ในตอนท้ายของอัลกอริทึมนี้น้ำหนักของโหนดรูทจะแสดงต้นทุนที่เหมาะสมที่สุด