- 다양한 주제에 대해 자유롭게 글을 작성하는 게시판입니다.
Date | 18/01/10 22:48:15 |
Name | 유리소년 |
Subject | 거리함수 이야기 (1) |
1. 거리함수의 개념 거리distance는 두 개의 객체가 얼마나 떨어져 있는지를 나타내는 척도입니다. 일반적으로 거리라는 것은 두 장소 사이를 연결한 직선의 공간적 길이나 두 시각 사이의 시간의 간격 등을 가리키는 말로 쓰입니다만 수학에서는 이것을 일반화하여 다양한 상황에서 적용할 수 있는 [떨어진 정도] 를 묘사하는 데 쓰기도 합니다. 예를 들어, 지하철을 타고 사당역에서 광화문역으로 가려고 한다고 합시다. 이때 사당역-광화문역 사이를 연결한 직선의 거리는 별 의미가 없습니다. 지하철은 직선으로 다니지 않으니까요. 이 상황에서 승객에게 사당역-광화문역 사이가 얼마나 떨어져 있는지를 나타내는 가장 적절한 척도는 '광화문역-사당역을 연결하는 지하철 노선들 중 가장 길이가 짧은 것의 길이'가 될 겁니다. 그러므로 '역 A-역 B를 연결하는 지하철 노선들 중 가장 길이가 짧은 것의 길이'는 [거리 개념을 지하철역들 사이로 일반화한 것]이 됩니다. 그러면 두 객체 사이에서 발생하는 숫자값을 아무거나 잡아도 그것을 거리 개념으로 쓸 수 있는 걸까요? 그건 아닙니다. 수학에서 거리함수metric function/distance function은 다음의 조건들을 만족하는 함수로 이야기합니다. 즉, 다음 테스트들을 전부 통과하면 거리 개념으로 쓰기에 합격이고, 하나라도 실패하면 거리 개념으로 쓰기에 적합하지 않다는 거죠. 1. 거리가 가질 수 있는 값은 0 또는 양수여야 한다. - 당연합니다. 마이너스 거리라는 건 말이 안되잖아요. 2. 동일한 객체인 A와 A 사이의 거리는 0이다. 또한, 두 객체가 서로 다르다면, 둘 사이의 거리는 무조건 0보다 커야 한다. (식별가능성) - 이것도 당연합니다. 3. A와 B 사이의 거리는 B와 A 사이의 거리와 같아야 한다. (상호대칭성) - 납득이 가면서도 중요한 성질입니다. 예를 들어, 위에 든 지하철 노선 예시는 이 조건을 만족합니다. 광화문역에서 출발해서 사당역에 도착할 때까지의 최단 지하철노선의 길이는 사당역에서 출발해서 광화문역에 도착할 때까지의 최단 지하철노선의 길이와 같기 때문입니다. 그러나, 다음 예시는 이 조건을 만족하지 않습니다. 두 사람 A와 B 사이의 친밀함의 정도를 'A가 B에게 한달 동안 보내는 카톡 메시지의 수'라고 주장하면, 이 척도는 거리 개념으로 쓸만한 조건을 만족시키지 못합니다. 집착이 심한 A가 대쉬를 할 때 B에게 카톡 100개를 보냈지만, B는 맨날 읽씹을 하면서 답장 10개를 보낸 경우, A가 B에게 보낸 메시지 수와 B가 A에게 보낸 메시지 수는 다르고, A는 자신이 B와 친하다고 착각할 수 있지만 B 입장에서는 A가 짜증날 수 있기 때문입니다. 거리 개념을 묘사하기 위한 척도로 쓰기 위해서는 상호대칭적이어야 합니다. 4. A와 C 사이의 거리는 A와 B 사이의 거리 + B와 C 사이의 거리 보다 작거나 같아야 한다. (최단성, 삼각부등식) - 바로 와닿지 않을 수도 있겠지만, 가장 핵심적으로 만족해야 하는 조건 중 하나입니다. 이것을 더 쉽게 이해하기 위해서는 위의 지하철 최단노선길이의 예를 다시 들어 봅시다. 당신이 광화문역에서 출발해 사당역에 도착하고 싶은 상황에서, 지하철 경로들에 대한 선택지 자체는 매우 많습니다. 당신은 도중에 심심해서 왕십리나 혜화까지 갔다올 수도 있을 겁니다. 하지만 [그래서 두 역 사이가 얼마나 떨어져 있다는 건데?] 라는 본질적인 질문에 답하기 위해서는, 광화문에서 출발해서 사당역에 도착하는 수많은 경로들 중 가장 짧은 것을 택하는 것이 가장 자연스러울 겁니다. 빙빙 돌아가는 경로들은 별로 중요하지 않으니까요. 위의 조건을 [거리 = 최단 경로를 묘사하는 척도]로 쓰기 위해서 넣었다고 생각한다면, 수식은 자연스럽게 납득됩니다. [A -> C로 가려면 A -> C로 가는 직통 노선을 택하는 게 중간에 A -> B -> C를 거쳐 가는 것보다 나아야 한다] 는 뜻이니까요. 2. Lp 거리 많은 거리함수들 중 범용적이라 여겨지는 것은 두 장소 사이의 물리적 거리를 묘사하는 Lp 거리일 겁니다. 중학교 과정부터 배우는 가장 친숙한 거리는 역시 [두 장소 사이를 연결하는 선의 공간적 길이] 인데, 이것도 Lp 거리의 일부이지요. 두 점을 연결하는 선의 길이는 피타고라스 센세의 정리에 의해 다음과 같이 계산됩니다. ![]() 이를 유클리드 거리 또는 L2 거리라고 합니다. 왜 다른 이름이 L2 거리인지는 조금 이따가 설명. 이 함수는 위의 조건 4개를 전부 만족합니다. 정규 교과 과정에 나오니까 설명은 생략하도록 합시다. 이것을 확장한 것으로 Lp 거리 (민코프스키 거리)라는 것이 있습니다. 요렇게 표현하는 녀석이지요. p ≥ 1이라면 이 함수도 역시 위의 조건 4개를 만족해서 거리의 일부분으로 쓸 수 있습니다. (p < 1이면 안됩니다. 자세한 설명은 생략) 잘 보면 저 식에 p = 2를 넣으면 우리가 아는 유클리드 거리가 됨을 알 수 있습니다. 즉 유클리드 거리는 Lp 거리의 특수한 경우이며, 그래서 유클리드 거리의 또 다른 이름이 L2 거리인 거지요. 1 이상의 수많은 p들 중 다른 것들은 그렇게 자주 쓰이진 않고 p = 1 (L1 거리/맨하탄 거리), p = 2 (L2 거리/유클리드 거리), p = ∞ (L∞ 거리/체비세프 거리) 가 가장 많이 쓰입니다. p = 1의 경우 위의 식은 이렇게 변합니다. ![]() L1 거리는 맨하탄 거리, 택시캡 거리 등등 많은 이름들이 있습니다만 저는 이 글에선 영걸전 거리 또는 SRPG 거리라고 부르겠습니다. ![]() 위의 수식과 같이 봅시다. 수식이 나타내는 값은 [가로 거리와 세로 거리를 더한 것]입니다. 영걸전에서 유닛은 상하좌우로만 이동할 수 있고, 관우가 왼쪽 위 대각선 1칸으로 가려면 왼쪽 1칸 + 위쪽 1칸 식으로 이동해야 하기 때문에 이동력 2를 써야하죠. 때문에 왼쪽 위 대각선 1칸과의 거리는 2가 됩니다. 많은 SRPG들은 우리가 아는 L2 거리가 아닌 L1 거리를 사용합니다. L2 거리라면 왼쪽 위 대각선 1칸과의 거리는 루트2가 되어야 하지만, 우리는 영걸전이나 조조전을 할때 직관적으로 '대각선 1칸은 이동력 2를 소모해야 갈 수 있는 곳'이라는 것을 받아들이고 있죠. p = ∞의 경우에는 위의 식은 다음과 같이 정의할 수 있습니다. ![]() Lp 거리의 p에 무한대를 대입하면 왜 저렇게 되느냐? 라는 것에 대해선.. p = ∞를 직접 대입한 것이 아니라 Lp 거리에 lim p→∞를 적용시켜서 얻는 함수입니다. 수학 계산이기 때문에 역시 여기에 대해서는 자세한 설명은 생략합니다. L∞ 거리는 체비세프 거리라는 이름이 있지만, 여기서는 체스킹 거리라는 이름을 사용하겠습니다. ![]() 역시 수식과 같이 봅시다. 수식이 나타내는 값은 [가로 거리, 세로 거리 둘 중에 큰 것] 입니다. 체스에서 킹은 상하좌우뿐만 아니라 한번에 대각선으로도 이동할 수 있기 때문에, 킹이 왼쪽 위 대각선 2칸으로 가려면 왼쪽 2칸 -> 위쪽 2칸을 갈 필요 없이 그냥 대각선으로 두번 가면 됩니다. 때문에 2턴만에 이동이 가능하지요. 즉 체스의 킹은 이동할 때 L∞ 거리를 사용하는 것입니다. 다음 글에서는 두 장소 사이의 물리적 거리가 아닌 예들을 소개하겠습니다. 9
|