k 최단 경로 라우팅

k shortest path routing

k 최단 경로 라우팅 문제는 주어진 네트워크에서 최단 경로 라우팅 문제의 일반화다.최단 경로뿐 아니라 다음 k-1 최단 경로(최단 경로보다 길 수도 있음)에 대해서도 묻는다.그 문제의 변형은 반복되지 않는 가장 짧은 길이다.

dijkstra 알고리즘이나 Bellman-Ford 알고리즘을 확장하고 둘 이상의 경로를 찾도록 확장함으로써 k 최단 경로를 찾는 것이 가능하다.

역사

1957년 이래로 k 최단 경로 라우팅 문제에 대한 많은 논문이 발표되었다.대부분의 기초 작업은 1960년대와 2001년 사이에 이루어졌다.그 이후로 대부분의 연구는 문제의 적용과 그 변형에 관한 것이었다.2010년에 Michael Günther et al.은 확률적 공정 대수 도구 CASPA로 k-단거리 경로 및 관련 조치에 대한 상징적 계산에 관한 책을 출판했다.[1]

알고리즘.

Dijkstra 알고리즘은 k 최단 경로를 찾기 위해 일반화할 수 있다.

정의:
  • G(V, E): 정점 V 및 방향 에지 E 집합이 있는 가중 지시 그래프,
  • w(u, v): 노드 u에서 노드 v까지의 방향 지정된 에지 비용(비 음수).
최단 경로의 제약 조건을 충족하지 않는 링크가 그래프에서 제거됨
  • s: 소스 노드
  • t: 대상 노드
  • K: 찾을 최단 경로 수
  • Pu: s에서 u로 가는 경로
  • B는 경로를 포함하는 힙 데이터 구조다.
  • P: s에서 t까지의 최단 경로 집합
  • 개수u: 노드 u에 대해 발견된 최단 경로 수

알고리즘:

P =비어 있음,
카운트u = 0, V의 모든 u에 대해
경로 Ps = {s}을(를) B에 비용 0으로 삽입
B가t 비어 있지 않고 < K:
– P를u 비용 C와 함께 B에서 가장 짧은 비용으로 사용
– B = B - {Pu }, 카운트u = 카운트u + 1
– u = t인 경우 P = P U {Pu}
– count K를 세는u 경우
  • u에 인접한 각 꼭지점 v에 대해:
– P를v 경로 P에u 에지(u, v)를 연결함으로써 비용 C + w(u, v)를 형성하는 새로운 경로로 설정
– B에 P 삽입v
P를 반환하다

변형

k 최단 경로 라우팅 문제에는 크게 두 가지 변화가 있다.하나의 변화에서 경로는 동일한 노드를 두 번 이상 방문할 수 있도록 허용되어 루프가 생성된다.또 다른 변화에서는 경로가 단순하고 반복되지 않아야 한다.루프 버전은 엡스타인의 알고리즘을[2] 이용해 해결할 수 있고, 루프리스 변형은 옌의 알고리즘으로 해결할 수 있다.[3][4]

루피 변종

이 변종에서는 경로를 반복할 필요가 없으므로 문제가 단순화된다.[4]해결책은 1975년 B. L. Fox에 의해 제시되었는데, 여기서 가장 짧은 경로는 O(m + kn log n) 점증적 시간 복잡성(빅 O 표기법 사용)으로 결정된다.[5]1998년에 데이비드 엡스타인은 경로의 암묵적 표현을 계산하여 점증상 복잡성을 유지하는 접근법을 보고하였는데, 각각은 O(n)의 추가 시간으로 출력할 수 있다.[2][4]2015년 아쿠바 등은 엡스타인의 알고리즘에 대한 훨씬 빠른 대안으로 인덱싱 방법을 고안했는데, 이 방법에서는 인덱스라고 불리는 데이터 구조를 그래프에서 생성한 다음 임의의 정점 쌍 사이의 상위 k 거리를 빠르게 얻을 수 있다.[6]

루프리스 변종

반복되지 않는 변종에서, 경로는 추가적인 복잡성을 더하는 루프를 포함하는 것이 금지된다.[4]그것은 다른 이용 가능한 최단 경로 알고리즘이 필요로 하는 것보다 적은 2n2 추가와 n2 비교만 필요한 기술인 n-노드 비 음거리 네트워크에서 고정 노드에서 다른 모든 노드로 가는 모든 최단 경로의 길이를 찾기 위해 엔의 알고리즘을[3][4] 사용하여 해결할 수 있다.실행 시간 복잡성은 의사-폴리노말이며 O(kn(m + n log n)이다(여기서 m과 n은 각각 에지와 정점의 수를 나타낸다).[3][4]2007년, 존 헤르슈베르거와 서브하쉬 수리는 대체 경로 알고리즘을 제안하였는데, 이 알고리즘은 O(n)의 시간 향상으로 롤러와 엔의 알고리즘을 보다 효율적으로 구현하는 것이다.[8]

몇 가지 예와 설명

예 #1

다음 예제는 통신 엔드 노드 사이의 k 최단 경로를 찾기 위해 엔의 모델을 이용한다.즉th, K 최단 경로까지 최단 경로, 두 번째 최단 경로 등을 찾아낸다.자세한 내용은 여기에서 확인할 수 있다.이 예에서 제공된 코드는 단방향 및 양방향 링크의 조합을 포함하는 15노드 네트워크의 k 최단 경로 라우팅 문제를 해결하려고 시도한다.

양방향 링크와 유니방향 링크의 조합을 포함하는 15노드 네트워크

예제 #2

또 다른 예는 k 최단 경로 알고리즘을 사용하여 여러 개체를 추적하는 것이다.이 기법은 k 최단 경로 라우팅 알고리즘을 기반으로 다중 객체 추적기를 구현한다.확률론적 거주 지도 세트가 입력으로 사용된다.물체 감지기는 입력을 제공한다.

자세한 내용은 "Computer Vision Laboratory – CVLAB"에서 확인할 수 있다.

예 #3

k 최단 경로 알고리즘의 또 다른 사용은 대중교통 시스템에 대한 승객들의 경험을 향상시키는 환승 네트워크를 설계하는 것이다.이러한 교통망의 예는 이동 시간을 고려함으로써 건설될 수 있다.이동 시간 외에도 경제적, 지리적 한계에 따라 다른 조건을 취할 수 있다.매개변수의 변화에도 불구하고, k 최단 경로 알고리즘은 거의 모든 사용자 요구를 만족시키는 가장 최적의 솔루션을 찾는다.이러한 k 최단 경로 알고리즘의 적용이 보편화되고 있는데, 최근 쉬, 허, 송, 초드리(2012년)는 전송 네트워크 시스템의 k 최단 경로 문제를 연구했다.[9]

적용들

k 최단 경로 라우팅은 다음을 위한 좋은 대안이다.

관련 문제

체르카스키 등은 더 많은 알고리즘과 관련 평가를 제공한다.[10]

참고 항목

메모들

  1. ^ 마이클 귄터 외:" 확률적 공정 대수 도구 CASPA를 통한 k-최단 경로 및 관련 조치의 상징적 계산"인: 고장 방지 시스템(DYADEM-FTS), ACM 프레스(2010) 13–18에 대한 신뢰성 모델의 동적 측면에 관한 워크숍.l 워크샵.
  2. ^ a b Eppstein, David (1998). "Finding the k Shortest Paths" (PDF). SIAM J. Comput. 28 (2): 652–673. doi:10.1137/S0097539795290477.
  3. ^ a b c Yen, J. Y. (1971). "Finding the k-Shortest Loopless Paths in a Network". Management Science. 1 7 (11): 712–716. doi:10.1287/mnsc.17.11.712..
  4. ^ a b c d e f Bouillet, Eric; Ellinas, Georgios; Labourdette, Jean-Francois; Ramamurthy, Ramu (2007). "Path Routing – Part 2: Heuristics". Path Routing in Mesh Optical Networks. John Wiley & Sons. pp. 125–138. ISBN 9780470015650.
  5. ^ Fox, B. L. (1975). "Kth shortest paths and applications to the probabilistic networks". ORSA/TIMS Joint National Meeting. 23: B263. CiNii 국가 기사 ID: 10012857200.
  6. ^ Akuba, Takuya; Hayashi, Takanori; Nori, Nozomi; Iwata, Yoichi; Yoshida, Yuichi (January 2015). "Efficient Top-k Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling". Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. Austin, TX: Association for the Advancement of Artificial Intelligence. pp. 2–8.
  7. ^ Lawler, Eugene L. (1972-03-01). "A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem". Management Science. 18 (7): 401–405. doi:10.1287/mnsc.18.7.401. ISSN 0025-1909.
  8. ^ Hershberger, John; Maxel, Matthew; Suri, Subhash (2007). "Finding the k Shortest Simple Paths: A New Algorithm and its Implementation" (PDF). ACM Transactions on Algorithms. 3 (4). Article 45 (19 pages). doi:10.1145/1290672.1290682.
  9. ^ 쉬, W, He, S, S, Song, R, & Chaudhry, S. (2012)일정 기반 전송 네트워크에서 가장 짧은 경로 찾기컴퓨터 & 운영 연구, 39(8), 1812-1826. doi:10.1016/j.cor.2010.02.005
  10. ^ 체르카스키, 보리스 V; 골드버그, 앤드류 V; 라지크, 토마즈(1996)"가장 짧은 경로 알고리즘: 이론 및 실험 평가"수학 프로그래밍.서장 A 73(2): 129–174.

외부 링크