최 적 화 된 두 갈래 검색 트 리 동적 계획
1663 단어 알고리즘
최 적 화 된 이 진 트 리 검색 문 제 는 질 서 있 는 집합 S 와 그 액세스 확률 이나 가중치 (q0, p1, q1, p2, q2, p3, q3) 에 대해 질 서 있 는 집합 S 를 표시 하 는 이 진 트 리 에서 최소 평균 길이 의 이 진 트 리 를 찾 는 것 입 니 다.
해결 방법:
동적 계획 방법 을 사용 하여 아래 에서 위로 최 적 화 된 이 진 트 리 를 점차적으로 구성 합 니 다.
동적 계획 의 두 가지 중요 한 요 소 는:
1. 최 우수 서브 구조.2. 중첩 자 문제.
1) 최 적 화 된 서브 구 조 는 문제 의 최 적 화 된 해석 에 서브 문제 의 최 적 화 된 해석 이 포함 되 어 있 으 면 이 문 제 는 최 적 화 된 서브 구 조 를 가진다.
2) 중첩 자 문 제 는 귀속 해결 방안 에서 대량의 동일 자 문제 가 발생 하면 동일 한 자 문제 가 여러 번 중복 계산 되 어 알고리즘 의 효율 손실 이 매우 크다 는 것 을 말한다.
문제 중 q0, q1, q2, q3 는 외부 노드, 즉 검색 에 성공 하지 못 한 가중치 나 확률, p1, p2, p3 는 내부 노드, 즉 검색 에 성공 한 가중치 나 확률, T [i] [j] 는 i 에서 j 까지 의 하위 트 리, w [i] [j] 로 누적 가중치, c [i] [j] 는 나무의 대가, r [i] [j] 는 나무의 뿌리 를 저장 합 니 다.
< 1 >, 알고리즘 사고방식:
(1) 내부 노드 만 있 는 최 적 화 된 이 진 트 리 를 구성 합 니 다.
c[i-1][j]=w[i-1][i]
r[i-1][i]=i
(2) 、 구조 가 m (m > = 2) 개 내부 노드 를 가 진 최 적 화 된 검색 트 리:
c[i][j]=w[i][j]+min{c[i][k-1]+c[k][j]}，i
r[i][j]=k，i
< 2 >, 알고리즘 코드:
#include
using namespace std;
const int n = 3;
int r[n+1][n+1];//
int c[n+1][n+1];// （ ）
int w[n+1][n+1];//
void OBST(int *p,int *q,int n);
void printOBST(int r[n+1][n+1],int i,int j,int n,int f,char ch);
int main()
{
int p[]={0,5,10,50};//
int q[]={15,10,5,5};//
cout<0)
{
if(f==0)
{
cout<=i && t<=n)
{
printOBST(r,i,t,n,k,'L');//
}
int m=k+1;
if(t<=j)
{
printOBST(r,m-1,j,n,k,'R');//
}
}
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
