본문으로 이동

최단 경로 문제

위키백과, 우리 모두의 백과사전.

그래프 이론에서 최단 경로 문제란 가장 짧은 경로에서 두 꼭짓점을 찾는 문제로서, 가중 그래프에서는 구성하는 변들의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제이다. 예를 들면, 도로 지도 상의 한 지점에서 다른 지점으로 갈 때 가장 빠른 길을 찾는 것과 비슷한 문제이다. 이 때, 각 도로 구간에서 걸리는 시간을 변의 가중치라 할 수 있다.

보통은 주어진 가중 그래프에서 (V는 꼭짓점, E는 변, 가중치 함수 f : E → R) 가 v에서 v'로 가는 모든 경로들 중 최소가 되도록 하는 경로를 찾는 문제이다. 이런 문제는 단일-쌍 최단 경로 문제라고 부르며, 아래의 일반화된 문제들과는 차이가 있다.

  • 단일-출발 최단 경로 문제 : 단일 꼭짓점 v에서 출발하여 그래프 내의 모든 다른 꼭짓점들에 도착하는 가장 짧은 경로를 찾는 문제이다.
  • 단일-도착 최단 경로 문제 : 모든 꼭짓점들로부터 출발하여 그래프 내의 한 단일 꼭짓점 v로 도착하는 가장 짧은 경로를 찾는 문제이다. 이 문제에서 그래프 내의 꼭짓점들을 거꾸로 뒤집으면 출발 최단 경로 문제로 바뀔 수 있다.
  • 전체-쌍 최단 경로 문제 : 그래프 내의 모든 꼭짓점 쌍들 사이의 최단 경로를 찾는 문제이다.

위의 일반화된 문제들은, 전체-쌍 중 단일-쌍만으로 찾아가는 단순 접근 방식보다, 확실히 더 효율적인 알고리즘을 가진다.

알고리즘

[편집]

아래는 이 문제를 해결하기 위한 주요 알고리즘들이다.

응용

[편집]

최단 경로 알고리즘은 웹 지도 등에서 실제 위치들 사이에 자동으로 경로를 탐색하여 운전방향을 잡아주고 명확한 경로를 찾는 데에 응용된다.

꼭짓점(V)은 상태, 변(E)은 가능한 전이로 표현되는 그래프와 같이, 만약 비결정적 추상 기계로 표현되는 어떤 문제에 대하여, 최단 경로 알고리즘은 목표 상태에 도달하기 위한 최적의 선택 순서를 찾거나, 주어진 상태에 도달하는 시간의 하한선을 찾는데 사용될 수 있다.

예를 들어, 한 꼭짓점이 루빅스 큐브와 같은 퍼즐 상태에 있고 각 방향의 가장자리 끝선이 한 번의 회전과 일치한다면, 최단 경로 알고리즘은 최소로 회전시키는 루빅스 큐브의 해답을 찾는데 응용할 수 있다.

최단 경로 문제를, 네트워크 또는 장거리통신에서는 최소-지연 경로 문제라고 부르기도 하며, 최광폭 경로 문제와 함께 다루어지는 것이 보통이다. 예를 들어, 최단 (최소-지연) 최광폭 경로, 최광폭 최단 (최소-지연) 경로가 있다.

6단계 분리(six degrees of separation) 게임에서, 같은 영화에 출연하는 영화배우들을 나타내는 그래프에서 최단 경로를 찾는 데에 응용되기도 한다.

대니 첸은 운영 연구, 공장 설비 배치, 로봇공학, 수송, VLSI 설계 등에 응용할 수 있음을 언급하였다.

관련 문제

[편집]
 컴퓨터 기하학에서의 최단경로문제에 대해 알고 싶다면 유클리드 최단 경로 문서를 참고하십시오.

이동하는 세일즈맨 문제는 모든 경로를 한번씩 지나갔다가 시작점으로 돌아오는 가장 짧은 경로를 찾는 문제이다. 최단 경로 문제와는 달리 이 문제는 NP-완전하여, 효율적인 해를 찾을 수 없다.(P-NP 문제 참고) 또한, 최장 경로 문제 역시 NP-완전하다

같이 보기

[편집]

각주

[편집]
  • (Journal of Korea Multimedia Society Vol. 19, No. 8,-A Combination Method of Trajectory Data using Correlated

Direction of Collected GPS Data, Kwang Min Koo, Heemin Park)https://pdfs.semanticscholar.org/3389/0374991fac0fcc3e12b9a4d9a9f60299b16d.pdf

원본 주소 "https://ko.wikipedia.org/w/index.php?title=최단_경로_문제&oldid=37164723"