1. 개요
최단거리( 最 短 距 離)는 두 점 사이의 거리 중 가장 짧은 크기를 갖는 것을 말한다. 크게 이산수학적 최단거리와 기하학적 최단거리로 나뉜다. 일반적으로 최단거리라 함은 후자를 뜻한다.2. 이산수학에서
|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( 공식) · 순열( 완전순열 · 염주순열) · 치환 · 분할( 분할수) · #s-2 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
경우의 수 문제중 유형화된 문제중 하나이다. 일반적으로 여러개의 점들 중에서 어떤점부터 다른 한 점까지의 최단 경로를 묻는 문제로 나온다. 아래의 기하학적 최단거리와 구별하기 위해 '점을 거쳐야 하는 규칙'을 추가한다.
2.1. 풀이
이 문제를 푸는 방법은 3가지로 나눌 수 있다.2.1.1. 1,1,1법칙( 시행착오법)
가장 귀찮지만 가장 생각은 안 하고 문제를 풀 수 있는 방법이다. 또한 후술할 법칙과는 달리 문제가 바뀌어도 풀이법에 크게 변화가 없는, 범용성이 뛰어나다.1,1,1 법칙은 다음과 같다.
| (0,1) | (1,1) | (도착) |
| (출발) | (1,0) | (2,0) |
| (0,1)-(1) | (1,1)-(2) | (도착)-(3) |
| (출발)-(1) | (1,0)-(1) | (2,0)-(1) |
실수할 확률이 높기 때문에 이 방법이 후술할 방법보다 유용하지 않을 수도 있다. 하지만 대부분의 연습문제의 경우 지도가 복잡하거나, 혹은 장애물이 많아 후술할 방법을 쓰면 생각할 것이 매우 복잡해지기 때문에 이 방법이 유용하게 쓰인다.
2.1.2. 동자순열(같은 것을 포함한 순열[1])을 이용한 풀이
| (0,2) | (1,2) | (2,2) | (도착) |
| (0,1) | (1,1) | (2,1) | (3,1) |
| (출발) | (1,0) | (2,0) | (3,0) |
이 풀이를 이용한 해법은 일반적으로 다음과 같이 정리할 수 있다.
[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)[2]으로 정의할 수 있으며 모든 이동경로의 길이의 절댓값을 더한 값이 된다. 이는 택시 거리 공간에서 아래의 기하학적 최단거리와 연결고리를 이룬다.3. 기하학에서
3.1. 유클리드 기하학
두 점을 잇는 선분을 죽 그어주면 되는 간단한 방법으로 구할 수 있다. 도형 내에서는 대각선이라고도 한다.해당 선분의 크기는 따로 유클리드 노름(Euclidean norm)이라고 한다.
3.2. 비유클리드 기하학
여기서는 측지선(geodesic, 測 地 線)이 최단 거리와 대응되는 개념이다. 측지선이란 다차원공간에 놓여진 2차원 재매개화가 가능한 곡선 [math(\gamma)]에 대하여 점 [math(\gamma(t))]에서 [math(\ddot \gamma(t))]가 0 혹은 해당 곡면에 직교하는 곡선을 의미한다.[3] 정의로부터 [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)]이므로 모든 측지선은 상수인 속력을 갖는다. 측지선의 대표적인 예로 구면기하학에서의 대원(Great circle)이 있는데, 해당 구의 지름에 대한 원 둘레 길이이다.곡면 위에서 최단거리 곡선은 측지선이지만, 측지선이 최단거리 곡선인 것은 아니다. 예를 들어 원통 표면을 두 바퀴 둘러서 높이가 서로 다른 두 점을 잇는 최대한 짧은 곡선을 생각하면, 이 선은 측지선이지만 두 점을 잇는 최단거리 곡선은 아니다. 유클리드 기하학에서의 대각선과는 달리, 이 측지선은 미분 기하학을 이용해서 구해야 하기 때문에 상당한 노가다가 된다.
상술했듯 택시 기하학에서는 택시 노름이라는 이름으로 불린다.