최근 수정 시각 : 2024-04-02 12:49:35

최단거리



1. 개요2. 이산수학에서
2.1. 풀이
2.1.1. 1,1,1법칙( 시행착오법)2.1.2. 동자순열(같은 것을 포함한 순열)을 이용한 풀이2.1.3. 조합을 이용한 풀이
2.2. 크기
3. 기하학에서

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)
이렇게, 출발이 있는 행과 열의 포인트들에 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)
위처럼 생긴 지도에서 최단거리의 길이는 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)[2]으로 정의할 수 있으며 모든 이동경로의 길이의 절댓값을 더한 값이 된다. 이는 택시 거리 공간에서 아래의 기하학적 최단거리와 연결고리를 이룬다.

3. 기하학에서

<rowcolor=#fff> ' 기하학· 위상수학
'
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"
평면기하학에 대한 내용은 틀:평면기하학 참고.
기본 대상
공리 유클리드 기하학 · 비유클리드 기하학
도형 기본 도형 평면 · 부피 · 꼬인 위치 · 각기둥 · 각뿔 · 원기둥 · 원뿔 · ( 공 모양) · 전개도 · 겨냥도 · 다면체 ( 정다면체) · 정사영
곡면 타원면 · 타원포물면 · 쌍곡포물면 · 원환면
프랙털 도형 시에르핀스키 삼각형 · 시에르핀스키 사각형( 멩거 스펀지) · 망델브로 집합 · 코흐 곡선 · 드래곤 커브
기타 다포체 · 초구 · 준구 · 일각형 · 이각형
다루는 대상과 주요 토픽
대수기하학 대수다양체 · · 스킴 · 에탈 코호몰로지 · 모티브 · 타원곡선
미분기하학 미분다양체 · 측지선 · 곡률( 스칼라 곡률 · 리만-크리스토펠 곡률 텐서 · 리치 텐서) · 열률 · 텐서 · 쌍곡 공간( 쌍곡삼각형 · 푸앵카레 원반) · 타원 공간( 구면삼각형) · 아핀접속
위상수학 위상 공간 유계 · 옹골 집합 · 다양체 · 택시 거리 공간 · 연결 공간 · 위상수학자의 사인곡선
위상도형 사영평면 · 뫼비우스의 띠 · 클라인의 병 · 매듭( 목록)
주요 성질·정리 분리공리 · 우리손 거리화정리( 우리손 보조정리) · 베르 범주 정리
대수적 위상수학 사슬 복합체 · 호몰로지 대수학( 호몰로지 · 코호몰로지) · 호모토피 · mapping class group · 닐센-서스턴 분류
기타 차원 · 좌표계 · 거리함수 · 그물 · 쾨니히스베르크 다리 건너기 문제
정리·추측
실베스터-갈라이 정리 · 해안선 역설 · 바나흐-타르스키 역설 · 라이데마이스터 변환 · 오일러 지표 · 푸앵카레 정리 · 페르마의 마지막 정리 · 호지 추측미해결 · 버츠와 스위너톤-다이어 추측미해결
분야
논증기하학 · 대수기하학 · 미분기하학 · 해석기하학 · 매듭이론 · 프랙털 이론 · 정보기하학 · 위상 데이터분석 }}}}}}}}}

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)이 있는데, 해당 의 지름에 대한 원 둘레 길이이다.

곡면 위에서 최단거리 곡선은 측지선이지만, 측지선이 최단거리 곡선인 것은 아니다. 예를 들어 원통 표면을 두 바퀴 둘러서 높이가 서로 다른 두 점을 잇는 최대한 짧은 곡선을 생각하면, 이 선은 측지선이지만 두 점을 잇는 최단거리 곡선은 아니다. 유클리드 기하학에서의 대각선과는 달리, 이 측지선은 미분 기하학을 이용해서 구해야 하기 때문에 상당한 노가다가 된다.

상술했듯 택시 기하학에서는 택시 노름이라는 이름으로 불린다.
[1] 고등학교 확률과 통계(확통)에서는 이 용어로 학습한다. [2] 맨해튼 노름(Manhattan norm)이라고도 한다. [3] 미분 연산자 [math(\displaystyle \frac{\operatorname{d}}{\operatorname{dt}})]를 벡터 위의 점으로 표기하였다.