최단거리
덤프버전 :
1. 개요[편집]
최단거리(最短距離)는 두 점 사이의 거리 중 가장 짧은 크기를 갖는 것을 말한다. 크게 이산수학적 최단거리와 기하학적 최단거리로 나뉜다. 일반적으로 최단거리라 함은 후자를 뜻한다.
2. 이산수학에서[편집]
경우의 수 문제중 유형화된 문제중 하나이다. 일반적으로 여러개의 점들 중에서 어떤점부터 다른 한 점까지의 최단 경로를 묻는 문제로 나온다. 아래의 기하학적 최단거리와 구별하기 위해 '점을 거쳐야 하는 규칙'을 추가한다.
2.1. 풀이[편집]
이 문제를 푸는 방법은 3가지로 나눌 수 있다.
2.1.1. 1,1,1법칙(시행착오법)[편집]
가장 귀찮지만 가장 생각은 안 하고 문제를 풀 수 있는 방법이다. 또한 후술할 법칙과는 달리 문제가 바뀌어도 풀이법에 크게 변화가 없는, 범용성이 뛰어나다.
1,1,1 법칙은 다음과 같다.
이렇게 생긴 지도에서 최단거리의 개수는 다음과 같다.
이렇게, 출발이 있는 행과 열의 포인트들에 1이라고 쓰고 어느 한 점의 최단거리의 개수를 그 점으로 갈 수 있는 점들의 최단거리의 개수의 합으로 하는 것 이다.
실수할 확률이 높기 때문에 이 방법이 후술할 방법보다 유용하지 않을 수도 있다. 하지만 대부분의 연습문제의 경우 지도가 복잡하거나, 혹은 장애물이 많아 후술할 방법을 쓰면 생각할 것이 매우 복잡해지기 때문에 이 방법이 유용하게 쓰인다.
2.1.2. 동자순열(같은 것을 포함한 순열[2])을 이용한 풀이[편집]
위처럼 생긴 지도에서 최단거리의 길이는 5이다. 또한 모든 최단거리는 오른쪽 3칸, 위쪽 2칸으로 구성되어 있음을 알 수 있다. 다시말해, 오른쪽 3번, 위쪽 2번을 배열해서 만든 배열은 모두 최단거리라는 것 이다. 따라서 동자순열의 원리에 따라 위 예시의 최단경로의 개수는 [math(\frac{5!}{3!2!})]과 같다.
이 풀이를 이용한 해법은 일반적으로 다음과 같이 정리할 수 있다.
[math(N{\sf x}M)]크기의 지도에서 최단경로의 개수는 [math(\frac{(N+M)!}{N!M!})]와 같다.
2.1.3. 조합을 이용한 풀이[편집]
조합을 이용한 풀이는 동자순열을 이용한 풀이와 맥락이 비슷하다. 다만 그 경우의 수를 구하는 방법이 조금 다를 뿐이다.
조합을 이용해 최단경로의 개수를 구하는 방법은 일반적으로 다음과 같다.
[math(N{\sf x}M)]크기의 지도에서 최단경로의 개수는 [math(N+M \choose M)]와 같다. ([math(p \choose q)]은 조합이다.)
2.2. 크기[편집]
격자 형태로 이루어진 이동 경로라는 점에서, 그 크기를 택시 노름(Taxicab norm)[3]으로 정의할 수 있으며 모든 이동경로의 길이의 절댓값을 더한 값이 된다. 이는 택시 거리 공간에서 아래의 기하학적 최단거리와 연결고리를 이룬다.
3. 기하학에서[편집]
3.1. 유클리드 기하학[편집]
두 점을 잇는 선분을 죽 그어주면 되는 간단한 방법으로 구할 수 있다. 도형 내에서는 대각선이라고도 한다.
해당 선분의 크기는 따로 유클리드 노름(Euclidean norm)이라고 한다.
3.2. 비유클리드 기하학[편집]
여기서는 측지선(geodesic, 測地線)이라는 이름으로 부른다.[4][5] 위의 대각선과는 달리, 이 측지선은 미분 기하학을 이용해서 구해야 하기 때문에 상당한 노가다가 된다.
측지선의 대표적인 예로, 구면기하학에서의 대원(Great circle)이 있는데, 해당 구의 지름에 대한 원 둘레 길이이다.
상술했듯 택시 기하학에서는 택시 노름이라는 이름으로 불린다.
이 문서의 내용 중 전체 또는 일부는 2023-12-19 01:07:18에 나무위키 최단거리 문서에서 가져왔습니다.[1] 고등학교 확률과 통계(확통)에서는 이 용어로 학습한다.[2] 고등학교 확률과 통계(확통)에서는 이 용어로 학습한다.[3] 맨해튼 노름(Manhattan norm)이라고도 한다.[4] 정확히는 곡면 위에서 최단거리 곡선은 측지선이지만, 그 역이 항상 성립하는 것은 아니다. 수학적 정의에 따르면 벡터 위의 점을 [math(\cdot=\displaystyle \frac{\operatorname{d}}{\operatorname{dt}})]라는 연산자라고 뒀을 때, 다차원공간에 놓여진 2차원 재매개화가 가능한 곡선 [math(\gamma)]에 대하여 점 [math(\gamma(t))]에서 [math(\ddot \gamma(t))]가 0 혹은 해당 곡면에 직교하는 곡선을 의미한다.[5] 또한 앞의 정의에 따라서, 모든 측지선은 상수인 속력을 갖게 된다. [math(\ddot \gamma\cdot\dot\gamma=0)]이므로 [math(\displaystyle \frac{\operatorname{d}}{\operatorname{dt}}\lVert \dot \gamma \rVert^{2}=2\ddot \gamma\cdot\dot\gamma=0)]이 되기 때문.