최단거리
1. 개요
두 점 사이의 거리 중 가장 짧은 크기를 갖는 것. 크게 이산수학적 최단거리와 기하학적 최단거리로 나뉜다. 일반적으로 최단거리라 함은 후자를 뜻한다.
2. 이산수학에서
경우의 수 문제중 유형화된 문제중 하나이다. 일반적으로 여러개의 점들 중에서 어떤점부터 다른 한 점까지의 최단 경로를 묻는 문제로 나온다. 아래의 기하학적 최단거리와 구별하기 위해 '점을 거쳐야 하는 규칙'을 추가한다.
2.1. 풀이
이 문제를 푸는 방법은 3가지로 나눌 수 있다.
2.1.1. 1,1,1법칙(노가다)
가장 귀찮지만 가장 생각은 안 하고 문제를 풀 수 있는 방법이다. 또한 후술할 법칙과는 달리 문제가 바뀌어도 풀이법에 크게 변화가 없는, 범용성이 뛰어나다.
1,1,1 법칙은 다음과 같다.
이렇게 생긴 지도에서 최단거리의 개수는 다음과 같다.
이렇게, 출발이 있는 행과 열의 포인트들에 1이라고 쓰고 어느 한 점의 최단거리의 개수를 그 점으로 갈 수 있는 점들의 최단거리의 개수의 합으로 하는 것 이다.
지도가 작은 경우, 혹은 장애물이 많은 경우 이 방법이 후술할 방법보다 유용할 수 도 있다. 하지만 대부분의 경우 실수할 확률도 높고 좋지 않은 풀이기 때문에 아래 방법도 알아두자.
2.1.2. 동자순열을 이용한 풀이
위처럼 생긴 지도에서 최단거리의 길이는 5이다. 또한 모든 최단거리는 오른쪽 3번, 위쪽 2번으로 구성되어 있음을 알 수 있다. 다시말해, 오른쪽 3번, 위쪽 2번을 배열해서 만든 배열은 모두 최단거리라는 것 이다. 따라서 동자순열의 원리에 따라 위 예시의 최단경로의 개수는 $$\frac{5!}{3!2!}$$과 같다.
이 풀이를 이용한 해법은 일반적으로 다음과 같이 정리할 수 있다.
$$N{\sf x}M$$크기의 지도에서 최단경로의 개수는 $$\frac{(N+M)!}{N!M!}$$와 같다.
2.1.3. 조합을 이용한 풀이
조합을 이용한 풀이는 동자순열을 이용한 풀이와 맥락이 비슷하다. 다만 그 경우의 수를 구하는 방법이 조금 다를 뿐이다.
조합을 이용해 최단경로의 개수를 구하는 방법은 일반적으로 다음과 같다.
$$N{\sf x}M$$크기의 지도에서 최단경로의 개수는 $$N+M \choose M$$와 같다. ($$p \choose q$$은 조합이다.)
2.2. 크기
격자 형태로 이루어진 이동 경로라는 점에서, 그 크기를 '''택시 노름'''(Taxicab norm)[1]으로 정의할 수 있으며 모든 이동경로의 길이의 절댓값을 더한 값이 된다. 이는 택시 거리 공간에서 아래의 기하학적 최단거리와 연결고리를 이룬다.
3. 기하학에서
3.1. 유클리드 기하학
두 점을 잇는 선분을 죽 그어주면 되는 간단한 방법으로 구할 수 있다. 도형 내에서는 대각선이라고도 한다.
해당 선분의 크기는 따로 '''유클리드 노름'''(Euclidean norm)이라고 한다.
3.2. 비유클리드 기하학
여기서는 '''측지선'''(geodesic)이라는 이름으로 부른다. 위의 대각선과는 달리, 이 측지선은 미분 기하학을 이용해서 구해야 하기 때문에 상당한 노가다가 된다.
측지선의 대표적인 예로, 구면기하학에서의 대원(Great circle)이 있는데, 해당 구의 지름에 대한 원 둘레 길이이다.
[1] 맨해튼 노름(Manhattan norm)이라고도 한다.