最佳合并模式算法
将一组不同长度的排序文件合并为一个排序文件。我们需要找到一个最优解，使得最终文件在最短时间内生成。
如果给定排序文件的数量，则有多种方法将它们合并为一个排序文件。此合并可以成对执行。因此，这种合并类型被称为双向合并模式。
由于不同的配对需要不同的时间，在这个策略中，我们想要确定一种将多个文件合并在一起的最佳方法。每一步，都会合并两个最短的序列。
要合并一个p记录文件和一个q记录文件，可能需要移动p + q条记录，显而易见的选择是，在每一步将两个最小的文件合并在一起。
双向合并模式可以用二叉合并树表示。考虑一组n个排序文件{f1, f2, f3, …, fn}。最初，将其中的每个元素视为一个单节点二叉树。为了找到这个最优解，我们使用以下算法。
伪代码
以下是最优合并模式算法的伪代码 −
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);
在该算法结束时，根节点的权重代表最优成本。
示例
考虑给定文件 f1、f2、f3、f4 和 f5，其元素数量分别为 20、30、10、5 和 30。
如果按照提供的顺序执行合并操作，则
M1 = 合并 f1 和 f2 => 20 + 30 = 50
M2 = 合并 M1 和 f3 => 50 + 10 = 60
M3 = 合并 M2 和 f4 => 60 + 5 = 65
M4 = 合并 M3 和 f5 => 65 + 30 = 95
因此，总运算次数为
50 + 60 + 65 + 95 = 270
现在问题来了，有没有更好的解决方案？
将数字按大小升序排列，得到以下序列 −
f4, f3, f1, f2, f5
因此，可以对该序列进行合并运算
M1 = 合并 f4 和 f3 => 5 + 10 = 15
M2 = 合并 M1 和 f1 => 15 + 20 = 35
M3 = 合并 M2 和 f2 => 35 + 30 = 65
M4 = 合并 M3 和 f5 => 65 + 30 = 95
因此，总操作次数为
15 + 35 + 65 + 95 = 210
显然，这个比上一个更好。
在这种情况下，我们现在将使用此算法来解决问题。
初始集合
步骤 1
步骤 2
步骤 3
步骤 4
因此，该解决方案需要 15 + 35 + 60 + 95 = 205 次比较。
示例
以下是上述方法在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
int optimalMerge(int files[], int n)
{
// 按升序对文件进行排序
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) {
// 合并最小的两个文件
int mergedFileSize = files[0] + files[1];
cost += mergedFileSize;
// 用合并后的文件大小替换第一个文件
files[0] = mergedFileSize;
// 将剩余文件移至左侧
for (int i = 1; i < n - 1; i++) {
files[i] = files[i + 1];
}
n--; // 减少文件数量
// 再次对文件进行排序
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("合并的最小成本是： %d Comparisons
", minCost);
return 0;
}
输出
合并的最小成本是： 205 Comparisons
#include <iostream>
#include <algorithm>
int optimalMerge(int files[], int n) {
// 按升序对文件进行排序
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) {
// 合并最小的两个文件
int mergedFileSize = files[0] + files[1];
cost += mergedFileSize;
// 用合并后的文件大小替换第一个文件
files[0] = mergedFileSize;
// 将剩余文件移至左侧
for (int i = 1; i < n - 1; i++) {
files[i] = files[i + 1];
}
n--; // 减少文件数量
// 再次对文件进行排序
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 << "合并的最小成本是： " << minCost << " Comparisons
";
return 0;
}
输出
合并的最小成本是： 205 Comparisons
import java.util.Arrays;
public class Main {
public static int optimalMerge(int[] files, int n) {
// 按升序对文件进行排序
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) {
// 合并最小的两个文件
int mergedFileSize = files[0] + files[1];
cost += mergedFileSize;
// 用合并后的文件大小替换第一个文件
files[0] = mergedFileSize;
// 将剩余文件移至左侧
for (int i = 1; i < n - 1; i++) {
files[i] = files[i + 1];
}
n--; // 减少文件数量
// 再次对文件进行排序
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("合并的最小成本是： " + minCost + " Comparisons");
}
}
输出
合并的最小成本是： 205 Comparison
def optimal_merge(files):
# 按升序对文件进行排序
files.sort()
cost = 0
while len(files) > 1:
# 合并最小的两个文件
merged_file_size = files[0] + files[1]
cost += merged_file_size
# 用合并后的文件大小替换第一个文件
files[0] = merged_file_size
# 删除第二个文件
files.pop(1)
# 再次对文件进行排序
files.sort()
return cost
files = [5, 10, 20, 30, 30]
min_cost = optimal_merge(files)
print("合并的最小成本是：", min_cost, "Comparisons")
输出
合并的最小成本是： 205 Comparisons
