ক্রমবদ্ধভাবে সাজানো পূর্ণসংখ্যাগুলোর একটি সেট এবং ফ্রিকোয়েন্সি কাউন্টের জন্য freq অ্যারে দেওয়া আছে। আমাদের কাজ হল সেই ডেটা দিয়ে একটি বাইনারি সার্চ ট্রি তৈরি করা যাতে সকল সার্চের জন্য ন্যূনতম খরচ হয়।
সাবপ্রব্লেমের সমাধান সংরক্ষণ ও সমাধানের জন্য একটি অ্যাক্সিলিয়ারি cost[n][n] অ্যারে তৈরি করা হয়। কস্ট ম্যাট্রিক্স বটম-আপ পদ্ধতিতে সমস্যা সমাধানের ডেটা ধারণ করবে।
ইনপুট এবং আউটপুট
ইনপুট: নোড হিসেবে কি মান এবং ফ্রিকোয়েন্সি।
Keys = {10, 12, 20}
Frequency = {34, 8, 50}
আউটপুট: ন্যূনতম খরচ ১৪২।
সম্ভাব্য BSTগুলো:
কেস ১: (34×1) + (8×2) + (50×3) = ২০০
কেস ২: (8×1) + (34×2) + (50×2) = ১৭৬
কেস ৫: (50×1) + (34×2) + (8×3) = ১৪২ (ন্যূনতম)
অ্যালগরিদম
optCostBst(keys, freq, n)
ইনপুট: BST-এ ইনসার্ট করার কি, প্রতিটি কির ফ্রিকোয়েন্সি, কি সংখ্যা।
আউটপুট: অপ্টিমাল BST তৈরির ন্যূনতম খরচ।
শুরু
n x n আকারের cost ম্যাট্রিক্স সংজ্ঞায়িত করুন
i := 0 থেকে n-1 পর্যন্ত, করুন
cost[i, i] := freq[i]
끝난
length := 2 থেকে n পর্যন্ত, করুন
i := 0 থেকে (n-length+1) পর্যন্ত, করুন
j := i + length - 1
cost[i, j] := ∞
r := i থেকে j পর্যন্ত, করুন
যদি r > i হয়, তবে
c := cost[i, r-1]
অন্যথায়
c := 0
যদি r < j হয়, তবে
c := c + cost[r+1, j]
c := c + i থেকে j পর্যন্ত ফ্রিকোয়েন্সির যোগফল
যদি c < cost[i, j] হয়, তবে
cost[i, j] := c
শেষ
끝난
끝난
cost[0, n-1] ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
using namespace std;
int sum(int freq[], int low, int high) {
int sum = 0;
for (int k = low; k <= high; k++)
sum += freq[k];
return sum;
}
int minCostBST(int keys[], int freq[], int n) {
int cost[n][n];
for (int i = 0; i < n; i++)
cost[i][i] = freq[i];
for (int length=2; length<=n; length++) {
for (int i=0; i<=n-length+1; i++) {
int j = i+length-1;
cost[i][j] = INT_MAX;
for (int r=i; r<=j; r++) {
int c = ((r > i) ? cost[i][r-1] : 0) + ((r < j) ? cost[r+1][j] : 0) + sum(freq, i, j);
if (c < cost[i][j])
cost[i][j] = c;
}
}
}
return cost[0][n-1];
}
int main() {
int keys[] = {10, 12, 20};
int freq[] = {34, 8, 50};
int n = 3;
cout << "Cost of Optimal BST is: " << minCostBST(keys, freq, n);
}
আউটপুট
Cost of Optimal BST is: 142
