나는 하나의 가장자리를 제거하여 N 개의 노드 (각 노드의 최대 차수가 3 인 곳)가있는 트리를 분할하는 알고리즘을 찾고 있으므로 두 개의 트리가 가능한 한 N/2에 가깝습니다. "가장 중심에있는"가장 자리를 어떻게 찾습니까?균등 분할 나무
트리는 알고리즘의 이전 단계에서 입력으로 제공되며 그래프로 입력되므로 밸런싱되지 않으며 어떤 노드가 루트인지 분명하지 않습니다.
제 아이디어는 트리에서 가장 긴 경로를 찾은 다음 가장 긴 경로의 중간에있는 가장자리를 선택하는 것입니다. 작동합니까?
최적의 방법으로, 어느 트리에도 2N/3 노드 이상이 존재하지 않도록하는 솔루션을 찾고 있습니다.
답장을 보내 주셔서 감사합니다.
의견에서 언급 한 이유로 초기 알고리즘이 작동하지 않는다고 생각합니다. 그러나 수정 된 DFS를 사용하여 O (n) 시간과 공간에서이 문제를 해결할 수 있다고 생각합니다.
전체 노드 수를 계산하려면 그래프를 걷기 시작하십시오. 이것을 n이라고 부르십시오. 자, 임의의 노드를 선택하고 트리를 루트합니다. 우리는 이제 루트에서 시작하는 트리를 재귀 적으로 탐색하고 각 하위 트리에 얼마나 많은 노드가 있는지 각 하위 트리에 대해 계산합니다. 그 아이를 루트로하는 서브 트리에있는 노드의 수를, 각 아동의 경우
을 하위 트리의 경우 이후 그 가장자리 아래의 하위 트리 그 안에 k 개의 노드가있을 때, 유출은 (k, n - k)가됩니다. 따라서 모든 노드에서 반복을 수행하고 가장 균등하게 (k, n-k) 균형을 유지하는 것을 찾는 것이 가장 좋습니다.
노드 계산에는 O (n) 시간이 걸리고 재귀 실행은 각 노드와 에지를 최대 O (1) 회 방문하므로 O (n) 시간도 걸립니다. 최적 절단을 찾는 것은 O (n)의 순 런타임에 대해 추가 O (n) 시간이 걸립니다. 서브 트리 노드 수를 저장해야하기 때문에 O (n) 메모리도 필요합니다.
희망이 도움이됩니다.
이 작업을 수행하는 알고리즘을 찾을 수 없습니다. –
@ SaeedAmiri- 죄송합니다,이 부분에 대해 자세히 설명해 주시겠습니까? – templatetypedef
크기 3의 최대 정도를 보지 못했습니다. 맞습니다. –
내 대답은 Divide-And-Conquer Algorithm for Trees입니다. 트리를 2 개의 거의 동일한 크기의 트리 (하단 알고리즘)로 파티션하는 노드를 찾을 수 있습니다. 이제이 노드의 가장자리 중 하나를 선택하기 만하면됩니다. 네가 원하는 걸해라.
현재 접근법이 작동하지 않습니다. 완전한 이진 트리가 있다고 가정하고 길이가 3*log n 인 리프 (이름은 bad) 중 하나에 길이를 추가하십시오. 가장 긴 경로는 다른 리프 중 하나의 끝에 있습니다. 경로가이 bad 잎에 연결되어 있고 중간 가장자리가이 경로 내에 있습니다 (실제로 나쁜 잎을 통과 한 후).이 가장자리에서 기초를 파티션하면 O(log n) 부분과 다른 부분은 O(n)입니다.
나무의 레이아웃 균형에 관한 데이터가 없다면 퇴화 된 나무 (예 : 왼쪽 팔에 100 개, 오른쪽 팔에 50 개)로 시작하여 나중에 50/100으로 나뉘어 다시 시작할 수 있습니다 같은 배. –
예, 길이가 150 인 가장 긴 경로를 취하고 경로의 중간 가장자리 (경로의 75 번째 또는 76 번째)를 취하면 길이가 같은 부분으로 분할됩니다. 문제는 그러한 최적의 가장자리가 항상 존재하는지 (나는 그렇게 생각하지 않는다)이다. – anonymous
퇴화 된 나무는 기본적으로 연결된 목록입니다. 예 : 두 개의 자식이있는 유일한 노드는 루트 노드입니다. 따라서 루트에서 트리를 통과하는 경로가 두 개 있습니다. 100 개의 선형 노드로 왼쪽 아래로, 50으로 오른쪽 아래로 이동합니다. 가장 긴 경로 (100 노드 분기)를 분할하면 100을 50/50으로 분할하고 오른쪽 분기에서 나머지를 더하기 때문에 트리를 100/50 내지 50/100이다. –