Оптимальная стоимость бинарного дерева поиска - PullRequest
Новая
       1

Оптимальная стоимость бинарного дерева поиска

0 голосов
/ 31 марта 2020

Мне нужно сгенерировать оптимальное бинарное дерево поиска, найти его стоимость и root. Когда я сравниваю это с примером, предоставленным для назначения; моя программа печатает правильное дерево, получая правильное значение "w", "root", но стоимость не подходит. Я сделал огромные изменения и разработал их настолько, насколько мог, но я не могу понять, почему стоимость не получается правильной. Код приведен ниже. Это также мой первый подход к динамическому c программированию. Пример ввода:

нет. элементов: 5 элементов: 1 2 3 4 5 пи: 0,15 0,10 0,05 0,00 0,20 ци: 0,05 0,0,10 0,05 0,05 0,05 0,05

Root: 2, стоимость: 2,75, Вт: 1,00 Мой ответ: Root -> 2, стоимость-> 2,35, W-> 1.000

КОД, генерирующий W, COST, ROOT: 

import java.io.*;
import java.util.*;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

class MALIKP44
{
public double p[]; // Probabilities with which we search for an element
public double q[]; // Probabilities that an element is not found
public String a[]; // Elements from which OBST is to be built
public double w[][]; // Weight w[i][j] of a tree having root r[i][j]
public double c[][]; // Cost c[i][j] of a tree having root r[i][j]
public int r[][]; // Represents Root
public int n; // Number of nodes
int front,rear,queue[]; //THIS IS QUEUE STRUCTURE
public MALIKP44(int SIZE)
{
p=new double[SIZE];
q= new double[SIZE];
a=new String[SIZE];
w=new double[SIZE][SIZE];
c=new double[SIZE][SIZE];
r=new int[SIZE][SIZE];
queue=new int[SIZE];
front=rear=-1;
}
public int Min_Value(int i, int j) //FINDING MIN VALUE
{
int k=0;
int m=0;
double minimum = 34000;
for (m=r[i][j-1] ; m<=r[i+1][j] ; m++)
{
if ((c[i][(m-1)]+c[m][j]) < minimum)
{
minimum = c[i][(m-1)] + c[m][j];
k = m;
}
}
System.out.println("K:" + k);
return k;
}
public void OBST() //OPTIMAL BINARY SEARCH TREE
{

int i, j, l, m;
int k=0;
for (i=0 ; i<n; i++) {

// Initialize
w[i][i] = q[i];
r[i][i] = 0;
c[i][i] = 0;

// Optimal trees with one node
w[i][i+1] = q[i] + q[i+1] + p[i+1];
r[i][i+1] = i+1;
c[i][i+1] = q[i] + q[i+1] + p[i+1];
}
w[n][n] = q[n];
r[n][n] = 0;
c[n][n] = 0;

// Find optimal trees with m nodes
System.out.println("\nNAME: SHAHBAZ HASSAN KHAN MALIK");
System.out.println("ID: 109614906");
System.out.println();
System.out.println("——————————COST, ROOT, WEIGHT——————————"); 
System.out.println("\nCOST-> C" + "\n" + "WEIGHT-> W" + "\n" + "ROOT-> R");
System.out.println();

//NESTED LOOP, PROCESS 
for (m=2 ; m<=n ; m++)
{
for (i=0 ; i<=n-m ; i++)
{
j = i+m;
w[i][j] = w[i][j-1] + p[j] + q[j];
k = Min_Value(i,j);
c[i][j] = w[i][j] + c[i][(k-1)] + c[k][j];

//OUTPUT PROCESS
System.out.println();
System.out.println();
System.out.print("C" + "[" + i + "," + j + "]" + ": ");
System.out.print(c[i][j] + "  ");
System.out.println();
r[i][j] = k;
System.out.print("R" + "[" + i + "," + j + "]" + ": ");
System.out.print(r[i][j] + "  ");
System.out.println();
System.out.print("W" + "[" + i + "," + j + "]" + ": ");
System.out.print(w[i][j] + "  ");
System.out.println();
}//inner Fo
}

System.out.println("\n\nRoot is " + a[k]);

}
...