다른 트리에서 트리의 노드 찾기

Question

내 문제는 : 두 개의 트리 P와 R을 고려하십시오. 가장 깊은 가능한 트리의 레벨 인 노드를 트리 R의 가능한 가장 깊은 레벨의 노드와 일치시켜야합니다. 즉, 트리의 모든 노드는 가장 일반적인 것부터 가장 구체적인 것까지의 계층 적 관계와 같습니다. 나무 R과 나무 P의 가장 구체적인 일치가 발견되어야합니다. 가장 적합한 방법이 필요합니다.

예를 들어 검토 자 패널을 만들 수 있습니다. 각 리뷰어는 일반 관심 분야에서부터 에너지에서 바이오 가스 (Biogas) 플랜트와 같은 특정 관심사에 이르는 관심의 트리를 가지고 있습니다. 이제 리뷰어의 관심사와 일치하는 논문이 있습니다. 논문의 카테고리와 가장 일치하는 리뷰어를 찾을 수 있습니다. 각 논문에는 가장 일반적인 카테고리에서 정확히 특정 카테고리에 이르는 카테고리 트리도 있습니다.

Answer 1

편집 :

1. 당신이 그들의 "유사성"에 대 자신의 깊이에 노드를 일치에 제공하는 방법을 많은 중요성을 결정 깊이 차이에 대한 고정 식입니다. 이 함수를 사용하여 점수 계산 함수 s (x, y) = a * (- | 깊이 (x) - 깊이 (y) |) + (1-a) * (유사도 (x, y))를 만듭니다. (유사도 (x, y)는 x와 y의 모든 함수가 될 수 있습니다. 예를 들어 x와 y가 문자열 인 경우 가장 긴 공통 부분 시퀀스의 길이가 될 수 있습니다)
2. (개념적으로) 각 노드의 정점을 트리 1의 각 노드에 대한 정점, 첫 번째 트리에서 x가 있고 두 번째 트리에서 y가있는 모든 정점 쌍 (x, y)에 대한 모서리. 이 가장자리의 무게를 s (x, y)로 설정하십시오.
3. 이제 bipartite maximum weighted matching problem, 할당 문제가 생겼습니다. 헝가리어 알고리즘을 적용하여 O (n^3) 시간에 최적 솔루션을 찾습니다.

Answer 2

루트는 가장 일반화 된 범주가 있고 그 하위에는 더 구체적인 범주가 있고 그 하위에는 더 구체적인 내용이있는 Trie을 사용하여 해결할 수 있습니다. 루트에서부터 가장 긴 매칭을 찾아야합니다.