dijkstra보다 더 빠른 알고리즘이 있습니까?

StackOverflow https://stackoverflow.com/questions/1701221

  •  19-09-2019
  •  | 
  •  

문제

포지티브 에지 가중치 만있는 지시 된 연결된 그래프가 주어지면 Fibonacci 힙을 사용하는 Dijkstra보다 두 정점 사이의 가장 짧은 경로를 찾기위한 더 빠른 알고리즘이 있습니까?

Wikipedia는 Dijkstra가 O (| e | + | v | * log (| v |)) (fibonacci 힙을 사용)에 있다고 말합니다.

예를 들어 실행 시간의 절반이 아니라 다른 시간 복잡성 (O (n * log n)에서 O (n)으로 이동하는 등의 알고리즘이 오히려 최적화를 찾고 있습니다.

또한 다음 접근 방식에 대한 귀하의 의견을 알고 싶습니다.

  1. 모든 에지 가중치의 GCD를 결정하십시오.
  2. 균일 한 가장자리 가중치가있는 그래프로 그래프를 변환하십시오.
  3. BFS를 사용하여 주어진 두 개의 정점 사이의 가장 짧은 경로를 찾으십시오.

포인트 2에 대한 예 :
GCD가 1이라고 상상해보십시오. 그러면 나는 가장자리를 변형시킬 것입니다.
A ---> B (가장자리 3)
~ 안으로
a-> a '-> a' '-> b (3 배 에지 무게 1)
이 변환 비용은 일정한 시간이 걸리며 모든 엣지마다 한 번 수행해야합니다. 따라서이 알고리즘은 o (| e |) (변환) + o (| e | + | v |) (bfs) = o (2 * | e | | + | v |) = o (| e | + | V |)

시간을내어 내 질문을 읽어 주셔서 감사합니다. 시간이 허리에 빠지지 않기를 바랍니다 ^^. 좋은 하루 되세요.

도움이 되었습니까?

해결책

알고리즘에 대해 한 큰 OH 분석은 깊은 결함이 있습니다. 모든 가장자리가 소수라고 가정합니다. 새 그래프의 가장자리 수는 모든 가중치의 합과 같습니다. 따라서 O(|E| + |V|) 의 새로운 그래프는 실제로입니다 O(W x |E| + |V|) 원래 그래프에서 O(|E| + |V| log |V|).

다른 팁

dijkstra보다 더 빠른 알고리즘이 있습니까?

예. 문제는 모든 경우 또는 대부분의 경우 더 나은 성능을 요구할 수 있도록 자격이 없습니다. 단일 케이스에서 더 나은 성능을 가진 알고리즘은 긍정적 인 답변을 설정하기에 충분합니다.

Dijkstra의 방법에 대한 Bellman-Ford 방법에 의해 요구되는 일반적으로 더 많은 수의 반복에도 불구하고, 실제로 Bellman-Ford 방법은 반복 당 더 작은 오버 헤드로 인해 우수 할 수있다 [Golden, B., 1976.“가장 짧은 경로 알고리즘 : A 비교,”Operations Research, Vol. 44, pp. 1164-1168].

위의 인용문은 Dimitri P. Bertsekas (1992 년 3 월)입니다. "가장 짧은 경로에 대한 간단하고 빠른 레이블 교정 알고리즘"(PDF). 네트워크, vol. 23, pp. 703-709, 1993. http://www.mit.edu/people/dimitrib/slf.pdf. 2008-10-01을 검색했습니다.

요컨대, 내 주장은 Bertsekas의 Golden에 대한 해석을 기반으로합니다. 내 결론이 일어는지 여부에 관계없이 Bertsekas가 Dijkstra 알고리즘의 분류에 흥미로운 것을 발견 할 수 있습니다. 레이블 설정 대조되는 방법 레이블 수정 행동 양식.

O (1)가있는 알고리즘이 있습니다. 가중치를 체인 길이로 바꾸고 노드의 키 링을 사용합니다 (주머니에있는 실제 키 링). 키 링을 올바른 체인과 연결하십시오. 두 노드를 선택하고 서로 뽑아냅니다.

한 노드에서 다른 노드로 팽팽한 체인을 따라 가십시오. 이것은 가장 짧은 경로입니다.

이것을 컴퓨터 프로그램으로 구현하려면 두 개의 산업용 로봇이 필요합니다 :)

보다 실제적인 예를 위해서는 사용하십시오 개미 식민지 최적화 짧은 시간에 아주 좋은 결과를 제공합니다. 이 알고리즘에서 실행 수를 지정할 수 있으므로, 소비 된 시간을 결정할 수 있습니다 (예 : 런타임은 O (N)을 제공하지만 완벽한 결과는 보장되지 않습니다.

항상 a*가 있으며 계층 적 a* 및 a* jps와 같은 파생물입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top