바로가기 메뉴
본문 바로가기
대메뉴 바로가기

TECH M

토박이vs.컴퓨터, 길 찾기 대결 승자는?

길 탐색 최적화 알고리즘

2016-04-12조은아 기자


지도 앱은 사람들의 일상에 시나브로 파고들었다.
스마트폰이 보급되고 지도 앱이 동네 토박이만큼 정확한 길을 안내하기 시작하면서 자리 잡은 현상이다.

실시간 교통 정보까지 반영되면서 점점 더 똑똑해지고 있는 지도 앱의 원리는 최근 화제가 된 알파고의 바둑 알고리즘과 닮았다. 수많은 바둑 기보를 참고해 승률이 높은 최적의 수를 찾는 알파고처럼 주어진 가중치 그래프에서 최적화된 길을 찾는다. 출발점부터 도착점까지의 수많은 지점들을 연결한 선(도로)을 바탕으로 거리, 시간, 길의 상태 등을 수치화한 값에 가중치를 주는 것.

최단거리를 찾고자 한다면, 그래프의 가중치를 ‘거리’로 해야 할 것이다. 가장 먼저 꺾어지는 길을 택하거나 가장 꺾어지는 횟수가 적은 길을 보여주는 식이다. 여기에 실시간 교통정보, 고속도로 우선 등의 옵션을 추가해 교정된 소요시간을 따져 최단거리 경로를 산출하게 된다.

그렇다면 샛길까지 빠삭한 동네 토박이와 컴퓨터 기반 지도 앱 중 누가 더 정확하고 빠른 답을 내놓을까.
결론부터 말하면, 컴퓨터다.

나현숙 숭실대 컴퓨터학부 교수는 “길 찾기 문제는 바둑 대국보다 더 쉬운 문제”라며 “출발점에서 도착점까지 가중치의 합이 최소가 되는 알고리즘은 매우 많이, 잘 개발된 상태로 두 번째 짧은 길, K번째 짧은 길 모두 정확하게 찾을 수 있다”고 설명했다.

그럼에도 불구하고 알고리즘을 이용한 지도 앱이 사람을 100% 만족시키는 결과를 내놓지 못하는 이유는 뭘까.

시간별로 상황이 바뀌기 때문이다. 교통에는 돌발 변수가 많아 최적화된 길을 출력하는 데 어려움이 많다. 게다가 사람마다 선호하는 길이 다른데, 내비게이션 알고리즘은 개인별 선호도를 모두 반영하기는 어렵다. 사람들은 최단 거리, 고속도로 우선, 무료 도로 등의 요소에 대해 항상 우선시하는 것이 아니라 때에 따라 요소들의 적당한 조합을 찾기 때문. 이용자는 거리와 시간은 최적 값의 1.2배 정도 수용할 수 있고, 요금은 4000원까지 더 낼 수 있는 등 선호하는 길이 있지만 현재 내비게이션은 일반적인 기호를 감안한 결과를 보여준다.

나 교수는 “사람마다 다른 선호도를 반영한 ‘가중치’의 그래프(도로지도)를 개발하고 제공하느냐는 고려할 요소가 많은 문제”라며 “최근 ‘추천경로’ 옵션이 사용자 선호도를 반영하는 시도를 한 알고리즘”이라고 설명했다.

<본 기사는 테크M 제36호(2016년4월) 기사입니다>