This is a good article. Click here for more information.

가장 넓은 경로 문제

Widest path problem
이 그래프에서 Maldon에서 Feering까지의 가장 넓은 경로는 대역폭 29로 Clacton, Tiptree, Harwich 및 Blaxhall을 통과합니다.

그래프 알고리즘에서 가장 넓은 경로 문제는 가중 그래프에서 지정된 두 꼭지점 사이의 경로를 찾는 문제이며, 경로에서 최소 가중치 에지의 무게를 최대화합니다.가장 넓은 경로 문제는 최대 용량 경로 문제라고도 합니다.경로 [1]길이 대신 병목 거리를 사용하도록 수정함으로써 대부분의 최단 경로 알고리즘을 가장 넓은 경로를 계산하도록 조정할 수 있습니다.그러나 대부분의 경우 보다 빠른 알고리즘이 가능합니다.

예를 들어 인터넷 내의 라우터 간의 접속을 나타내는 그래프에서는 엣지의 무게가 2대의 라우터 간의 접속 대역폭을 나타내는 경우 가장 넓은 패스의 문제는 가능한 최대 [2]대역폭을 가진2개의 인터넷노드 간의 엔드 투 엔드 패스를 찾는 문제입니다.이 경로의 최소 에지 웨이트는 경로의 용량 또는 대역폭으로 알려져 있습니다.네트워크 라우팅에서의 응용뿐만 아니라, 가장 넓은 경로 문제는 다방향 선거의 [3]승자를 결정하기 위한 슐제 방법의 중요한 구성요소이며, 디지털 합성,[4] 대사 경로 [5]분석 및 최대 [6]흐름 계산에 적용되어 왔다.

이와 밀접하게 관련된 문제, 미니맥스 경로 문제 또는 병목현상 최단 경로 문제는 엣지의 최대 무게를 최소화하는 경로를 요구합니다.교통 [7]계획을 포함한 어플리케이션을 갖추고 있습니다.가장 넓은 경로 문제에 대한 알고리즘은 알고리즘에 의해 실행되는 모든 무게 비교의 감각을 반전시키거나 모든 에지 무게를 부정으로 치환함으로써 미니맥스 경로 문제에 대한 알고리즘으로 변환할 수 있습니다.

무방향 그래프

무방향 그래프에서는 그래프의 최대 스패닝 트리 내의 2개의 정점 사이의 경로로서 가장 넓은 경로를 찾을 수 있으며 최소 스패닝 [8][9][10]트리 내의 2개의 정점 사이의 경로로서 미니맥스 경로를 찾을 수 있다.

어떤 그래프에서도 최소 무게 가장자리의 무게를 알게 되면 가장 넓은 경로를 찾기 위한 간단한 알고리즘이 있습니다. 즉, 너비 우선 검색 또는 깊이 우선 검색을 사용하여 모든 작은 가장자리를 삭제하고 나머지 가장자리 중 경로를 검색합니다.이 테스트에 기초하여 최대 스패닝트리를 사용하지 않는 무방향 그래프에서 가장 넓은 s-t 경로를 찾는 선형 시간 알고리즘도 존재합니다.알고리즘의 주요 아이디어는 선형 시간 경로 검색 알고리즘을 그래프의 중앙 에지 가중치에 적용한 다음 경로의 존재 여부에 따라 모든 작은 에지를 삭제하거나 모든 큰 에지를 축소하고 결과적으로 [9][11][12]작은 그래프에 반복하는 것입니다.

Fernandez, Garfinkel & Arbiol(1998)은 겹치는 영역의 여러 이미지를 결합하는 복합 항공 사진을 형성하기 위해 무방향 병목 현상 최단 경로를 사용한다.가장 넓은 경로 문제가 적용되는 하위 문제에서는 두 이미지가 이미 공통 좌표계로 변환되었습니다. 남은 과제는 겹치는 영역을 통과하여 두 이미지 중 하나를 다른 이미지로부터 나누는 곡선인 심을 선택하는 것입니다.심의 한쪽에 있는 픽셀은 이미지 중 하나에서 복사되고, 심의 다른 쪽에 있는 픽셀은 다른 이미지에서 복사됩니다.양쪽 화상의 픽셀을 평균화하는 다른 합성 방법과는 달리, 이것은 촬영되는 영역의 모든 부분의 유효한 사진 이미지를 생성한다.그들은 그리드 그래프의 가장자리에 걸쳐 있는 심이 얼마나 시각적으로 명백할지에 대한 수치 추정치로 가중치를 부여하고 이러한 가중치에 대한 병목현상 최단 경로를 찾는다.이 경로를 기존의 최단 경로가 아닌 심으로 사용하면 이미지 일부에서 가시성이 향상되고 다른 [4]곳에서 가시성이 저하되는 대신 시스템에서 모든 점에서 식별하기 어려운 심을 찾을 수 있습니다.

그리드 그래프의 반대쪽 두 모서리 사이의 미니맥스 패스 문제에 대한 해법은 두 폴리곤 체인 사이의 약한 프레셰 거리를 구하는데 사용할 수 있다.여기서 각 그리드 그래프 정점은 한 쌍의 선분을 나타내며, 각 체인에서 한 쌍의 선분을 나타내며, 가장자리의 무게는 한 쌍의 [13]선분을 통과하는 데 필요한 프레셰 거리를 나타낸다.

무방향 그래프의 모든 에지 가중치가 양수인 경우, 포인트 쌍 사이의 미니맥스 거리(미니맥스 경로의 최대 에지 가중치)는 초메트릭을 형성한다. 반대로 모든 유한 초메트릭 공간은 이러한 [14]방식으로 미니맥스 거리로부터 온다.최소 스패닝 트리로 구성된 데이터 구조는 데카르트 트리에서 가장 낮은 공통 상위 쿼리를 사용하여 쿼리당 일정한 시간에 정점 쌍 간의 최소 거리를 쿼리할 수 있도록 합니다.데카르트 트리의 루트는 가장 무거운 최소 스패닝 트리 에지를 나타내며, 루트의 자녀는 가장 무거운 에지를 제거하여 형성된 최소 스패닝 트리의 하위 트리에서 재귀적으로 생성된 데카르트 트리입니다.데카르트 트리의 잎은 입력 그래프의 정점을 나타내며, 두 정점 사이의 최소 거리는 가장 낮은 공통 조상인 데카르트 트리 노드의 무게와 같습니다.최소 스패닝 트리 가장자리가 정렬되면 이 데카르트 트리를 선형 [15]시간으로 구성할 수 있습니다.

유도 그래프

유도 그래프에서는 최대 스패닝트리 솔루션을 사용할 수 없습니다.대신에, 몇개의 다른 알고리즘이 알려져 있습니다.사용하는 알고리즘의 선택은, 패스의 개시 정점 또는 행선지 정점 중 어느 것이 고정되어 있는지, 또는 다수의 개시 정점 또는 행선지 정점의 패스를 동시에 찾을 필요가 있는지에 따라 달라집니다.

모든 쌍

올페어 광폭 문제는 유권자들이 선호도 순으로 후보를 정하는 다원적 선거에서 승자를 선택하는 슐제 방식으로 적용된다.슐제 방법은 정점이 후보를 나타내고 각 두 정점이 모서리에 의해 연결되는 완전한 방향 그래프를 구성합니다.각 엣지는 그것이 연결하는 두 후보 간의 페어 대결에서 승자에서 패자로 향하며, 그 대회의 승리 마진으로 라벨이 붙여집니다.그런 다음 이 방법은 모든 정점 쌍 사이의 가장 넓은 경로를 계산하고, 승자는 정점이 그 [3]반대보다 각 상대에게 더 넓은 경로를 가진 후보가 됩니다.이 방법을 사용한 선거의 결과는 Condorcet 방식(모든 페어별 경연에서 자동으로 승리하는 후보)과 일치하지만 일반적으로 Concorcet 방식 자체가 [16]실패한 경우에도 승자를 선택할 수 있습니다.Schulze 메서드는 Wikimedia [17]Foundation을 포함한 여러 조직에서 사용되고 있습니다.

투표 어플리케이션에서 발생하는 것과 같은 조밀한 방향 그래프에서 모든 노드 쌍에 대한 가장 넓은 경로 폭을 계산하기 위해 점근적으로 가장 빠른 것으로 알려진 접근법은 θ가 빠른 행렬 곱셈의 지수인 시간 O(n(3+ω)/2)가 걸린다.행렬 곱셈에 가장 잘 알려진 알고리즘을 사용하면 이 시간 범위는 O(n2.688)[18]가 됩니다.대신에 슐제 방법에 대한 참조 구현은 O3(n) [3]시간이 걸리는 더 단순한 Floyd-Warshall 알고리즘의 수정된 버전을 사용합니다.스파스 그래프의 경우 단일 소스 가장 넓은 경로 알고리즘을 반복적으로 적용하는 것이 더 효율적일 수 있습니다.

단일 소스

가장자리가 가중치에 따라 정렬되면 Dijkstra 알고리즘의 수정된 버전은 지정된 시작 정점과 그래프의 다른 모든 정점 사이의 병목 현상을 선형 시간으로 계산할 수 있습니다.Dijkstra 알고리즘의 기존 버전에 대한 속도 향상 뒤에 있는 핵심 아이디어는 이 알고리즘에 의해 정점이 고려되는 순서대로 각 정점에 대한 병목 거리 시퀀스가 에지 가중치의 정렬된 시퀀스의 단조로운 연속이라는 것이다. 따라서 Dijkstra 알고리즘의 우선순위 큐가 구현될 수 있다.버킷 큐: 1~m(그래프 내 에지 수)의 숫자로 색인화된 배열. 여기서 배열 셀 i에는 위치 i를 정렬된 순서대로 위치 i의 가장자리 무게인 정점이 포함됩니다.이 방법을 사용하면 가장 넓은 경로 문제를 정렬만큼 빠르게 해결할 수 있습니다. 예를 들어 가장자리 가중치가 정수로 표시되는 경우 m개의 정수 목록을 정렬하는 시간 범위도 이 [12]문제에 적용됩니다.

단일 소스 및 단일 수신처

Berman & Handler(1987)는 서비스 콜에서 기지로 돌아올 때 서비스 차량과 응급 차량이 최소 경로를 사용해야 한다고 제안한다.이 응용 프로그램에서는 차량 반환 중에 다른 서비스 콜이 발생할 경우 반환 시간이 응답 시간보다 덜 중요합니다.엣지의 무게가 엣지상의 지점에서 가능한 가장 먼 서비스 콜까지의 최대 주행시간인 미니맥스 패스를 이용하는 것으로, 서비스 콜의 수신으로부터 응답 [7]차량의 도착까지의 최대 가능한 지연을 최소한으로 억제하는 루트를 계획할 수 있다.Ullah, Lee & Hassoun(2009)은 대사 네트워크의 지배적인 반응 사슬을 모델링하기 위해 최대 경로(maximin path)를 사용한다.그 모델에서, 에지의 무게는 [5]에지로 표현되는 대사 반응의 자유 에너지이다.

Ford-Fulkerson 알고리즘에서는 최대 흐름 문제에 대한 다른 넓은 경로 적용이 발생합니다.흐름의 잔존 네트워크에서 최대 용량 경로를 따라 흐름을 반복적으로 증가시키면 최대 흐름을 찾는 데 필요한 증가 수 O(m log U)가 작아집니다.여기서 엣지 용량은 최대 U인 정수로 간주됩니다.단, 이 분석은 정확한 최대값을 가진 경로를 찾는 데 의존하지 않습니다.최대 용량의 상수 계수 내에 있는 모든 경로로 충분합니다.이 근사 아이디어를 Edmonds-Karp 알고리즘의 최단 경로 증강 방법과 결합하면 실행 시간이 O(mn log U)[6]인 최대 흐름 알고리즘이 됩니다.

입력 그래프의 에지 가중치 비교만 허용하고 [12][19]산술은 허용하지 않는 계산 모델에서도 단일 소스 및 단일 수신처를 가진 최대 용량 경로와 미니맥스 경로를 매우 효율적으로 찾을 수 있다.알고리즘은 최적의 경로의 병목 에지를 포함하는 것으로 알려진 일련의 S 에지를 유지합니다.초기적으로 S는 그래프의 모든 m 에지의 세트일 뿐입니다.알고리즘의 반복마다 S를 크기가 거의 같은 서브셋1 S, S2, ...의 순서 있는 시퀀스로 분할한다.이 분할의 서브셋의 수는 시간 O(m)의 반복적인 중위수 검색에 의해 서브셋 간의 모든 분할점을 찾을 수 있도록 선택된다.그런 다음 알고리즘은 에지를 포함하는 하위 집합의 인덱스에 따라 그래프의 각 에지에 다시 가중치를 부여하고 수정된 Dijkstra 알고리즘을 사용합니다. 이 계산 결과를 바탕으로 선형 시간 내에 어떤 서브셋이 병목 에지 가중치를 포함하는지 결정할 수 있습니다.다음으로 보틀 넥 웨이트를 포함하기로 결정한 서브셋S로i S를 대체하고 이 새로운 세트S로 다음 반복을 시작합니다.S를 분할할 수 있는 부분 집합의 수는 단계별로 기하급수적으로 증가하므로 반복 횟수는 반복 로그 함수 O(log*n)에 비례하며 총 시간은 O(m log*n)[19]입니다.각 엣지 웨이트가 기계정수인 연산모델에서는 이 알고리즘에서의 반복분할을 Han & Thorup(2002)의 리스트 분할기법으로 대체할 수 있어 S를 1단계로 O(θm) 소세트 S로i 분할할 수 있어 전체 시간범위를 [20]선형으로 할 수 있다.

유클리드 점집합

짙은 파란색 대역은 미니맥스 경로 길이가 2 이상인 가우스 소수 쌍을 분리합니다.

유클리드 평면의 점 집합에 대해 미니맥스 경로 문제의 변형도 고려되었다.무방향 그래프 문제와 마찬가지로, 이 유클리드 미니맥스 경로 문제는 유클리드 최소 스패닝 트리를 찾음으로써 효율적으로 해결할 수 있습니다. 트리의 모든 경로는 미니맥스 경로입니다.단, 홉길이를 최소화할 뿐만 아니라 같은 홉길이의 패스 중 패스의 총길이를 최소화할 수 있는 패스가 필요한 경우에는 문제가 더욱 복잡해집니다.용액은 기하학적 [21]스패너를 사용하여 근사할 수 있습니다.

수 이론에서, 미해결 가우스 해자 문제는 가우스 소수에서 미니맥스 경로가 유계 또는 무한 미니맥스 길이에 있는지 여부를 묻습니다.즉, 가우스 소수에 의해 정의된 무한 유클리드 점 집합의 모든 포인트 쌍 p와 q에 대해 p와 q 사이의 가우스 소수에 있는 미니맥스 경로가 최대 [22]B의 미니맥스 에지 길이를 갖는 상수 B가 존재하는가?

레퍼런스

  1. ^ Pollack, Maurice (1960), "The maximum capacity through a network", Operations Research, 8 (5): 733–736, doi:10.1287/opre.8.5.733, JSTOR 167387
  2. ^ Shacham, N(1992년),"계층적 데이터의 멀티 캐스트 라우팅"IEEE국제 회의 통신(ICC'92)에, vol. 3,를 대신하여 서명함. 1217–1221, doi:10.1109/ICC.1992.268047, hdl:2060/19990017646, 아이 에스비엔 978-0-7803-0599-1, 왕, 정화, Crowcroft, J.(1995년),"Bandwidth-delay 라우팅 알고리즘 기반", IEEE글로벌 통신 회의(범세계 통신 체계다. 95). 2129–2133, doi:10.1109/GLOCOM.1995.502780, 아이 에스비엔 978-0-7803-2509-8 3,를 대신하여 서명함 vol..
  3. ^ a b c Schulze, Markus (2011), "A new monotonic, clone-independent, reversal symmetric, and Condorcet-consistent single-winner election method", Social Choice and Welfare, 36 (2): 267–303, doi:10.1007/s00355-010-0475-4
  4. ^ a b Fernández, Elena; Garfinkel, Robert; Arbiol, Roman (1998), "Mosaicking of aerial photographic maps via seams defined by bottleneck shortest paths", Operations Research, 46 (3): 293–304, doi:10.1287/opre.46.3.293, JSTOR 222823
  5. ^ a b Ullah, E.; Lee, Kyongbum; Hassoun, S. (2009), "An algorithm for identifying dominant-edge metabolic pathways", IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2009), pp. 144–150
  6. ^ a b Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), "7.3 Capacity Scaling Algorithm", Network Flows: Theory, Algorithms and Applications, Prentice Hall, pp. 210–212, ISBN 978-0-13-617549-0
  7. ^ a b Berman, Oded; Handler, Gabriel Y. (1987), "Optimal Minimax Path of a Single Service Unit on a Network to Nonservice Destinations", Transportation Science, 21 (2): 115–122, doi:10.1287/trsc.21.2.115
  8. ^ Hu, T. C. (1961), "The maximum capacity route problem", Operations Research, 9 (6): 898–900, doi:10.1287/opre.9.6.898, JSTOR 167055
  9. ^ a b Punnen, Abraham P. (1991), "A linear time algorithm for the maximum capacity path problem", European Journal of Operational Research, 53 (3): 402–404, doi:10.1016/0377-2217(91)90073-5
  10. ^ Malpani, Navneet; Chen, Jianer (2002), "A note on practical construction of maximum bandwidth paths", Information Processing Letters, 83 (3): 175–180, doi:10.1016/S0020-0190(01)00323-4, MR 1904226
  11. ^ Camerini, P. M. (1978), "The min-max spanning tree problem and some extensions", Information Processing Letters, 7 (1): 10–14, doi:10.1016/0020-0190(78)90030-3
  12. ^ a b c Kaibel, Volker; Peinhardt, Matthias A. F. (2006), On the bottleneck shortest path problem (PDF), ZIB-Report 06-22, Konrad-Zuse-Zentrum für Informationstechnik Berlin
  13. ^ 를 클릭합니다Alt, Helmut; Godau, Michael (1995), "Computing the Fréchet distance between two polygonal curves" (PDF), International Journal of Computational Geometry and Applications, 5 (1–2): 75–91, doi:10.1142/S0218195995000064.
  14. ^ Leclerc, Bruno (1981), "Description combinatoire des ultramétriques", Centre de Mathématique Sociale. École Pratique des Hautes Études. Mathématiques et Sciences Humaines (in French) (73): 5–37, 127, MR 0623034
  15. ^ Demaine, Erik D.; Landau, Gad M.; Weimann, Oren (2009), "On Cartesian trees and range minimum queries", Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Lecture Notes in Computer Science, vol. 5555, pp. 341–353, doi:10.1007/978-3-642-02927-1_29, hdl:1721.1/61963, ISBN 978-3-642-02926-4
  16. ^ 구체적으로 슐제 방식이 깨지지 않는 유일한 연결고리는 서로 동등하게 넓은 경로를 가진 두 후보 사이의 연결고리다.
  17. ^ Jesse Plamondon-Willard, 2008년 5월 선호도 투표 사용 이사회 선거, 2008년 6월 Wikimedia Board 선거 결과, 2008년 6월 Wikimedia Board 선거, 2008년 6월 및 2009년 8월 이사회 선거 참조.
  18. ^ Duan, 란, Pettie, 세스(2009년),"를 빠른 알고리즘(max,분)-matrix 곱셈과 최단 경로 병목 현상", 20회 ACM-SIAM 심포지엄 이산화 이론을(SODA '09)원 회보를 대신하여 서명함. 384–391.또한 모든 쌍 넓은 길을 가속화하기 위해 빠른 매트릭스 곱셈 연산에서도 사용 이전의 알고리즘은 Vassilevska, 버지니아, 윌리엄스, 라이언, Yuster, 라파엘(2007년),"일반 그래프에 정말sub-cubic 시간에All-pairs 애로 경로", 제39회 연간 ACM심포지움 이론 컴퓨팅에(팩스 축적 변환 장치 '07), 뉴욕의 회보:ACM,를 대신하여 서명함. 585–589를 참조하십시오., CiteSeerX 10.1.1.164.9808, doi:10.1145/1250790.1250876, 아이 에스비엔 9781595936318, MR2402484과 Vassilevska, 버지니아의 5장(2008년), 효율적 알고리즘 경로의 문제 가중 Graphs에(PDF), 박사 학위 논문 보고서 CMU-CS-08-147, 카네기 Mellon대학교 학교 전산학.
  19. ^ a b Gabow, Harold N.; Tarjan, Robert E. (1988), "Algorithms for two bottleneck optimization problems", Journal of Algorithms, 9 (3): 411–417, doi:10.1016/0196-6774(88)90031-4, MR 0955149
  20. ^ 를 클릭합니다Han, Yijie; Thorup, M. (2002), "Integer sorting in O(n√log log n) expected time and linear space", Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002), pp. 135–144, doi:10.1109/SFCS.2002.1181890, ISBN 978-0-7695-1822-0.
  21. ^ Bose, Prosenjit; Maheshwari, Anil; Narasimhan, Giri; Smid, Michiel; Zeh, Norbert (2004), "Approximating geometric bottleneck shortest paths", Computational Geometry. Theory and Applications, 29 (3): 233–249, doi:10.1016/j.comgeo.2004.04.003, MR 2095376
  22. ^ 를 클릭합니다Gethner, Ellen; Wagon, Stan; Wick, Brian (1998), "A stroll through the Gaussian primes", American Mathematical Monthly, 105 (4): 327–337, doi:10.2307/2589708, JSTOR 2589708, MR 1614871.