효율적으로 두 개념 중 가장 낮은 상위를 찾는 방법은 무엇입니까? 분류 체계에서 두 개념 중 가장 낮은 상위 개념은 두 개념의 가장 공통적 인 조상을 의미합니다. 예를 들어, 다음 분류 체계 그림에서 가장 공통적 인 1 조와 2 조의 조상을 찾는 방법은 무엇입니까?분류학에서 두 개념 중 가장 낮은 상위
BTW, 나는 단어 감지 동음이의 로베르토 나 빌리의 조사에서이 질문을 발견했다. 그는 상급자를 계산하는 방법을 언급하지 않았습니다.
Sense 1 쪽에서 계층 구조를 올라가서 모든 노드를 조상으로 표시 할 수 있습니다 (Sense 1). 그런 다음 Sense 2 페이지로 이동하여 각 조상을 확인하여 조상으로 표시했는지 확인하십시오 (Sense 1). 가장 먼저 발견되는 가장 상위 또는 가장 공통적 인 조상입니다.
사진에서 어떤 느낌인지에 관계없이 루트 노드가됩니다.
http://en.wikipedia.org/wiki/Lowest_common_ancestor에는 트리가있는 (일반적인) 경우 가장 공통적 인 조상 문제에 대한보다 효율적인 알고리즘에 대한 포인터가 들어 있으므로 모든 노드에는 부모가없는 루트 노드를 제외하고 하나의 부모가 있습니다. 이러한 알고리즘은 트리의 선형 시간 전처리 후 일정 시간에 쿼리에 응답 할 수 있습니다.
하나 이상의 부모를 가질 수있는 경우에 이러한 알고리즘 중 어떤 것이 일반화되는지는 알 수 없습니다. 명백한 일반화는 트리에있는 링크를 삭제하여 연결되어있는 동안 모든 노드에 최대 하나의 상위가 있음을 확인하는 것처럼 보입니다.
센스 1에는 부모가 둘 이상있을 수 있습니다. 센스 1에서 루트까지 모든 경로를 표시하고이를 센스 2의 각 경로와 일치시켜야합니까? 다른보다 효율적인 방법이 있습니까? –
@ jerry_sjtu : 분류 체계가 계층 구조가 아닌 경우 가장 잘 정의 된 하위 우선 순위가 필요하지 않습니다. 예를 들어, A와 B가 모두 X의 부모이고 Y의 부모 인 경우 A와 B 중 어느 것이 가장 낮은 상위입니까? –
예, 간단한 방법으로 감각 1에서 루트까지 모든 경로를 표시한다고 설명했습니다. 확실하게 더 효율적인 방법이있을 수 있지만 실제로 응용 프로그램에 따라 다릅니다. 어쨌든 각각의 감각을 계산할 필요가 있다고 가정 할 때, 필요에 따라 모든 감각에 대해 모든 최저 지위를 계산하는 것이 더 빠를 수 있습니다. – Justin