선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
가설 설정
- 여기서 실험을 간단하게 하기 위하여 노드와 노드 사이의 거리는 모두 ‘1’로 가정하였다.
제안 방법
- 특히 Dijkstra의 알고리즘과 A* 알고리즘이 별도의 Open 리스트를 사용하는 방법으로 Open 리스트의 무분별한 증가를 방지하여 비교횟수(연산비용)를 줄였다. 또한 Dijkstra의 알고리즘으로 최단거리 경로를 탐색하기 때문에 A* 알고리즘만으론 찾을 수 없는 경로를 찾을 수 있도록 하였다.
- 먼저 실제의 도로 정보와 비슷한 환경을 구축하여 실험하였다. 시뮬레이션 화면은 크게 탐색경로를 나타내는 화면영역은 최대 1600(40x40)개의 노드(경로와 경로가 만나는 교차로)를 표기할 수 있도록 하였고, 시작지점(S)를 출발하여 목적지점(E)에 도착하는 최단거리 경로를 탐색하는 실험환경을 설정하였다.
- 이 장에서는 하이브리드 알고리즘의 최단거리 경로 탐색에 대한 컴퓨터 시뮬레이션 내용을 설명한다. 먼저, 시뮬레이션 환경과 두 가지 지도 데이터(인공지도 및 실세계 지도 데이터)를 기반으로 실험 결과를 제시한다. 먼저, 인공지도 데이터를 이용하여 레벨 값(I)에 따른 연산비용을 측정한 결과를 고찰한 다음, 실제 지도 데이터를 이용한 탐색결과와 연산비용을 고찰한다.
- 먼저, 시뮬레이션 환경과 두 가지 지도 데이터(인공지도 및 실세계 지도 데이터)를 기반으로 실험 결과를 제시한다. 먼저, 인공지도 데이터를 이용하여 레벨 값(I)에 따른 연산비용을 측정한 결과를 고찰한 다음, 실제 지도 데이터를 이용한 탐색결과와 연산비용을 고찰한다.
- 본 논문의 하이브리드 검색에서는 먼저 Dijkstra의 알고리즘으로 최단거리가 될 수 있는 경로들을 찾아 Open 리스트를 구성한 후, 탐색 알고리즘을 A* 알고리즘을 교체한다. 즉, Dijkstra의 알고리즘 Open 리스트에 있는 노드들의 적합도를 (A* 알고리즘의 휴리스틱 경험치(h)를 이용하여) 새롭게 측정하여 가능성이 높은 노드들만을 남긴 후(A* 알고리즘의 Open 리스트에 저장한 후) Open 리스트의 내용을 모두 삭제하여(Dijkstra의 알고리즘을 새롭게 시작하여) Open 리스트의 크기가 급격히 증가하는 것을 방지한다.
- 먼저 실제의 도로 정보와 비슷한 환경을 구축하여 실험하였다. 시뮬레이션 화면은 크게 탐색경로를 나타내는 화면영역은 최대 1600(40x40)개의 노드(경로와 경로가 만나는 교차로)를 표기할 수 있도록 하였고, 시작지점(S)를 출발하여 목적지점(E)에 도착하는 최단거리 경로를 탐색하는 실험환경을 설정하였다. 여기서 실험을 간단하게 하기 위하여 노드와 노드 사이의 거리는 모두 ‘1’로 가정하였다.
- 앞 장에서 고찰한 기존의 개선된 탐색법이 동기가 되어, 본 논문에서는 Dijkstra와 A* 알고리즘을 하이브리드시킨 탐색알고리즘을 제안한다. 두 알고리즘을 교체하기 위하여 새 파라미터 Level을 정의한다.
- 이 문제를 해결하기 위하여 본 논문에서는 완전탐색 알고리즘의 하나인 Dijkstra의 알고리즘을 기본 탐색방식으로 사용하면서 선택적 알고리즘인 A* 알고리즘의 기법을 활용하는 하이브리드 탐색을 검토하였다.
- 따라서 A*에 기반한 알고리즘의 검색시간을 줄이기 위해선 A* 알고리즘의 Open 리스트 크기를 작게 하여야 하나 이는 탐색효율을 저하시키는(잘못된 경험규칙을 적용하여 탐색에 실패하는) 원인이 되기도 한다. 이 문제를 해결하기 위해서 본 논문에서는 Dijkstra와 A* 알고리즘을 하이브리드시키는 방법[12～13]을 확장 검토한다.
- 이 지도 데이터를 대상으로 Dijkstra, A*, LRTA*, Di-dir 알고리즘 및 하이브리드 알고리즘을 적용하여 최단거리 경로탐색을 수행하였고, 탐색결과를 기반으로 경로거리와 연산비용을 비교 분석하였다.
- 또한, 표 2에서 사용한 탐색 알고리즘은 Dijkstra, A*, LRTA*, Bi-dir 및 하이브리드 알고리즘이다. 특히 양방향 검색이 가능한 Bi-dir 알고리즘은 DD, AA, DA, AD 네 가지로 분류하여 실험하였다. 여기서 DD는 양방향 모두 Dijkstra를, AA는 양방향 모두 A* 알고리즘을 적용한 탐색이다.
대상 데이터
- 제안 알고리즘을 평가하기 위해 1600(40 × 40)개 노드의 인공 지도 데이터와 정부에서 제공한 지능형교통시스템용 전자도로망 지도 데이터를 사용하였다.
- 지능형교통시스템(ITS: Intelligent Transportation Systems)용 전자도로망 지도 데이터들을 이용하며, 서울, 부산, 대전, 대구, 경기도, 그리고 강원도 지역 데이터를 통한 경로 탐색을 실험한다. 표 1은 ITS에서 제공한 지도 데이터 중에서 서울, 부산, 대전, 대구, 경기도, 그리고 강원도 지역에 대한 노드와 링크의 수를 파악한 것이다.
이론/모형
- 즉, S에서 세 번째의 이웃 노드까지만 Dijkstra알고리즘으로 탐색한 후, A* 알고리즘으로 전환하게 된다. A* 알고리즘에 의해서 선정된 노드의 적합도를 평가한 다음 다시 Dijkstra 알고리즘을 적용하여 탐색한다.
- 차량용 내비게이션은 차량의 위치를 파악하기 위해 GPS(Global Positioning System)[1]를 활용한다. 국내 내비게이션에서 사용하는 운전자용 DB에는 180만개의 링크를 이용한다.
- 표 2의 경로거리에서 최단 경로 (진하게 표시한 수)를 찾아낸 알고리즘은 Dijkstra와 Bi-dir(DD)이며, 그 다음 짧은 경로를 찾은 알고리즘은 하이브리드 알고리즘이다. 이 결과로부터 하이브리드 알고리즘이 기존 A*에 비해 더 짧은 최단 경로를 찾을 수 있음을 알 수 있다.
성능/효과
- (3) 선택 노드 m이 목적노드인 경우 성공종료하고, DO가 공백 리스트인 경우 실패종료한다.
- 이와 같은 결과는 그림 4 (a), (b), (c)의 결과로부터도 관찰할 수 있다. 그림 5 (b)의 결과로부터 최단거리 경로탐색을 수행한 연산비용은 path1, path2, path3의 모든 경로에 대하여 제안 알고리즘이 다른 알고리즘보다 우수함(높이가 낮음)을 알 수 있다. 이와 같은 고찰로부터 하이브리드 알고리즘이 일반적으로 다른 알고리즘에 비해 연산비용 면에서 더 우수함을 알 수 있다.
- 즉, 표 2의 실험 은 간단한 실험을 위해 하이브리드 알고리즘의 경우 L15를 공통으로 사용하였다. 그런데 실험 결과, 제안된 하이브리드 알고리즘의 성능(연산비용)은 Level 값에 민감하였음을 보였다. 따라서 주어진 도로환경에 하이브리드 알고리즘을 효율적으로 적용하기 위해선 최적의 Level 값을 선정하여야 한다.
- 기존의 A*에 기반한 알고리즘에서 경험치(h)를 달리 사용하여 Dijkstra의 알고리즘 보다 연산비용(방문한 탐색공간의 크기)을 줄일 수 있다 (즉 Open 리스트의 길이를 줄일 수 있다).
- 이 지도 데이터를 대상으로 Dijkstra, A*, LRTA*, Di-dir 알고리즘 및 하이브리드 알고리즘을 적용하여 최단거리 경로탐색을 수행하였고, 탐색결과를 기반으로 경로거리와 연산비용을 비교 분석하였다. 본 시뮬레이션 결과로부터 제안된 하이브리드 알고리즘의 탐색 경로가 Dijkstra 알고리즘과 비슷한 결과를 보였으며, 연산비용은 A*와 비슷한 결과를 나타내었다. 그러나 제안 알고리즘의 성능(경로거리 및 연산비용)은 Level 값에 민감하였다.
- 세 종류 하이브리드 알고리즘으로 최단거리경로를 탐색한 결과, 탐색공간이 Level 값에 따라 차이가 있음을 알 수 있다.
- 실험 결과, 제안한 방법으로 기존의 Dijkstra, A*, LRTA*, Bi-directional (Bi-dir) 알고리즘 보다 연산이 감소할 수 있음을 보이고, A* 알고리즘만으론 찾을 수 없는 경로를 찾을 수 있음을 보인다. 즉, 기존 Dijkstra 수준의 최단거리 경로를 A* 보다 적은 탐색비용으로 탐색을 할 수 있음을 보인다.
- 표 2의 경로거리에서 최단 경로 (진하게 표시한 수)를 찾아낸 알고리즘은 Dijkstra와 Bi-dir(DD)이며, 그 다음 짧은 경로를 찾은 알고리즘은 하이브리드 알고리즘이다. 이 결과로부터 하이브리드 알고리즘이 기존 A*에 비해 더 짧은 최단 경로를 찾을 수 있음을 알 수 있다. 반면에 가장 적은 연산비용의 알고리즘은 일반적으로 Bi-dir(AA)이며, 그 다음이 하이브리드 알고리즘이다.
- 그리고 L4이후 연산비용이 소폭 증가함을 알 수 있다. 이상의 고찰로부터 L4의 하이브리드 탐색을 수행하면 연산비용(비교횟수)을 가장 효과적으로 줄일 수 있음을 알 수 있다.
- 본 논문의 하이브리드 검색에서는 먼저 Dijkstra의 알고리즘으로 최단거리가 될 수 있는 경로들을 찾아 Open 리스트를 구성한 후, 탐색 알고리즘을 A* 알고리즘을 교체한다. 즉, Dijkstra의 알고리즘 Open 리스트에 있는 노드들의 적합도를 (A* 알고리즘의 휴리스틱 경험치(h)를 이용하여) 새롭게 측정하여 가능성이 높은 노드들만을 남긴 후(A* 알고리즘의 Open 리스트에 저장한 후) Open 리스트의 내용을 모두 삭제하여(Dijkstra의 알고리즘을 새롭게 시작하여) Open 리스트의 크기가 급격히 증가하는 것을 방지한다.
- 실험 결과, 제안한 방법으로 기존의 Dijkstra, A*, LRTA*, Bi-directional (Bi-dir) 알고리즘 보다 연산이 감소할 수 있음을 보이고, A* 알고리즘만으론 찾을 수 없는 경로를 찾을 수 있음을 보인다. 즉, 기존 Dijkstra 수준의 최단거리 경로를 A* 보다 적은 탐색비용으로 탐색을 할 수 있음을 보인다. 이하, 제 Ⅱ장에서는 기존의 탐색 알고리즘을 이용한 경로탐색을 설명한다.
- 반면에 가장 적은 연산비용의 알고리즘은 일반적으로 Bi-dir(AA)이며, 그 다음이 하이브리드 알고리즘이다. 즉, 최단 경로거리 탐색은 연산비용이 증가하고, 연산비용의 최소화는 경로거리의 증가로 연결됨을 알 수 있다. 따라서 Dijkstra, Bi-dir(DD), Bi-dir(AA) 등은 경로거리와 연산비용의 두 평가기준을 모두 만족시키기 어렵다.
- 이 문제를 해결하기 위하여 본 논문에서는 완전탐색 알고리즘의 하나인 Dijkstra의 알고리즘을 기본 탐색방식으로 사용하면서 선택적 알고리즘인 A* 알고리즘의 기법을 활용하는 하이브리드 탐색을 검토하였다. 특히 Dijkstra의 알고리즘과 A* 알고리즘이 별도의 Open 리스트를 사용하는 방법으로 Open 리스트의 무분별한 증가를 방지하여 비교횟수(연산비용)를 줄였다. 또한 Dijkstra의 알고리즘으로 최단거리 경로를 탐색하기 때문에 A* 알고리즘만으론 찾을 수 없는 경로를 찾을 수 있도록 하였다.
후속연구
- 즉, 성능은 Level 값이 증가할수록 Dijkstra 알고리즘에 근접하고, 작아질수록 A* 알고리즘에 접근하였다. 따라서 시작지점과 목적지점간 사이의 거리 및 지역특성에 따른 최적의 Level 값을 자동으로 결정하기 위한 추가적인 연구가 필요하다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.