알고리즘 서론 제1 5 장 - 최 적 화 된 이 진 트 리 찾기

가장 좋 은 두 갈래 로 나 무 를 찾 아서 나무의 검색 대가 가 가장 적다.트 리 의 모든 노드 는 검색 되 는 확률 값 이 있 습 니 다. 한 노드 를 검색 하 는 데 드 는 비용 은 확률 * (깊이 + 1) 입 니 다. 이 진 트 리 를 어떻게 구성 하여 트 리 의 모든 노드 를 검색 하 는 데 드 는 비용 을 최소 화 하 는 것 이 가장 좋 은 이 진 트 리 문 제 를 찾 는 것 입 니까?이 문 제 는 동적 기획 의 사고방식 으로 실현 할 수 있다.구체 적 으로 해석 하면 알고리즘 서론 을 볼 수 있다.코드 는 다음 과 같 습 니 다:

//       ，        。    。
#include<iostream>
using namespace std;
void Optimal_BST(double *p,double *q,int length,double (*e)[20],int (*root)[20])
{
	int i,j,k,r;
	double t;
	double w[20][20]={0};
	for(i=1;i<=length+1;i++)
	{
		e[i][i-1]=q[i-1];
		w[i][i-1]=q[i-1];
	}
	//i         
	for(i=1;i<=length;i++)
	{
		//    j          k    
		for(j=1;j<=length-i+1;j++)
		{
			k=i+j-1;
			e[j][k]=0x7fffffff;
			w[j][k]=w[j][k-1]+p[k]+q[k];
			//  j k              j k  ，              ， r  j
			// k    
			for(r=j;r<=k;r++)
			{
				t=e[j][r-1]+e[r+1][k]+w[j][k];
				if(e[j][k]>t)
				{
					e[j][k]=t;
					//r     j k    
					root[j][k]=r;
				}
			}
		}
	}

}
void Construct_Optimal_BST(int (*root)[20],int i,int j,bool flag)
{
	if(flag==0)
	{
		cout<<"k"<<root[i][j]<<"   "<<endl;
		flag=1;
	}
	int r=root[i][j];
	//        
	if(r-1<i)
	{
		cout<<"d"<<r-1<<" is the left child of "<<"K"<<r<<endl;
	}
	//         
	else
	{
		cout<<"k"<<root[i][r-1]<<" is the left child of "<<"K"<<r<<endl;
		Construct_Optimal_BST(root,i,r-1,1);
	}
	//        
	if(r>=j)
	{
		cout<<"d"<<j<<" is the right child of "<<"K"<<r<<endl;
	}
	//         
	else
	{
		cout<<"k"<<root[r+1][j]<<" is the right child of "<<"K"<<r<<endl;
		Construct_Optimal_BST(root,r+1,j,1);
	}
}
int main()
{
	double p[6]={0,0.15,0.1,0.05,0.1,0.2};
	double q[6]={0.05,0.1,0.05,0.05,0.05,0.1};
	double e[20][20]={0};
	int root[20][20]={0};
	Optimal_BST(p,q,6,e,root);
	cout<<e[1][5]<<endl;
	Construct_Optimal_BST(root,1,5,0);
	return 0;
}