Task-6
Implement OBST using dynamic programming
Algorithm:
Algorithm OBST(p, q, n)
// Given n distinct identifiers a1 < a2 < ··· < an and probabilities
// p[i], 1 ≤ i ≤ n, and q[i], 0 ≤ i ≤ n, this algorithm computes
// the cost c[i, j] of optimal binary search tree for identifiers
// a_i, ..., a_j. It also computes r[i, j], the root of t[i, j].
// w[i, j] is the weight of t[i, j].
{
for i := 0 to n do
{
// Initialize.
w[i, i] := q[i]; r[i, i] := 0; c[i, i] := 0.0;
// Optimal trees with one node
w[i, i + 1] := q[i] + q[i + 1] + p[i + 1];
c[i, i + 1] := w[i, i + 1]; r[i, i + 1] := i + 1;
}
for m := 2 to n do // Find optimal trees with m nodes.
for i := 0 to n - m do
{
j := i + m;
w[i, j] := w[i, j - 1] + p[j] + q[j];
c[i, j] := ∞; // Solve 5.12 using Knuth's result.
k := Find(c, r, i, j);
// A value of k in the range [r[i, j - 1], r[i + 1, j]] that minimizes c[i, k - 1] + c[k, j];
c[i, j] := w[i, j] + c[i, k - 1] + c[k, j];
r[i, j] := k;
}
write (c[0, n], w[0, n], r[0, n]);
}
Algorithm Find(c, r, i, j)
{
min := ∞;
for m := r[i, j - 1] to r[i + 1, j] do
if (c[i, m - 1] + c[m, j] < min) then
{
min := c[i, m - 1] + c[m, j];
l_i := m;
}
return l_i;
}
Program:
#include <stdio.h>
#define MAX 10
#define INF 300000
void main() {
char ele[MAX][MAX];
int w[MAX][MAX], c[MAX][MAX], r[MAX][MAX];
int p[MAX], q[MAX];
int temp, min, min1;
int i, j, k, b, n;
// Input number of elements
printf("Enter the number of elements: ");
scanf("%d", &n);
// Input probabilities for elements p[i]
for (i = 1; i <= n; i++) {
printf("Enter the element P(%d): ", i);
scanf("%d", &p[i]);
}
printf("\n");
// Input probabilities for dummy keys q[i]
for (i = 0; i <= n; i++) {
printf("Enter the element q(%d): ", i);
scanf("%d", &q[i]);
}
printf("\n");
printf("W \t\t C \t\t R\n");
// Initialization of w, c, and r matrices for single elements
for (i = 0; i <= n; i++) {
for (j = 0; j <= n; j++) {
if (i == j) {
w[i][i] = q[i];
c[i][i] = 0;
r[i][i] = 0;
printf("w[%d][%d] : %d \t c[%d][%d]: %d \t r[%d][%d] : %d\n", i, j, w[i][j], i, j, c[i][j], i, j, r[i][j]);
}
}
}
printf("\n");
// Fill w, c, and r matrices for ranges [i, j]
for (b = 0; b < n; b++) {
for (i = 0, j = b + 1; j <= n; i++, j++) {
if (i != j && i < j) {
// Calculate w[i][j]
w[i][j] = w[i][j - 1] + p[j] + q[j];
min = INF;
// Find minimum cost and root for this subproblem
for (k = i + 1; k <= j; k++) {
min1 = c[i][k - 1] + c[k][j] + w[i][j];
if (min > min1) {
min = min1;
temp = k;
}
}
// Store minimum cost and root for this range
c[i][j] = min;
r[i][j] = temp;
}
// Print w[i][j], c[i][j], and r[i][j]
printf("w[%d][%d] : %d \t c[%d][%d]: %d \t r[%d][%d] : %d\n", i, j, w[i][j], i, j, c[i][j], i, j, r[i][j]);
}
printf("\n");
}
// Print minimum cost for the entire tree
printf("Minimum cost: %d\n", c[0][n]);
}
Output:
/tmp/VsdNZE6fYV.o
Enter the number of elements: 4
Enter the element P(1): 3
Enter the element P(2): 3
Enter the element P(3): 1
Enter the element P(4): 1
Enter the element q(0): 2
Enter the element q(1): 3
Enter the element q(2): 1
Enter the element q(3): 1
Enter the element q(4): 1
W C R
w[0][0] : 2 c[0][0]: 0 r[0][0] : 0
w[1][1] : 3 c[1][1]: 0 r[1][1] : 0
w[2][2] : 1 c[2][2]: 0 r[2][2] : 0
w[3][3] : 1 c[3][3]: 0 r[3][3] : 0
w[4][4] : 1 c[4][4]: 0 r[4][4] : 0
w[0][1] : 8 c[0][1]: 8 r[0][1] : 1
w[1][2] : 7 c[1][2]: 7 r[1][2] : 2
w[2][3] : 3 c[2][3]: 3 r[2][3] : 3
w[3][4] : 3 c[3][4]: 3 r[3][4] : 4
w[0][2] : 12 c[0][2]: 19 r[0][2] : 1
w[1][3] : 9 c[1][3]: 12 r[1][3] : 2
w[2][4] : 5 c[2][4]: 8 r[2][4] : 3
w[0][3] : 14 c[0][3]: 25 r[0][3] : 2
w[1][4] : 11 c[1][4]: 19 r[1][4] : 2
w[0][4] : 16 c[0][4]: 32 r[0][4] : 2
Minimum cost: 32
=== Code Exited With Errors ===