Ⅰ서 론

최단경로 탐색 알고리즘은 그래프 알고리즘에서 비롯하여 그래프상의 노드와 링크의 정보를 이용하 여 경로를 찾아내는 기본적인 알고리즘으로, 교통 공학분야에서는 Dijkstra 알고리즘[1]을 기초로 하여 지금까지 적용되어 오고 있다. 그러나 Dijkstra 알고 리즘은 하나의 노드에서 모든 다른 노드로 가는 최단경로를 정확히 찾아내는 장점을 가지는 반면, 대규모 네트워크에서는 탐색소요시간이 길어지는 약점을 가진다.

즉, Dijkstra 알고리즘은 네트워크를 구성하고 있 는 노드에 대해, 출발노드에서 가장 빠른 경로를 모 든 가능한 경로와의 비교를 통하여 구축하고, 최단 경로가 구축된 경로 중에서 목적노드가 존재하면 탐색을 종료하기 때문에 각 노드의 방향성 등을 전 혀 고려하지 않아 최단경로 탐색시간이 길게 된다.

지능형교통체계(ITS) 분야에서 도로망에서 신속 하게 주행 경로 안내를 위한 연구가 활발하게 진행 되면서, 대규모 도로망에 대한 경로 탐색에 그대로 적용하기 힘들기 때문에 이러한 실제적인 문제들을 반영한 효율적인 최단경로탐색 알고리즘 개발에 관 심이 높아지고 있다.

이제까지 Dijkstra 알고리즘의 약점개선을 위한 연 구들은 크게 3가지 접근방법에 의해서 많이 진행되 어 왔다. 구체적으로는 첫째, 출발노드와 목적노드 에서 양방향으로 최단경로를 탐색하는 양방향 탐색 법(Bidirectional Search), 둘째로 정확한 최단경로의 구축이 아니라 적정 수준에서의 최단경로 구축을 목 적으로 하는 휴리스틱 탐색법(Heuristic Search), 셋째 로 출발노드와 목적노드가 멀리 떨어진 경우 주로 사용하는 네트워크 계층구분법(Hierarchical Methods) 등 이다[2,3,4].

이들 세 가지 방법 가운데 어떤 방법이 가장 우 수하다고 단정하기에는 다소 어려움이 있는데, 그 이유는 네트워크의 규모 및 혼잡정도, 출발지와 목 적지간의 위치관계, 가로 부하량의 변화 정도에 따 라 최적의 최단경로 탐색방안이 달라질 수 있기 때 문이다[5].

이러한 개선을 위한 세 가지 방법 중 탐색속도 개선에 초점을 두고 AI(Artificial Intelligent)분야에서 시작된 휴리스틱 탐색법(Heuristic Search)은 규칙적 인 가로망을 대상으로 할 때, 속도만이 아니라 탐색 의 정확도도 가지는 알고리즘으로 부각되었는데, 대표적 알고리즘이 A^*알고리즘이다.

A^* 알고리즘은 식(1)과 같은 평가함수를 기본으 로 한다[8].

g(n) : 출발노드에서 n노드까지의 부하량

h(n) : n노드에서 목적노드까지의 추정 부하량

휴리스틱 값인 h(n)은 통상 목표노드까지의 직 선거리를 많이 적용하고 있는데, h(n) 값의 범위가 실제 부하량 범위에 근접되어야 효율성을 가지게 된다.

그리고 불규칙하고 복잡한 네트워크, 즉, 추정부 하량(h(n) )과 실제 부하량이 비례관계에 있지 못할 경우에는 실패할 확률이 높아지는 단점을 가진다 [4]. 이와 같이 평가함수에서 h(n)이 복잡한 네트 워크의 실제 부하량을 제대로 반영할 수 없기 때문 에 실패확률이 높아지기 마련이다.

따라서 기존 알고리즘의 문제점(약점)을 찾아 이 를 개선하거나 빠른 탐색과 높은 정확성을 가지는 최단경로 탐색 알고리즘 개발하는 것이 필요하다.

이를 배경으로, 본 연구에서는 복잡한 네트워크 에서 기존 A^* 알고리즘의 추정 부하량(h(n) )의 탐 색실패 요인을 규명하고, 실패확률을 줄이기 위한 평가함수 및 개선된 평가함수를 적용하는 알고리즘 을 개발하고자 한다.

ⅡA* 알고리즘의 평가함수 연구 고찰

현재까지 A^* 알고리즘 개선을 위한 연구는 지속 적으로 진행되고 있으며, 연구방향을 크게 분류하 면 평가함수 개선에 관한 연구와 반복 알고리즘 적 용에 관한 연구로 구분할 수 있다.

본 연구에서 목적으로 하는 평가함수 개선에 관 한 대표적 연구는 Fu(2006)의 연구[3]를 들 수 있다.

Fu(2006)는 추정 한계 값을 설정하여 평가함수를 개선하는 방법을 제안하였는데, 평가함수 값이 추 정 한계 값을 초과할 경우 탐색을 하지 않도록 하 였다. 다음 식 (2), 식 (3)과 같이 나타낼 수 있다.

E(_o,d) : 출발노드에서 목적노드까지의 최소 소요 시간(부하량) 추정 한계값

K : 조정계수

이 제안에서 강조한 특성은 조정계수 K로 반복 적용토록 하여 실패 확률을 줄이도록 하였다. 결국 이 방법을 적용하여 분석한 결과 정확성이 높아지 는 장점을 가지나, 탐색 소요시간이 증가되는 단점 을 가지게 된다[6].

또한 Fu(2006)는 추정 부하량(h(n) )을 수정하는 것을 제안하였는데, 일반적으로 직선거리를 사용하 는 것을, 직선거리를 네트워크의 평균속도로 나누 어 적용하는 방법을 제안하였다.

S(n) : n노드에서 목적노드까지의 직선거리

V : 네트워크에서의 평균속도

Ryu(2013)는 최소 가로 부하량 원단위를 이용하 여 추정 부하량을 실제 부하량에 근접시키는 방법 을 개발하였다[6].

emw(n) : 탐색노드(n)에서~목적노드(en)까지 최소 기대 부하량

Ecu_Dis [n] [en] : 탐색노드(n)에서~목적노드 (en)까지 직선거리

Min_Weight_Unit : 최소 가로부하량 원단위 이 방법은 기존 A^* 알고리즘을 적용하는 경우 보 다, 정확도가 높아지고, 실패확률은 감소하지만 탐 색소요시간은 길어지는 단점을 갖고 있다.

ⅢA* 알고리즘의 적용상 취약점

A^* 알고리즘의 적용상 약점은 피드백(feed back) 기능이 없어 실패확률이 높다는 것으로, 최단경로 가 아닌 경로를 최단경로로 결정하거나, 어떠한 경 로도 탐색하지 못하고, 종료되는 경우가 있다는 것 이다.

다음으로는 평가함수의 약점으로 출발 노드에서 탐색 노드(진행된 노드)까지의 실제 부하량이 목표 노드까지 많이 진행되어 큰 경우에 선택되지 못하 고, 출발노드에서 탐색노드까지의 실제 부하량이 작으면서, 목표 노드까지는 더 멀리 떨어진 노드가 쉽게 선택되어질 가능성이 높다는 것이다.

즉, 평가함수가 진행된 부하량과 목표 노드까지 의 추정 부하량 합이 최소가 되는 노드를 선택하기 때문에 단순하고 규칙적이지 않은 네트워크에서는 성공확률이 낮은 노드를 쉽게 선택할 수 있다는 것 이다. 이러한 경우를 <그림 1>에서 다시 구체적으 로 설명하였다.

다음 <그림 1>의 예에서 나타낸바와 같이 출발 노드에서 A노드까지의 실제 부하량은 60, B노드까 지의 실제 부하량은 30이다. 그리고 A노드에서 목 표 노드까지 추정 부하량(휴리스틱 값, 직선거리)은 10, B노드에서 목표 노드까지의 추정 부하량이 30 으로 계산 되었다면, A노드의 평가함수 값은 70, B 노드의 평가함수 값은 60이기 때문에 목표노드에서 더욱 떨어진 B노드를 선택하면서 진행하게 된다.

물론 B노드가 최단경로를 구성할 확률이 없는 것은 아니나, 비효율적인 탐색 가능성이 높은 약점 이 있다. 그리고 목표 노드를 만나면 탐색을 종료시 키므로, 최단 경로가 아닌 경로를 최단경로로 결정 하는 위험성이 있다.

이와 같이 A^* 알고리즘의 평가함수 개선을 위한 기존 연구들은 기본적인 A^* 알고리즘의 추정 부하 량(h(n) )의 산정 방법 변화에만 국한되어 있음으로 써, A^* 알고리즘의 기본적인 취약점을 개선하는데 다소 어려움이 있다. 따라서 본 연구에서는 탐색노 드의 출발노드 및 도착노드와의 위치관계를 적용하 여 취약점을 개선하고자 한다.

Ⅳ평가함수의 개선

평가함수의 개선은 기본 평가함수의 개념을 바 꾸는 것으로, 기존 A^* 알고리즘의 개념은 “지나온 부하량과 앞으로 남은 추정 부하량의 합이 최소인 노드를 선택한다.”인데 이 개념을 “앞으로 남은 추 정 부하량이 최소인 노드를 선택한다.”라는 개념으 로 전환하여 적용한다. 그리고 기존 남은 부하량을 선(線)적으로 계산하였으나, 개선 평가함수에서는 면(面)적으로 계산토록 한다.

부하량의 면(面)적인 계산을 위하여 기대 최단경 로 부하량(exp_SNTN_weight)과 진행 노드 기대 부하량(exp_node_weight)을 적용한다.

기대 최단경로 부하량(exp_SNTN_weight)은 출발 노드(SN )에서 목표 노드(TN )까지 추정하는 부하량을 의미하는 것으로 최초에는 실제의 최단경 로 부하량보다 충분히 큰 임의의 부하량을 설정하 고, 탐색 과정에서 목표 노드(TN )가 발견되면 출발 노드(SN )에서 목표 노드(TN )까지의 부하량 값으로 한다.

진행 노드 기대 부하량은 진행 노드(j)에서 목표 노드(TN )까지의 직선거리(sline (j, TN ) )에 네트워 크 최소 부하량 원단위(min_node_unit) 를 곱한 값이다.

개선된 평가함수의 개념은 <그림 2>와 같고, 계 산은 출발 노드(SN )에서 목표 노드(TN )까지 기대 최단경로 부하량(exp_SNTN_weight)에서 출발 노 드에서 진행 노드까지의 부하량(진행 경로 부하량, g(j))을 뺀 값에 진행노드 기대 부하량 (exp_node_weight)을 곱한 값으로 한다.

여기서 평가함수 계산식을 나타내면 다음 식(6) 과 같다.

개선된 평가함수는 진행된 실제 부하량과 함께 남은 부하량을 면적으로 계산하여 최소값을 가지는 노드를 최단경로 구성노드로 선택한다.

만약, 진행경로 부하량(g(j))이 기대 최단경로 부하량(exp_SNTN_weight) 과 같을 경우에는 진 행경로 부하량에 관계없이 평가함수가 “0”이 되기 때문에 식(7)과 같이 계산한다.

그리고 진행경로 부하량(g(j))과 기대 최단경로 부하량(exp_SNTN_weight) 이 같지는 않으나, 진 행노드 기대부하량(exp_node_weight) 이 “0”인 경우는 식(8)과 같이 계산한다.

새로운 평가함수 계산을 위한 두 개의 변 중에서 하나의 변이 “0”이 된다는 것은 목표노드로의 도달 을 의미하나, 최단경로라는 보장이 없으므로, “0”이 아닌 변의 길이를 2등분하고, 정사각형의 면적을 산정하여 타 노드에서의 평가함수 값과 비교하고 가장 적을 경우 최단경로 구축이 완료되고, 탐색이 종료된다.

Ⅴ새로운 알고리즘의 개발

기존 A^* 알고리즘은 피드백이 없는 극히 단순한 알고리즘으로써, 타 노드까지의 부하량 비교 없이 우선탐색으로 진행됨에 따라 실제 최단경로가 아닌 경로를 최단경로로 인정하거나, 목표노드를 찾지 못하고 종료하는 등 약점이 있었다.

본 연구에서 개선된 평가함수를 적용하는 알고 리즘은 기존 A^* 알고리즘에서와 같이 목표 노드가 탐색되면 탐색종료가 아니라 평가함수 값을 이용하 여 피드백 기능을 보강하였으며, 평가함수 값이 최 소인 노드가 목표노드이면 종료하도록 개선하였다.

여기서 평가함수는 다음 식(6)～식(8)을 적용하여 계산할 수 있으며, 이러한 개선된 평가함수를 이용 하고, 피드백 기능을 보강한 알고리즘은 기존 A^* 알 고리즘에 비해 탐색속도는 다소 저하할 수 있으나, 정확도의 경우 더욱 향상될 것으로 기대한다.

본 연구에서 개선된 알고리즘을 단계별로 정리 하면 다음과 같다.

< 적용변수 >

i /^* 진행단계 ^*/

SN /^* 출발노드 ^*/

TN /^* 목표노드 ^*/

M /^* 네트워크 노드 집합 ^*/

closed{ } /^* 검색된 노드집합 ^*/

chk_val /^* 최소 평가함수 값 ^*/

tem_sp_node[i] /^* i단계 진행노드 ^*/

g_weight[i] /^* i단계 진행경로 부하량 ^*/

weight[i, j] /^* i노드에서 j노드까지의 실 부하량 ^*/

< STEP 0 >

M = {p1, p2, p3, .... pN}

SN, TN 입력

i ⇐ 0,tem_sp_node[i] =SN, g_weight[i] = 0

exp_SNTN_weight = ∽, chk_val =∽

closed[i] = SN

< STEP 1 >

i = i+1

< STEP 2 >

탐색된 노드 집합 closed{ }에 포함되어 있지 않으면서 진행노드에 직접연결된 노드탐색

직접 연결된 노드가 없으면 i = i - 1

< STEP 3 >

i = 0 이면 STEP 6으로 이동

< STEP 4 >

직접 연결된 노드 평가함수 계산

< STEP 5 >

단계별 진행노드 출력(최단경로), g_weight[i] 출력(부하량)

Ⅵ평가함수의 유용성 검증

1검증방법

새로운 평가함수와 알고리즘의 유용성 평가는 실제 네트워크와 실제부하량을 이용하여, A^* 알고 리즘과 Fu의 제안(2006), Ryu(2013)의 연구와 비교 로부터 행하였다. 비교항목은 탐색 속도와 정확성 으로 하였으며, 공정한 비교를 위해 Ryu(2013)의 알 고리즘에서 이용한 실제 네트워크와 자료를 동일하 게 적용하였다.

검증 네트워크는 <그림 3>과 같이 대구광역시 간선가로 네트워크로, 노드 수가 126개, 가로(링크) 수는 213개이며, 최단경로 탐색수는 15750(126×126 –126)개로 하였다.

부하량은 2013년 6월 13일 18시 15분의 가로 통 행시간 값이다. 공정한 속도 비교를 위해서도 Ryu(2013)의 알고리즘에서 이용한 동일한 성능 (CPU 3.09GHz, RAM 2.99GB )의 컴퓨터를 이용하 였다.

2탐색 소요시간

본 연구에서 개발한 알고리즘과 비교대상 알고 리즘의 탐색소요시간 비교결과는 <표 1>에서 나타 내었다.

각 구간별로 비교한 결과, A^* 알고리즘과 Fu의 제안 알고리즘에 비해서 개발한 알고리즘의 탐색속 도는 구간별로 차이는 있으나, 다소 늦는 것으로 나 타났다. 그러나, 기존 개선된 연구 Ryu(2013)의 알 고리즘 보다는 약간 빠른 것으로 나타났다.

이는 피드백 기능에 의한 결과로 사료되며, 네트 워크 최소 가능 원단위를 이용하여 가능경로를 전 부 탐색하는 Ryu(2013)의 알고리즘보다 진행 단계 에서 최소 부하량이 목표노드이면 멈추게 하였기 때문이다. 그리고 개발된 알고리즘이 약간 빠른 것 은 적용 네트워크가 정상 네트워크(규칙적 교차로, 실 거리와 부하량의 비례관계 등)인 영향도 큰 것 으로 판단된다.

3정확성

비교대상 알고리즘과 개발한 알고리즘의 탐색소 요시간 비교결과는 <표 2>에서 나타내었다.

본 연구에서 개발한 알고리즘을 단순히 A^* 알고 리즘과 비교하면, 성공확률을 상당히 높일 수 있다 는 것이 증명되었다. 그리고 가로 최소 원단위와 가 능 경로를 전부 탐색하여 최단경로를 결정하는데 있어서는 정확도가 조금 떨어지나, <표 2>에 나타 낸바와 같이 타 알고리즘에 비해서는 높은 정확도 를 보이고 있다.

Ⅶ결 론

본 연구에서는 A^* 최단경로 탐색 알고리즘의 취 약점을 개선하기 위하여 평가함수 개선 및 피드백 기능을 보강한 알고리즘을 개발하였다.

평가함수는 진행된 거리 최소와 남은 거리 최소 의 적용 개념에서 남은 진행거리 중심으로 바꾸고, 네트워크의 부하량 최소 원단위와 기대 최단경로 부하량을 이용하여 남은거리에서도 진행되어온 거 리의 영향이 효과적으로 반영될 수 있도록 하였다.

알고리즘에서는 목표노드가 탐색되었다고 하여 종료하는 것이 아니라, 다른 노드를 경유하는 것이 더욱 최단경로를 구성할 가능성도 있으므로, 평가 함수 값이 최소인 동시에 목표노드일 경우 탐색을 종료하도록 하였다.

실제 대구광역시 네트워크에서 기존 A^* 알고리 즘 및 기존 A^* 알고리즘 개선 연구들과 최단경로 탐색 비교를 행한 결과, 속도 및 정확성에서 유용성 이 있는 것으로 검증되었다.

탐색속도와 정확성 모두 최상의 결과를 나타내 지는 않았으나, 네트워크 및 부하량 조건에 따라서 최상의 결과 도출도 가능한 것으로 판단된다.

마지막으로 본 연구에서 개발한 평가함수와 알 고리즘은 복잡하고 불규칙적인 네트워크에서 크게 늦지 않은 탐색속도로 A^* 알고리즘 보다 높은 정확 도를 얻기 위해서 유용하게 적용할 수 있을 것으로 판단된다.

향후 타 알고리즘의 결합 등, 최단경로 탐색 속 도를 더욱 증가시킬 수 있는 알고리즘 개선에 관한 연구를 진행할 예정이다.