한국정보통신학회 논문지 (Journal of the Korea Institute of Information and Communication Engineering)
Current Result Document :
| 한글제목(Korean Title) |
추상 그래프를 활용한 경로 탐색 알고리즘의 구현 및 성능 평가 |
| 영문제목(English Title) |
Implementation and Evaluation of Path-Finding Algorithm using Abstract Graphs |
| 저자(Author) |
김지수
이지완
조대수
Ji-Soo Kim
Ji-wan Lee
Dae-Soo Cho
|
| 원문수록처(Citation) |
VOL 13 NO. 11 PP. 2367 ~ 2372 (2009. 11) |
한글내용
(Korean Abstract) |
최근 단말기 기반의 경로 탐색에서도 동적인 정보를 반영하기 위한 연구가 진행되고 있다. 제시하는 대부분의 알고리즘은 A알고리즘을 기반으로 한다. 휴리스틱을 이용한 알고리즘에서는 탐색 비용이 증가하는 문제가 발생할 수 있다. 추상 그래프는 실제 도로 네트워크를 단순화한 그래프로, 휴리스틱의 의존성과 탐색 비용을 줄이기 위해 제안된 방법이다. 이 논문에서는 생성 방법이 다른 두 가지의 추상 그래프를 이용하여 성능 평가 하였다. 추상 그래프는 생성 방법에 따라 동일 특성 노드 합병을 통한 추상 그래프(AGH)와 연결 노드 합병을 통한 추상 그래프(AGC)로 구별된다. 성능 실험 결과 생성 비용과 노드 접근 비용 측면에서 AGC가 좋은 성능을 보였지만, 탐색된 경로의 이동시간 측면에서는 AGH가 좋은 성능을 보였다.
|
영문내용
(English Abstract) |
Recently, Many studies have been progressing to path-finding adapted dynamic information on the Terminal Based Navigation System(TBNS). The algorithms proposed are based on A algorithm. Path-finding algorithms which use heuristic function may occur a problem of the increase of exploring cost. Path-finding with an abstract graph which expresses real road network as a simple graph is proposed for reducing dependency of heuristic and exploring cost. In this paper, two abstract graph that are different method of construction, Homogeneous Node merging(AGH) and Connected Node Merging(AGC), are implemented. In result of evaluation of performance, AGC has better performance than AGH at construction cost and the number of node access but AGC has worse performance than AGH at exploring cost.
|
| 키워드(Keyword) |
동적 휴리스틱
탐색 영역 가지치기
A 알고리즘
추상 그래프
Dynamic Heuristic
Pruning Search Space
A Algorithm
Abstract Graph
|
| 파일첨부 |
PDF 다운로드
|
