最优合并模式算法

Table of content

伪代码
示例

将一组不同长度的有序文件合并成一个有序文件。我们需要找到一个最优解，使得生成的结果文件在最短时间内完成。

如果给定了有序文件的数量，那么将它们合并成一个有序文件的方法有很多。这种合并可以成对进行。因此，这种类型的合并称为**二路合并模式**。

由于不同的配对需要不同的时间，因此在这种策略中，我们希望确定一种将多个文件合并在一起的最佳方法。在每一步中，合并两个最短的序列。

合并一个**包含p个记录的文件**和一个**包含q个记录的文件**可能需要**p + q**次记录移动，显而易见的选择是在每一步中合并两个最小的文件。

二路合并模式可以用二叉合并树表示。让我们考虑一组**n**个有序文件**{f₁, f₂, f₃, …, f_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);

在这个算法结束时，根节点的权重表示最优成本。

示例

让我们考虑给定的文件f₁、f₂、f₃、f₄和f₅，它们分别包含20、30、10、5和30个元素。

如果根据提供的顺序执行合并操作，则

M₁ = 合并f₁和f₂ => 20 + 30 = 50

M₂ = 合并M₁和f₃ => 50 + 10 = 60

M₃ = 合并M₂和f₄ => 60 + 5 = 65

M₄ = 合并M₃和f₅ => 65 + 30 = 95

因此，操作总数为

50 + 60 + 65 + 95 = 270

现在，问题出现了，是否有更好的解决方案？

根据大小按升序对数字进行排序，我们得到以下序列：

f₄, f₃, f₁, f₂, f₅

因此，可以在此序列上执行合并操作

M₁ = 合并f₄和f₃ => 5 + 10 = 15

M₂ = 合并M₁和f₁ => 15 + 20 = 35

M₃ = 合并M₂和f₂ => 35 + 30 = 65

M₄ = 合并M₃和f₅ => 65 + 30 = 95

因此，操作总数为

15 + 35 + 65 + 95 = 210

显然，这比前一个更好。

在这种情况下，我们现在将使用此算法来解决问题。

初始集合

步骤1

步骤2

步骤3

步骤4

因此，该解决方案需要15 + 35 + 60 + 95 = 205次比较。

示例

以下是上述方法在各种编程语言中的实现：

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
int optimalMerge(int files[], int n)
{
    // Sort the files in ascending order
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (files[j] > files[j + 1]) {
                int temp = files[j];
                files[j] = files[j + 1];
                files[j + 1] = temp;
            }
        }
    }
    int cost = 0;
    while (n > 1) {
        // Merge the smallest two files
        int mergedFileSize = files[0] + files[1];
        cost += mergedFileSize;
        // Replace the first file with the merged file size
        files[0] = mergedFileSize;
        // Shift the remaining files to the left
        for (int i = 1; i < n - 1; i++) {
            files[i] = files[i + 1];
        }
        n--; // Reduce the number of files
        // Sort the files again
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (files[j] > files[j + 1]) {
                    int temp = files[j];
                    files[j] = files[j + 1];
                    files[j + 1] = temp;
                }
            }
        }
    }
    return cost;
}
int main()
{
    int files[] = {5, 10, 20, 30, 30};
    int n = sizeof(files) / sizeof(files[0]);
    int minCost = optimalMerge(files, n);
    printf("Minimum cost of merging is: %d Comparisons\n", minCost);
    return 0;
}

输出

Minimum cost of merging is: 205 Comparisons

#include <iostream>
#include <algorithm>
int optimalMerge(int files[], int n) {
    // Sort the files in ascending order
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (files[j] > files[j + 1]) {
                std::swap(files[j], files[j + 1]);
            }
        }
    }
    int cost = 0;
    while (n > 1) {
        // Merge the smallest two files
        int mergedFileSize = files[0] + files[1];
        cost += mergedFileSize;
        // Replace the first file with the merged file size
        files[0] = mergedFileSize;
        // Shift the remaining files to the left
        for (int i = 1; i < n - 1; i++) {
            files[i] = files[i + 1];
        }
        n--; // Reduce the number of files
        // Sort the files again
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (files[j] > files[j + 1]) {
                    std::swap(files[j], files[j + 1]);
                }
            }
        }
    }
    return cost;
}
int main() {
    int files[] = {5, 10, 20, 30, 30};
    int n = sizeof(files) / sizeof(files[0]);
    int minCost = optimalMerge(files, n);
    std::cout << "Minimum cost of merging is: " << minCost << " Comparisons\n";
    return 0;
}

输出

Minimum cost of merging is: 205 Comparisons

import java.util.Arrays;
public class Main {
    public static int optimalMerge(int[] files, int n) {
        // Sort the files in ascending order
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (files[j] > files[j + 1]) {
                    // Swap files[j] and files[j + 1]
                    int temp = files[j];
                    files[j] = files[j + 1];
                    files[j + 1] = temp;
                }
            }
        }
        int cost = 0;
        while (n > 1) {
            // Merge the smallest two files
            int mergedFileSize = files[0] + files[1];
            cost += mergedFileSize;
            // Replace the first file with the merged file size
            files[0] = mergedFileSize;
            // Shift the remaining files to the left
            for (int i = 1; i < n - 1; i++) {
                files[i] = files[i + 1];
            }
            n--; // Reduce the number of files
            // Sort the files again
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < n - i - 1; j++) {
                    if (files[j] > files[j + 1]) {
                        // Swap files[j] and files[j + 1]
                        int temp = files[j];
                        files[j] = files[j + 1];
                        files[j + 1] = temp;
                    }
                }
            }
        }
        return cost;
    }
    public static void main(String[] args) {
        int[] files = {5, 10, 20, 30, 30};
        int n = files.length;
        int minCost = optimalMerge(files, n);
        System.out.println("Minimum cost of merging is: " + minCost + " Comparisons");
    }
}

输出

Minimum cost of merging is: 205 Comparison

def optimal_merge(files):
    # Sort the files in ascending order
    files.sort()
    cost = 0
    while len(files) > 1:
        # Merge the smallest two files
        merged_file_size = files[0] + files[1]
        cost += merged_file_size
        # Replace the first file with the merged file size
        files[0] = merged_file_size
        # Remove the second file
        files.pop(1)
        # Sort the files again
        files.sort()
    return cost
files = [5, 10, 20, 30, 30]
min_cost = optimal_merge(files)
print("Minimum cost of merging is:", min_cost, "Comparisons")

输出

Minimum cost of merging is: 205 Comparisons

打印页面