最優合併模式演算法

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

列印頁面