Data Structures Algorithms 简明教程
Optimal Merge Pattern Algorithm
将一组不同长度的已排序文件合并为一个已排序文件。我们需找到一个最优解决方案，以便在最短时间内生成结果文件。
Merge a set of sorted files of different length into a single sorted file. We need to find an optimal solution, where the resultant file will be generated in minimum time.
如果给出了已排序文件的数量，则有许多方法可以将它们合并为一个已排序文件。此合并可以逐对进行。因此，这种类型的合并称为 2-way merge patterns 。
If the number of sorted files are given, there are many ways to merge them into a single sorted file. This merge can be performed pair wise. Hence, this type of merging is called as 2-way merge patterns.
由于不同的配对需要不同的时间，在此策略中，我们要确定一种将许多文件合并在一起的最优方法。在每一步中，都会合并两个最短序列。
As, different pairings require different amounts of time, in this strategy we want to determine an optimal way of merging many files together. At each step, two shortest sequences are merged.
合并一个 p-record file 和一个 q-record file 可能需要 p + q 条记录移动，显而易见的做法是，在每一步将两个最小的文件合并在一起。
To merge a p-record file and a q-record file requires possibly p + q record moves, the obvious choice being, merge the two smallest files together at each step.
双向合并模式可以用二进制合并树表示。我们来考虑一组 n 个已排序文件 {f1, f2, f3, …, fn} 。最初，此组的每个元素都被视为一颗单节点二叉树。要找到此最优解决方案，请使用以下算法。
Two-way merge patterns can be represented by binary merge trees. Let us consider a set of n sorted files {f1, f2, f3, …, fn}. Initially, each element of this is considered as a single node binary tree. To find this optimal solution, the following algorithm is used.
Pseudocode
以下是最优合并模式算法的伪代码 -
Following is the pseudocode of the Optimal Merge Pattern Algorithm −
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);在此算法结束时，根节点的权重表示最优成本。
At the end of this algorithm, the weight of the root node represents the optimal cost.
Examples
我们来考虑给定的文件 f1、f2、f3、f4 和 f5，它们各自有 20、30、10、5 和 30 个元素。
Let us consider the given files, f1, f2, f3, f4 and f5 with 20, 30, 10, 5 and 30 number of elements respectively.
如果合并操作按照提供的序列执行，则
If merge operations are performed according to the provided sequence, then
M1 = merge f1 and f2 ⇒ 20 + 30 = 50
M1 = merge f1 and f2 ⇒ 20 + 30 = 50
M2 = merge M1 and f3 ⇒ 50 + 10 = 60
M2 = merge M1 and f3 ⇒ 50 + 10 = 60
M3 = merge M2 and f4 ⇒ 60 + 5 = 65
M3 = merge M2 and f4 ⇒ 60 + 5 = 65
M4 = merge M3 and f5 ⇒ 65 + 30 = 95
M4 = merge M3 and f5 ⇒ 65 + 30 = 95
因此，操作总数为
Hence, the total number of operations is
50 + 60 + 65 + 95 = 270
现在，问题来了，有没有更好的解决方案？
Now, the question arises is there any better solution?
按升序对数字进行排序，我们可以得到以下序列 −
Sorting the numbers according to their size in an ascending order, we get the following sequence −
f4, f3, f1, f2, f5
f4, f3, f1, f2, f5
因此，可以对这个序列进行合并操作
Hence, merge operations can be performed on this sequence
M1 = merge f4 and f3 ⇒ 5 + 10 = 15
M1 = merge f4 and f3 ⇒ 5 + 10 = 15
M2 = merge M1 and f1 ⇒ 15 + 20 = 35
M2 = merge M1 and f1 ⇒ 15 + 20 = 35
M3 = merge M2 and f2 ⇒ 35 + 30 = 65
M3 = merge M2 and f2 ⇒ 35 + 30 = 65
M4 = merge M3 and f5 ⇒ 65 + 30 = 95
M4 = merge M3 and f5 ⇒ 65 + 30 = 95
因此，操作总数为
Therefore, the total number of operations is
15 + 35 + 65 + 95 = 210
显然，这比前一个更好。
Obviously, this is better than the previous one.
在此背景下，我们现在将使用此算法来解决问题。
In this context, we are now going to solve the problem using this algorithm.
