우리는 n 개의 꼭지점이있는 완전한 그래프를 가지고 있다고 생각하십시오. 각 정점에는 값이 있습니다. 두 꼭지점 i와 j 사이의 엣지의 가중치는 value [i] xor value [j]와 같습니다.
문제는 꼭지점 1에서 꼭지점 n까지 경로의 가장자리가 최대가되는 경로를 찾는 것입니다. 이미 Dijkstra의 알고리즘을 수정했고 O (n^2 lg (n))의 알고리즘을 발견했습니다. 좀 더 효율적인 알고리즘을 찾는 데 도움을 줄 수 있습니까?그래프에서 최소 병목 경로를 찾으십시오.
최소 병목 값은 value[1] XOR value[n]의 최상위 비트 (M)로 결정된 수보다 커야합니다. 두 개의 노드 A 및 B, 노드의 등이 M 높은 비트를 발견하면 1 및 A 평등뿐만 아니라 동일 A 및 B, 최소 병목 경로 사이의 최소한의 가장자리 무게 노드 n 및 B의 M 높은 비트입니다 1-ABn이됩니다 (또는 A = 1 및/또는 B = n이면 더 짧을 수도 있음).
최소 에지 가중치 인 A/B 쌍을 선택하려면 노드 1과 일치하는 상위 비트 (M 이상)를 갖는 모든 노드 값에 대해 이진 트라이를 구성하십시오. 그런 다음 상위 비트가 노드 n과 일치하는 모든 노드 값에 대해이 값에서이 값을 검색하십시오. 정확히 일치하는 것이 발견되지 않으면 가장 깊은 부분 일치를 선택하십시오.
시간 복잡도는 O (n * M)입니다.
O (n * log n)을 의미합니까? 또는 O (n^(log n))? – templatetypedef
@templatetypedef 나는 그가 O (n * n * logn)를 의미한다고 생각한다. –