해시넷
최단경로
최단경로는 출발지에서 목적지까지 가는 가장 짧은 길을 말한다.
내비게이션 최단경로 찾는 방법[편집]
내비게이션이 빠른 길을 찾는 것에는 '최단경로 탐색 알고리즘'이 사용된다. 최단경로 탐색 알고리즘은 여러 종류가 있는데, 내비게이션에서 가장 많이 쓰이는 것은 '다익스트라 알고리즘'이다.
컴퓨터 과학에서 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허르 데이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다.
- 알고리즘
시작할 꼭짓점은 초기점으로, 꼭짓점 Y의 거리를 초기점에서 Y까지의 거리로 정의한다. 다익스트라 알고리즘은 초기 거리 값을 부여하고, 단계를 거듭하며 개선시킬 것이며, 이 개선시키는 것을 간선 완화(edge relaxation)이라고 한다.
- 모든 꼭짓점을 미방문 상태로 표시한다. 미방문 집합이라는 모든 미방문 꼭짓점의 집합을 만든다.
- 모든 꼭짓점에 시험적 거리 값을 부여한다: 초기점을 0으로, 다른 모든 꼭짓점을 무한대로 설정한다. 초기점을 현재 위치로 설정한다.
- 현재 꼭짓점에서 미방문 인접 꼭짓점을 찾아 그 시험적 거리를 현재 꼭짓점에서 계산한다. 새로 계산한 시험적 거리를 현재 부여된 값과 비교해서 더 작은 값을 넣는다. 예를 들어, 현재 꼭짓점 A의 거리가 6이라고 표시되었고, 인접 꼭짓점 B로 연결되는 변의 길이가 2라고 한다면, A를 통한 B까지의 거리는 6+2=8이 된다. 이전의 B까지의 거리가 8보다 컸다면 8로 바꾸고, 그렇지 않다면 그대로 놔둔다.
- 만약 현재 꼭짓점에 인접한 모든 미방문 꼭짓점까지의 거리를 계산했다면, 현재 꼭짓점을 방문한 것으로 표시하고 미방문 집합에서 제거한다. 방문한 꼭짓점은 이후에는 다시 방문하지 않는다.
- 두 꼭짓점 사이의 경로를 찾는 경우: 도착점이 방문한 상태로 표시되면 멈추고 알고리듬을 종료한다.
- 완전 순회 경로를 찾는 경우: 미방문 집합에 있는 꼭짓점들의 시험적 거리 중 최솟값이 무한대이면 이는 출발점과 미방문 집합 사이에 연결이 없는 경우이므로 멈추고 알고리즘을 종료한다.
- 아니면 시험적 거리가 가장 작은 다음 미방문 꼭짓점을 새로운 '현재 위치'로 선택하고 3단계로 되돌아간다.
경로를 계획하고 있을 때, 사실은 위에서 했던 것처럼 도착점이 '방문'한 상태가 될 때까지 기다릴 필요가 없다: 도착점이 '미방문' 꼭짓점들 중 가장 시험적 거리가 작아지면 (그리고 다음 '현재 위치'로 선택될 수 있다면) 알고리즘을 종료할 수 있다.
내비게이션과 다른 선택을 하는 이유[편집]
출발지에서 목적지까지의 최단 거리는 직선이다. 그러나 복잡하게 길이 얽혀 있는 시내를 걸을 때는 일직선으로 가는 게 불가능하다. 이때 컴퓨터 내비게이션은 지도 속 거리를 일일이 계산해 가장 빠른 길을 안내해 준다. 때론 골목골목을 오가는 복잡한 길을 안내하기도 한다. 하지만 인간은 내비게이션과 다른 길로 향하는 경우가 많다. 출발지와 목적지를 왕복할 때 다른 길을 택하기도 한다.
인간이 내비게이션과 다른 선택을 하는 이유가 미국 과학자들에 의해 밝혀졌다. 파올로 산티 미국 매사추세츠공대(MIT) 도시연구 및 계획학부 수석연구원 연구팀은 인간은 경로가 길어지더라도 목적지 방향과 최대한 일치하는 경로를 선택하는 것을 선호한다고 국제학술지 '네이처 계산과학'에 발표했다.
연구팀은 인간의 길찾기 전략을 분석하기 위해 미국 매사추세츠주의 두 도시인 보스턴과 케임브리지 내 보행자 1만 4000명의 이동 경로 55만 개를 기록한 위성위치확인시스템(GPS) 데이터를 분석했다. 분석 결과 보행자는 최단 경로를 선택하는 대신 약간 더 멀어도 목적지와의 각도 편차를 최소화하는 경로를 선택했다. 왼쪽과 오른쪽으로 많이 꺾는 경로가 실제로 더 짧아지더라도 목적지를 직진으로 마주할 수 있는 경로를 선호하는 것으로 나타난 것이다.
이에 대해 산티 수석연구원은 '인간이 길을 찾는 모델이 최단 경로를 찾는 것이 아니라 각도 변위를 최소화하는 것임을 발견했다'고 설명했다. 예를 들어 목적지가 북쪽에 더 가까운 북동쪽에 있다면 갈림길에서 동쪽으로 꺾은 후 북쪽으로 이동하는 것이 거리상 유리하더라도 우선 북쪽으로 이동한다는 것이다. 이후 동쪽으로 더 목적지가 가까워지고 나서야 다시 길을 꺾어 목적지를 찾게 된다.
이러한 경향에 대해 연구팀은 인간이 지도를 정확하게 머릿속에 담을 수 없는 만큼 기준점이나 랜드마크 등 주변에서 얻는 정보를 통해 공간을 탐색하는 방향으로 진화한 것으로 추정했다. 최단 경로를 복잡하게 계산하기보다 두뇌 작업량을 줄여 다른 작업에 더 많은 힘을 할애할 수 있도록 진화했다는 것이다.
연구팀은 주변 지형이나 사물의 위치들보다는 방향을 기준으로 삼는 탐색법이 곤충에서 영장류까지 이르는 동물들에게서 광범위하게 나타난다고 설명했다.
연구팀 라티 교수는 '이 방법은 최단경로를 만들진 않지만 최단경로와 비슷하게 짧으면서도 계산은 매우 간단하다', '스마트폰과 휴대용 전자제품이 점점 인간을 모사한 인공지능(AI)을 결합하고 있다'며 '우리 뇌가 사용하는 계산법과 기계가 사용하는 계산법이 어떻게 차이가 나는지를 더 잘 이해하는 것이 점점 중요해지고 있다'고 말했다.[1]
세일즈맨 최단경로 찾기[편집]
세일즈맨이 물건을 팔기 위해 5개의 도시를 순회하려고 하는데, 하나의 도시는 반드시 한 번만 방문한다고 할 때 최단 경로를 어떻게 찾을 수 있을까? 이는 '세일즈맨 최단 경로 문제'라고 하는 것으로서 동선(動線)의 최적화 문제를 다룰 때마다 약방의 감초격으로 등장한다.
확실한 방법은 모든 경우를 하나씩 비교해보는 것이다. 도시가 5개라면 세일즈맨이 갈 수 있는 경로는 모두 120가지(5!=5×4×3×2×1)가 된다. 이 정도는 하루 정도의 시간과 인내심만 있다면 얼마든지 풀 수 있다.
도시가 25개로 늘어난다면 문제는 심각해진다. 상상을 초월하는 천문학적인 경우의 수(25!)가 나오기 때문이다. 초당 100만 번의 비교가 가능한 슈퍼컴퓨터로도 4900억 년이라는 엄청난 시간이 걸린다. 우주의 나이인 100억 년보다 훨씬 오랜 억겁(億劫)의 시간이 필요하다.
하지만 비즈니스의 세계에서는 포기할 수 없는 일이다. 25개가 아니라 그 이상의 도시가 존재할 때도 최단 경로를 찾아야 하기 때문이다. 100% 만족스러운 답이 이론적으로 힘들다면 60% 혹은 70%만 만족할 수 있는 답이라도 찾아야 한다.
단숨에 답을 찾겠다는 만용을 버리고 무수히 많은 경로 중 가장 짧을 것 같은 두 개의 경로를 먼저 골라내야 한다. 그런 다음 서로 비교해 둘 중에 더 짧은 경로를 택하는 방법을 취하면 된다. 어느 정도 만족할 만한 수준에 도달했다고 판단되면 문제 풀기를 멈춘다. 그것이 최단 경로가 아니라도 말이다. 정해진 기간 내에 25개의 도시를 모두 돌 수 있는 경로인지, 교통비를 감당할 수 있는 수준인지 등을 검토해야 하기 때문이다. 무식해 보이긴 하지만 이 같은 '한 걸음씩' 접근방식이 복잡한 현실의 문제를 푸는 데 최선이다.[2]
동영상[편집]
각주[편집]
- ↑ 조승한 기자, 〈내비게이션 최단 경로 놓고 다른 길 찾는 인간, 이유 찾았다〉, 《동아사이언스》, 2021-10-19
- ↑ 〈세일즈맨의 최단 경로 찾기〉, 《중앙일보》, 2007-05-13
참고자료[편집]
- 〈데이크스트라 알고리즘〉, 《위키백과》
- 조승한 기자, 〈내비게이션 최단 경로 놓고 다른 길 찾는 인간, 이유 찾았다〉, 《동아사이언스》, 2021-10-19
- 〈세일즈맨의 최단 경로 찾기〉, 《중앙일보》, 2007-05-13
같이 보기[편집]
