가중치가있는 무향 그래프에서 두 노드 사이에 고정 길이 경로를 찾으려면 어떻게해야합니까?

Question

가중치가 부여 된 무 방향성 그래프에서 두 노드 사이에 고정 된 길이의 경로를 찾는 방법에 대한 추가 연구에 대한 알고리즘이나 지침이 필요합니다.

Answer 1

주어진 노드에서 지정된 길이의 주어진 노드까지의 단순 경로 찾기는 NP 완료입니다. Hamiltonian cycle problem은이 클래스의 문제이며 NP 완료입니다. 가장자리가 가중하는 경우

는 다음 subset sum problem이 문제의 특별한 경우이다, 그래서 우리는 여전히 두 경우 모두

NP-완료있어, 당신은 경로 간단하지 않거나, 가지 치기 경로를 열거 할 수 있습니다 경로가 너무 길어 theta(b^len) 예상 시간 b이 분기 인수 (평균 외계)입니다. 반복 에지를 허용하는 경로를 찾기

는

---

O(v^3 * len) 시간 복잡도 or better 총 [길이] 행렬 곱셈에서 수행 될 수있다 (때로는 거리라고 함).

A은 그래프의 인접 행렬을 나타냅니다. 그런 다음 A^len은 각 쌍의 꼭지점 사이의 길이 len의 경로 수를 유지합니다. 승산 (부울 추가 - 진보 된 행렬 곱셈 알고리즘으로 어떻게 작동하는지 확실하지 않음) 중에 1+1 = 1을 사용할 수 있습니다. 그런 다음에는 그러한 경로가 존재하지만 동시에 정수 오버플로를 피할 수 있습니다.

A^1..A^len (O(n^3 len))을 준비하십시오. 그런 다음 각 거리 d에 1..len을 입력하고 v[d-1]의 자식 인 v[d]의 정점을 찾고- 대상에 대한 긴 경로 (O(n len))가 있는지 확인합니다.

이러한 경로가 있는지 알아야 할 경우 A..A^len 만 필요하며 A^len 만 필요합니다. square-and-multiply 알고리즘으로 O(n^3 log(len)) 시간으로 계산하거나 Coppersmith-Winograd matrix multiplication algorithm과 결합하여 O(n^2.37 log(len))까지 계산할 수 있습니다.

---

양자 택일로, 당신은 단지 [node x distance] 상태 공간을 검색 할 수 있으며 O(n*b*len)에서 수행했다.