Cây tìm kiếm nhị phân tối ưu (Optimal Binary Search Tree) - Quy hoạch động

Cho tập số nguyên đã sắp xếp và mảng tần suất (freq). Nhiệm vụ tạo cây tìm kiếm nhị phân (BST) với dữ liệu đó để tìm chi phí nhỏ nhất cho tất cả các tìm kiếm.

Tạo mảng phụ cost[n][n] để giải và lưu giải pháp các bài toán con. Ma trận cost giữ dữ liệu để giải bài toán theo phương pháp bottom-up.

Đầu vào và đầu ra

Input – Giá trị khóa (node) và tần suất.

Keys = {10, 12, 20}  Frequency = {34, 8, 50}

Output – Chi phí nhỏ nhất là 142.

Đây là các BST có thể từ giá trị cho trước.

• Trường hợp 1: cost = (34×1) + (8×2) + (50×3) = 200
• Trường hợp 2: cost = (8×1) + (34×2) + (50×2) = 176
• Trường hợp 5: cost = (50×1) + (34×2) + (8×3) = 142 (Tối thiểu)

Thuật toán Quy hoạch động

optCostBst(keys, freq, n)
Input: Khóa chèn vào BST, tần suất mỗi khóa, số khóa.
Output: Chi phí nhỏ nhất tạo optimal BST.
Begin
    define cost matrix n x n
    for i = 0 to n-1: cost[i][i] := freq[i]
    for length = 2 to n:
        for i = 0 to n-length:
            j := i + length - 1
            cost[i][j] := INF
            for r = i to j:
                c := 0
                if r > i: c := cost[i][r-1]
                if r < j: c := c + cost[r+1][j]
                c := c + sum(freq[i..j])
                if c < cost[i][j]: cost[i][j] := c
    return cost[0][n-1]
End

Ví dụ C++

#include <iostream>
using namespace std;

int sum(int freq[], int low, int high) {
    int s = 0;
    for(int k=low; k<=high; k++) s += freq[k];
    return s;
}

int minCostBST(int keys[], int freq[], int n) {
    int cost[n][n];
    for(int i=0; ii)?cost[i][r-1]:0) + ((r

Cost of Optimal BST is: 142