수축 계층

컴퓨터 과학에서 수축 계층의 방법은 그래프에서 최단 경로를 찾기 위한 속도 향상 기법이다.가장 직관적인 애플리케이션은 차량 내비게이션 시스템이며, 사용자는 가능한 가장 빠른 경로를 사용하여$$ $A{\displaystyle }$ ${\displaystyle A}$에서 $B{\displaystyle }$ ${\displaystyle$ B$}(으$)로$$ 운전하고자 한다.여기서 최적화된 측정기준은 이동시간이다.교차로들은 정점으로 표시되고, 교차로들은 가장자리로 연결된다.가장자리 무게는 도로의 이 구간을 따라 주행하는 데 걸리는 시간을 나타낸다.$A{\displaystyle }$ ${\displaystyle A}$에서 B ${\displaystyle B}$까지의 경로는 에지 순서(도로 섹션)이며$$, 최단 경로는 가능한 모든 경로 중에서 에지 가중치의 합이 최소인 경로다.그래프에서 가장 짧은 경로는 Dijkstra의 알고리즘을 사용하여 계산할 수 있지만, 도로망이 수천만 개의 정점으로 구성되어 있다는 점을 고려하면, 이것은 비현실적이다.^[1]수축 계층은 도로망을 나타내는 그래프의 속성을 이용하기 위해 최적화된 속도 향상 방법이다.^[2]속도 향상은 사전 처리 단계에서 바로 가기를 생성하여 달성되며, 이때 최단 경로 쿼리 중에 "중요하지 않은" 정점을 건너뛰기 위해 사용된다.^[2]이는 도로망이 계층성이 높다는 관측에 따른 것이다.예를 들어, 고속도로 분기점 같은 일부 교차로들은 막다른 골목으로 이어지는 분기점보다 "더 중요"하고 계층이 더 높다.단축키는 알고리즘이 쿼리 시 이러한 결합 사이의 전체 경로를 고려할 필요가 없도록 두 개의 중요한 결합 사이의 사전 계산된 거리를 저장하는 데 사용될 수 있다.수축 계층 구조는 인간이 "중요하다"고 여기는 도로(예: 고속도로)는 알 수 없지만, 그래프를 입력으로 제공하고 경험적 접근법을 사용하여 정점에 중요성을 부여할 수 있다.

수축 계층은 차량 항법 시스템의 속도 향상 알고리즘뿐만 아니라 웹 기반 경로 계획자, 교통 시뮬레이션, 물류 최적화에도 적용된다.^[3][1][4]알고리즘의 구현은 오픈 소스 소프트웨어로서 공개적으로 이용할 수 있다.^{[5][6][7][8][9]}

알고리즘.

수축 계층(CH) 알고리즘은 사전 처리 단계와 쿼리 단계로 구성된 최단 경로 문제에 대한 2상 접근법이다.도로망이 다소 간헐적으로 변경됨에 따라 질의 응답 전에 일부 계산을 사전 계산하는 데 더 많은 시간(초에서 시간)을 사용할 수 있다.이 사전 계산된 데이터를 사용하면 각각 매우 적은 시간(마이크로초)이 소요되는 많은 쿼리에 응답할 수 있다.^[1][3]CH는 이러한 속도 증가를 달성하기 위해 바로 가기에 의존한다.바로 가기는 원래 그래프에 인접하지$$ 않은 $두{\displaystyle }$ 꼭지점 $u{\displaystyle }$ ${\displaystyle u}$과 v ${\displaystyle v}$을(를) 연결한다.에지 중량은 가장 짧은 $u{\displaystyle }$ ${\displaystyle u}$- ${\displaystyle }$ ${\displaystyle v}$ 경로에$$ 있는 에지 중량의 합이다.

고속도로로 연결된 두 개의 대도시를 생각해 보라.이 두 도시 사이에는 작은 마을과 교외로 이어지는 수많은 교전이 있다.대부분의 운전자들은 한 도시에서 다른 도시로 - 아마도 더 큰 경로의 일부로 - 이동하면서 출구 중 하나를 타지 않기를 원한다.이 도로 배치를 나타내는 그래프에서, 각 교차로들은 노드로 표시되며 인접 교차로들 사이에 가장자리가 생성된다.이 두 도시 사이의 거리를 계산하기 위해 알고리즘은 그 길이에 더해 모든 가장자리를 가로지르며 이동해야 한다.이 거리를 한 번 미리 계산하여 두 대도시 사이에 생성된 추가적인 가장자리에 저장하면 이 고속도로가 질의에서 평가되어야 할 때마다 계산이 절약될 것이다.이 추가 에지는 "숏컷"이라고 불리며 현실 세계에서는 상대가 없다.수축 계층 알고리즘은 도로 형태에 대한 지식이 없지만 그래프만 입력으로 사용하여 어떤 단축키를 만들어야 하는지 결정할 수 있다.

사전 처리 단계

CH 알고리즘은 검색 공간을 줄이기 위해 사전 처리 단계에서 생성된 바로 가기(쿼리 시간에 CH가 보아야 하는 정점의 수)에 의존한다.이를 위해 반복 정점수축을 수행한다.정점 $v{\displaystyle }$ ${\displaystyle v}$을(를) 수축할 때 그래프 $G{\displaystyle }$ ${\displaystyle$ G$\}$에서 일시적으로 제거되며$$, $u$ ${\textstyle u}$에서 w ${\textstyle w}$까지의 최단 경로에 v ${\displaystyty v}$이(가) 포함되어$$ 있으면 인접$$ 정점의${\displaystyle }$각 쌍 사이에 바로 가 생성된다.. ^[2]$u$ ${\textstyle u}$과 $w$ ${\textstyle w}$ 사이의 최단 경로에 v ${\displaystyle v}$이(가) $포함$되어 있는지 확인하는 프로세스를 증인 검색이라고 한다$$.예를 들어 아직 계약되지 않은 노드만 사용하여 전방 검색을 사용하여$$ $u{\displaystyle }$ ${\displaystyle u}$에서 $w{\displaystyle }$ ${\displaystyle w}$까지의 경로를 계산하여 수행할 수 있다.^[3]

노드 순서

입력 그래프의 정점은 수축에 의해 그래프에 추가된 가장자리 수를 최소화하는 방식으로 수축되어야 한다.최적의 노드 순서가 NP-완전하므로 휴리스틱스가 사용된다.^[10][2]

상향식 및 하향식 휴리스틱스가 존재한다.한편, 계산적으로 저렴하게 상향식 접근법은 정점을 탐욕스럽게 수축시키는 순서를 결정한다. 이는 그 순서를 미리 알 수 없고 오히려 이전의 수축이 완료된 후 다음 노드가 수축으로 선택된다는 것을 의미한다.반면에 하향식 경험은 첫 번째 노드가 수축되기 전에 전체 노드 주문을 사전 계산한다.이것은 더 좋은 결과를 낳지만 더 많은 사전 처리 시간이 필요하다.^[2]

상향식 휴리스틱스에서는 다음 수축 정점을 선택하기 위해 요인의 조합을 사용한다.단축키 수는 사전 처리와 쿼리 런타임을 결정하는 1차 요인인 만큼 최대한 작게 유지하고 싶다.따라서 수축하기 위해 다음 노드를 선택하는 가장 중요한 용어는 노드 $x{\displaystyle }$ ${\displaystyle x}$을(를) 수축할 때 추가된 가장자리의 순 수입니다$.$This is defined as ${\displaystyle A(x)- \{(u,x)\colon (u,x)\in E\} }$ where ${\displaystyle A(x)}$ is the number of shortcuts that would be created if ${\displaystyle x}$ were to be contracted and ${\displaystyle \{(u,x)\colon ($$u,x)\in E\} }$은(는) $x{\displaystyle }$ ${\displaystyle$ x$}$에 발생한 에지 수입니다$.$ 이 기준만 사용할 경우 선형 경로로 인해 선형 계층(여러 수준)이 생성되고 바로 가기가 생성되지 않는다.이미 수축된 근처 정점의 수를 고려함으로써 균일한 수축과 평탄한 계층 구조(낮은 수준)를 달성한다.예를 들어, 이는 인접 정점이 수축될 때마다 증가되는 각 노드에 대해 카운터를 유지함으로써 수행될 수 있다.그런 다음 카운터가 낮은 노드는 카운터가 높은 노드보다 선호된다.^[11]

반면에 하향식 휴리스틱스는 더 나은 결과를 낳지만 더 많은 사전 처리 시간이 필요하다.그들은 많은 최단 경로의 일부인 정점을 몇 개의 최단 경로에만 필요한 정점보다 더 중요한 것으로 분류한다.이것은 내포된 전파를 사용하여 대략적으로 추정할 수 있다.^[2]내포된 해부를 계산하기 위해, 한 개는 반복적으로 그래프를 두 부분으로 분리하고, 그래프는 그 자체로 두 부분으로 분리된다.That is, find a subset of nodes ${\displaystyle S\subseteq V}$ which when removed from the graph ${\displaystyle G}$ separate ${\displaystyle G}$ into two disjunct pieces ${\displaystyle G_{1},G_{2}}$ of approximately equal size such that ${\displaystyle S\cup G_{1}$\cup G_{2}=G}. 모든 노드 v ∈ S{\displaystylev\in S}는 노드를 주문하고 재귀적으로 G1{\displaystyle G_{1}의 중첩 해부를 계산한}, 그리고 G2{\displaystyle G_{2}}은 직관은 그래프의 절반은 그래프의 나머지 절반까지 모든 쿼리 throug을 통과해야 하는 것 ,[12].h가 현장 흙e 작은 분리기와 따라서 이 분리기의 노드는 매우 중요하다.중첩된 전파는 작은 분리기로 인해 도로망에서 효율적으로 계산할 수 있다.^[13]

쿼리 단계

쿼리 단계에서는 시작 노드 s {\$displaystyle s}$ $및$ 대상 노드 $t{\displaystyle }$ ${\displaystyle t}$에서 시작하여$$ 사전 처리 단계에서 생성된 바로 가기에 의해 증강되는 양방향 검색이 수행된다.^[2]$s{\displaystyle }$ ${\displaystyle s}$과 $t{\displaystyle }$ ${\displaystyle t}$ 사이의 최단 경로에서 가장 중요한 정점은 $s{\displaystyle }$ ${\displaystyle$ s$}$ 또는$$ $t{\displaystyle }$ ${\displaystyle t}$ 그 자체이거나$$ s ${\displaystyle$ $s$$}$과 t ${\displaystyt}$보다 더 중요할 것이다$.$Therefore the vertex ${\displaystyle u}$ minimizing ${\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)}$ is on the shortest ${\displaystyle s-t}$ path in the original graph and ${\displaystyle \mathrm {dis$$t}(s,u)+\mathrm {dist}(u,t)=\mathrm {dist}(s,t)}$이(가) 버티고 있다.^[2]이는 바로가기가 만들어지는 방법과 결합하여, 전방 및 후방 검색 모두 검색 공간을 작게 유지하는 계층에서 더 중요한 노드(위쪽)로 이어지는 가장자리만 완화하면 된다는 것을 의미한다.^[3]모든 위쪽(아래쪽) 아래쪽 경로에서 내부(아래쪽)를 건너뛸 수 있는데, 이는 사전 처리 단계에서 바로 가기가 생성되었기 때문이다.

경로 검색

위에서 설명한 CH 쿼리는 실제 $경로$가 아닌 s ${\displaystyle$ s$}$에서 $t$ ${\displaystyle$ t$}$까지의 시간 또는 거리를 산출한다.가장 짧은 경로에 있는 가장자리(도로) 목록을 얻으려면 선택한 바로 가기의 포장을 풀어야 한다.각 단축키는 두 개의 가장자리, 즉 원래 그래프의 두 가장자리 또는 두 개의 바로 가기 또는 한 개의 원래 가장자리 및 바로 가기 중 하나를 연결한 것이다.수축 중에 각 단축키의 중간 꼭지점을 저장하면 최단 경로의 선형 재귀적 언팩이 가능하다.^[2][3]

사용자 정의된 수축 계층

네트워크 위상보다 에지 가중치가 더 자주 변경되는 경우, CH는 사전 처리 단계와 쿼리 단계 사이에 사용자화 단계를 포함함으로써 3상 접근방식으로 확장할 수 있다.예를 들어, 최단거리와 최단시간 사이를 전환하거나 특정 유형의 도로(페리, 고속도로, ...)를 피하는 것과 같은 사용자 선호도뿐만 아니라 현재 교통 정보를 포함할 수 있다.사전 처리 단계에서는 대부분의 런타임이 노드가 계약되는 순서를 계산하는 데 사용된다.^[3]사전 처리 단계에서 이러한 수축 연산의 순서는 나중에 사용자 정의 단계에서 필요할 때 저장될 수 있다.메트릭이 사용자 정의될 때마다 사용자 정의 메트릭을 사용하여 저장된 순서대로 수축을 효율적으로 적용할 수 있다.^[2]또한 새로운 가장자리 무게에 따라 일부 단축키를 다시 계산해야 할 수도 있다.^[3]이를 위해 수축 순서는 미터법 독립 중첩 분포를 사용하여 계산해야 한다.^[1]

확장 및 애플리케이션

위에서 설명한 CH는 하나의 시작 노드에서 하나의 대상 노드까지의 최단 경로를 검색한다.이것을 일대일 최단 경로라고 하며, 예를 들어 자동차 항법 시스템에 사용된다.다른 애플리케이션에는 도로 구간에 GPS 추적을 일치시키고 네트워크의 모든 운전자가 취할 수 있는 경로를 고려해야 하는 트래픽 시뮬레이터의 속도를 향상시키는 것이 포함된다.경로 예측 시, 차량의 현재 및 과거 위치가 출발점에서 가능한 목표까지의 최단 경로와 얼마나 잘 일치하는지 계산하여 차량의 목적지를 추정하려고 한다.이것은 CH를 사용하여 효율적으로 할 수 있다.^[2]

일대다 시나리오에서는 시작 노드 $s{\displaystyle }$ ${\displaystyle s}$과 대상 노드 $T{\displaystyle }$ ${\displaystyle T$${\displaystyle \}}$이(가) 주어지고$$ 모든 t${\displaystyle }t{\displaystyle }$ ${\displaystyle T}$ ${\displaystyle t\\in$ T$}$에 대한 거리$$ d ${\displaystyle \mathrm{i}}$ ${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{t}}$ $(,t)$가 계산되어야 한다$$.일대다 질의에 대한 가장 두드러진 적용 분야는 관심 지점 검색이다.대표적인 예로 지리적 거리 대신 실제 이동 시간을 미터법으로 사용하여 가장 가까운 주유소, 식당 또는 우체국을 찾는 것이 있다.^[2]

In the many-to-many shortest path scenario, a set of starting nodes ${\displaystyle S}$ and a set of target nodes ${\displaystyle T}$ are given and the distance ${\displaystyle \mathrm {dist} (s_{i},t_{i})}$ for all ${\displaystyle (s_{i},t_{j})\in S\times T}$계산해야 한다.이것은 예를 들어 로지스틱 애플리케이션에서 사용된다.^[2]CH는 다음과 같은 방법으로 다대다 쿼리로 확장할 수 있다.먼저 각 $t{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ $∈$ ${\displaystyle T}$ ${\displaystyle t_{j}\in T}$에서 역상향 검색을 수행하십시오$.$ 이 검색 중에 검색된$$ 각 꼭지점 $u{\displaystyle }$ ${\displaystyle u$${\displaystyle \}}$에 $대해{\displaystyle \mathrm{}}$ d ${\displaystyle \mathrm{i}}$ ${\displaystyle \mathrm{s}}$ ${\displaystyle \mathrm{t}(t_{}}$ j ,${\displaystyle {}_{}u}$ ) ${\$$displaystystm {dist}(t_{$$j}$$u})}$을 버킷 $u$에 저장한다.그런 다음 각 s${\displaystyle {}_{}s}$ S ${\displaystyle s_{i}\in S}$에서 전방 위로 검색을 실행하여 비어 있지 않은 각 버킷을 확인하고 해당$$꼭지점 위의 경로가 최적의 거리를 개선하는지 점검하십시오.That is, if ${\displaystyle \mathrm {dist} (s_{i},u)+\mathrm {dist} (u,t_{j})<\mathrm {dist} (s_{i},t_{j})}$ for any ${\displaystyle (s_{i},t_{j})\in S\times T}$.^[2][3]

일부 애플리케이션에서는 일대일 계산이 필요하기도 한다. 즉, 소스 $꼭지점{\displaystyle }$ s ${\displaystyle s}$에서 그래프의 다른 모든 꼭지점까지의 거리를 찾는다.Dijkstra의 알고리즘은 각 가장자리를 정확히 한 번 방문하므로 이론적으로 최적이다.그러나 Dijkstra의 알고리즘은 병렬화가 어렵고 위치성이 좋지 않아 캐시 최적화가 되지 않는다.CH는 캐시 최적 구현을 위해 사용할 수 있다.이를 위해 $s{\displaystyle }$ ${\displaystyle s}$에서 전방 위쪽으로 검색한 후$$ 바로 가기 강조 그래프의 모든 노드에 대해 하향 검색이 수행된다.노드가 중요도 감소 순서로 처리되어 그에 따라 메모리에 저장될 수 있기 때문에 이후 작업은 선형적인 방식으로 메모리를 스캔한다.^[14]2단계에서 노드가 처리되는 순서가 소스 $노드{\displaystyle }$ s ${\displaystyle$ s$}$과(와) 독립적이기 때문에 이러한 작업이 가능하다는 점에 유의하십시오$.$^[2]

생산에서 자동차 네비게이션 시스템은 예측 교통 정보를 사용하여 가장 빠른 이동 경로를 계산하고 대체 경로를 표시할 수 있어야 한다.둘 다 CH를 사용하여 할 수 있다.^[2]전자는 주어진 에지의 이동 시간이 더 이상 일정하지 않고 오히려 에지에 들어갈 때의 시간의 함수인 시간에 의존하는 네트워크를 이용한 라우팅이라고 불린다.대체 루트는 가장 짧은 경로와 현저히 다르지만 크게 길지 않고 매끄럽게 보일 필요가 있다.^[2]

CH는 동시에 여러 지표를 최적화하도록 확장할 수 있다. 이를 다중 기준 경로 계획이라고 한다.예를 들어, 여행 비용과 시간 모두를 최소화할 수 있다.다른 예로는 배터리가 비어 있지 않을 수 있기 때문에 사용 가능한 배터리 충전이 유효한 경로를 제약하는 전기 차량을 들 수 있다.^[2]

이론

수축 계층의 사전 처리 및 쿼리 성능에 대해 많은 한계가 설정되었다.다음에서 $n{\displaystyle }$ ${\displaystyle n}$을(를) 그래프의 꼭지점 수로, $m{\displaystyle }${\$displaystyle m}$ $가장자리$ 수$,$ h {\$displaystyle$$$h} 고속도로 치수, $D{\displaystyle }$ ${\$$displaystyle$$$$d$} 그래프$$ 직경$$, ${\displaystyle t}$ $d{\displaystyle }$${\$$displaystystyle tw}$을 트리 너비로 한다$$.

수축 계층 성능의 첫 번째 분석은 부분적으로 고속도로 치수라고 알려진 수량에 의존한다.이 양의 정의 기술은 모든 r을었다면, 직관적으로 그래프를;0{\displaystyle r>0}그런 길이의 모든 최단 경로 r{r\displaystyle}보다 더 큰 Sr{\dis에서 꼭지점을 포함한다가 vertices Sr{\displaystyle S_{r}의 성긴 집합}은 작은 고속 도로 치수 있다.연주한다$tyle S_{r$ 고속도로 치수의 정확한 값을 계산하는 것은 NP-hard이지만,^[15] 그리드의 경우 고속도로 $치수{\displaystyle }$ h ∈${\displaystyle (}$ ${\displaystyle (n\sqrt{}}$ $){\displaysty$ h$\in \theta({\sqrt{n}})}$인 것으로 알려져 있다$.$^[16]

사용자 정의 가능한 수축 계층 작업 라인에 대체 분석이 제시되었다.쿼리 실행 시간은 $O{\displaystyle (}$ t ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\dplaystyle O(td^{2})$로 경계할 수 있으며$,$ 트리 깊이는 트리 너비로 경계할 수 있으므로 O${\displaystyle ((}t{\displaystyle w}$ ${\displaystyle \log \log }$ n${\displaystyle {}^{}}$)${\displaystyle {}^{}{2\mathrm{}}^{}}$ ) ${\displaystyle O(tw\log$ n$)^{2}}$도 유효한 상한이다$$.주요 출처는 그러나 최악의 경우 작동 시간에 대한 결과가 더 상세하게 설명되어 있다.^[18]

사전 처리 성능

수축위계층의 전처리시간 복잡성

알고리즘.	연도	시간 복잡성
임의[19] 처리	2015	${\displaystyle O(n^{2}\log n+nm)}$

성능 쿼리

수축 계층 구조 쿼리 시간 복잡성

알고리즘/분석 기법	연도	시간 복잡성	메모들
경계 성장 그래프[20]	2018	${\displaystyle O({\sqrt{n}\log n)}$
사용자 정의 가능한 수축 계층[21][22]	2013-2018	${\displaystyle O}$( ${\displaystyle t}$ ${\displaystyle {d\mathrm{}}^{}}$ 2${\displaystyle {}^{}}$) ${\dplaystyle$O($td^{2})$ $또는$ O${\displaystyle }$(${\displaystyle }$( t ${\displaystyle w}$ w${\displaystyle w}$ ${\displaystyle \log }$ ${\displaystyle {n\mathrm{}}^{}}$) 2${\displaystyle {}^{}}$) ${\displaystyle O(tw*\log$ n$)^\{$$2$} .	${\displaystyle t}$ ${\displaystyle d}$ ${\displaystyle td}$은(는) 트리 깊이이고 $t{\displaystyle }$ ${\displaystyle w}$ ${\displaystyle tw}$은(는) 트리 너비임
임의[19] 처리	2015	${\displaystyle {\sqrt{n}(6\ln(1/p)\log {\sqrt{n}+2)}$	정확하고 O-Notation이 없으며 높은 확률로 작동함
수정된 SARC[15]	2010	${\displaystyle O(h\log n\log D)^{2}}$	다항식 전처리
수정된 SARC[15]	2010	${\displaystyle O(h\log D)^{2}}$	초폴리노말 전처리

참조

외부 링크

오픈 소스 구현

• https://www.graphhopper.com/
• https://github.com/ifsttar/Tempus
• https://github.com/RoutingKit/RoutingKit
• http://project-osrm.org/
• http://www.opentripplanner.org/