SSISO Community

OpenGL | ES 튜토리얼 6편 [안드로이드]ndk란? 인공지능에 자주 나오는 수학 4 - 유사 계수(Similar Coefficient) 인공지능에 자주나오는 수학 2 - 벡터 공간(Vector Space)과 벡터 내적(Vector InnerProduct) 인공지능에 자주나오는 수학 1 - 유클리디안 거리(Euclidean Distance) 인공지능에 자주 나오는 수학 3 - 맨하탄 거리(Manhattan Distance) TSR Workshop obj viewer 구현 및 정리 안드로이드(Android) scale 이용해서 애니메이션(Animation) 구현하는 방법 Designing AI Algorithms For Turn-Based Strategy Games 3

시소당

인공지능에 자주 나오는 수학 3 - 맨하탄 거리(Manhattan Distance)

이번에는 거리를 측정하는 방법 중에 또 다른 방법 맨하탄 거리(Manhattan Distance) 측정법에 대해서 이야기 할려고 합니다.

맨하탄은 미국의 도시 이름인데요. 읽는 사람에 따라 "맨하탄", "맨하턴", "맨하튼", "매너턴" 등 다양합니다.

저는 그냥 "맨하탄"이라고 하겠습니다.

맨하탄 거리(Manhattan Distance) 측정법은 Taxicab Distance, Rectlinear Distance, City Block Distance, L1 Distance와 같은 여러가지 별명을 가지고 있습니다.
전에 유클리디안 거리 계산법을 공부 했었습니다. 이는 두 점을 잇는 가장 짧은 거리의 길이입니다.
만약 이 두 점이 도로 정비가 잘된 어떤 큰 도시의 두 장소를 의미하고 한 장소에서 다른 장소로 이동 하려 한다면 건물들을 가로 질러 갈 수는 없으므로 길을 이용해서만 가야할 것 입니다.
여기서 건물을 가로질러 갈 수 있다고 생각하고 계산하는 방식은 유클리디안 거리 계산이고 길을 이용할 때의 거리는 맨하탄 거리라고 이해하면 빠를 듯 합니다.

아주 오래 전 미국에 출장 갔다가 비행기 안에서 맨하탄을 내려다 본적이 있습니다. (직접 가보진 않았음... ^^;)
비록 비행기 내에서 본거지만 9.11 테러 전의 일이라 트레이드 센터도 보고 자유여신상도 보았습니다. 물론 자세히 본건아니구요. 모두 쫌 비스듬히 봤죠. ㅋㅋ
맨하탄을 비행기에서 본 그 때의 느낌은 멋지다라는 것과 길이 아주 반듯하게 정리가 잘 되어 있구나 하는 생각이었습니다.
다음은 구글어스에서 본 맨하탄의 전경입니다.

아래의 URL은 어떤 분이 저와 같이 맨하탄을 비행기에서 보고 찍은 사진이 것 같습니다. 그냥 한번 보세요.

http://imagebingo.naver.com/album/image_view.htm?uid=pudding0521&bno=17158&nid=6295
미국간 이야길 하려고 꺼낸 건 아니구요.
맨하탄 거리 측정법이 이러한 이유로 이름이 지어 졌다고 해서 하는 이야기 입니다. ㅎㅎ

맨하탄 거리 측정법은 단순히 두 점의 세로축의 차이와 가로축의 차이를 더하는 것입니다.

위의 그림은 위키피디아(http://en.wikipedia.org/wiki/Taxicab_geometry)에서 가져온 그림인데요.
위의 그림처럼 길이 반듯 반듯한게 나 있는 도시에서 한 장소에서 다른 장소로 이동한다고 생각해 보죠.
이 때 녹색선이 가장 짧고 빠르겠지만 이는 건물들에 막혀서 갈 수 없는 경로죠. (이게 유클리디안 거리입니다.)
일반적으로 사람들은 파란색 경로를 따라가겠네요. (여러분은 어떤길이 택하실지...)
그런데 사실 빨간색 길이나 파란색 길이나 노란색 길이 모두 같은 길이를 갖습니다.
믿지 못하겠다면 직접 지나가는 블록의 면수을 세어 보셔도 좋습니다. 12개의 블록 면을 지나야 한 다는 것을 알 수 있죠.
그래서 맨하탄 거리 측정법에서는 파란색 경로 처럼 계산하려면 복잡하니깐... 빨간색 경로의 길이를 계산해서 그 것을 거리(distance)로 합니다.

두 점이 각각 (x1, y1), (x2, y2) 라는 좌표를 갖는다고 할때 맨하탄 거리 측정 법을 공식으로 쓴다면 다음과 같습니다.

유클리디안 공식은 제곱도 있고 루트도 있고 해서 계산이 복잡했는데... 맨하탄은 정말 간단하네요.

복잡하다면 차이값을 절대값으로 한다는 것을 들 수 있을까요? ㅎㅎ

이를 3차원으로 확장시키면 다음과 같이 쓸 수 있습니다.

이를 일반화 시키기 위해 두 점 A,B를 A(a1, a2, a3 ... an), B(b1, b2, b3 ... bn)이라고 정의하면

과 같이 쓸 수 있습니다.

여기까지가 맨하탄 거리 측정 공식인데요.

한가지만 더 이야기 하도록 하겠습니다.

유클리디안 거리 공식과 맨하탄 거리 공식에는 관련성이 있습니다.

이미 맨하턴 거리 공식을 "L1 Distance"라고도 한다고 이야기 했고 유클리디안 거리 공식은 "L2 Distance"라고도 한다고 이야기 했었죠.

그럼 여기서 "Lm Distance"라는 것에 대해 알아보도록 하겠습니다. (이때 m은 숫자입니다.)

"Lm Distance"를 "Minkowski distance(민코우스키 거리)"라고도 합니다.

공식은 다음과 같습니다.

위의 식에서 m이 1이면 맨하탄 거리 공식과 같아지고 m이 2가 되면 유클리디안 거리 공식과 같아진다는 것입니다.

이런 점을 이용해서 m을 3이나 그 이상으로 늘려서 거리를 재는 또 다른 척도로 사용할 수 있다는 것 입니다. (그것이 기하학적으로 어떤 의미를 갖는지는 잘 몰라도...)

결국 데이터의 특성에 따라 적당한 거리 구하는 공식을 사용해야 한다는 이야기 입니다. ^^

사용예

우리 동네가 다음과 같이 생겼다고 가정합시다.

H는 우리집이고 A는 빵집, B는 과일가게, C는 철물점입니다.
어머니께서 심부름으로 빵과, 바나나, 망치를 사오라고 하셨다고 하죠.
여기서 질문은 "어떤 경로로 돌아다녀야 제일 힘을 안들이고 심부름을 마칠 수 있을까요?"입니다.

뭐 머리 좋은 분들은 그냥 대충 생각해서 가도 가장 짧은 길을 선택할 수도 있겠지만...
아무튼 맨하탄 거리 계산을 이용하여 한번 계산 해 보도록 하죠.

먼저 각 장소들의 좌표를 정해 보겠습니다.

H = (2, 2)
A = (1, 3)
B = (5, 3)
C = (0, 1)

또한 집에서 출발해서 빵집, 과일가게, 철물점을 모두 돌고 다시 집으로 돌아오는 모든 경우를 적어보도록 하겠습니다.

H -> A -> B -> C -> H

H -> A -> C -> B -> H

H -> B -> A -> C -> H
H -> B -> C -> A -> H
H -> C -> A -> B -> H

H -> C -> B -> A -> H

이제 각 경우를 맨하턴 거리 공식에 의해 계산해 보도록 하죠.

H -> A -> B -> C -> H = (|2-1|+|2-3|) + (|1-5|+|3-3|) + (|5-0|+|3-1|) + (|0-2|+|1-2|) = 2 + 4 + 7 + 3 = 16

이와 같은 방식으로 나머지 것들도 계산을 하면...

H -> A -> C -> B -> H = 2 + 3 + 7 + 4 = 16
H -> B -> A -> C -> H = 4 + 4 + 3 + 3 = 14
H -> B -> C -> A -> H = 4 + 7 + 3 + 2 = 16
H -> C -> A -> B -> H = 3 + 3 + 4 + 4 = 14
H -> C -> B -> A -> H = 3 + 7 + 4 + 2 = 16

이와 같은 결과로 아래 그림의 녹색선을 따라 "H -> B -> A -> C -> H" 혹은 "H -> C -> B -> A -> H" 순으로 돌아다니면 되겠네요. 집에서 제일 가깝다고 A(빵집) 부터 가면 대략 난감입니다. ㅠㅠ

여기서 계산한 값 자체가 길까지 알려 주진 않습니다.

즉, 각 사거리 마다 어떤 길을 선택할 것인지에 대한 이야기는 아니며 어떤 순서로 가야지만 가장 최선인지만을 알 수 있습니다.

다 설명하고 나니 쫌 시시하죠?

하지만 단순 2차원의 문제로 생각하지 마시고 이런 식의 문제가 다차원 공간에서 계산되어야 한다고 생각하면 이러한 공식이 있음이 참 다행이라고 생각되어지지 않을까요?

548 view

4.0 stars

SSISO Community