- 탐색 영역 확장 기법들을 활용한 추상 그래프 기반의 탐색 알고리즘 성능 개선
- ㆍ 저자명
- 조대수,Cho. Dae-Soo
- ㆍ 간행물명
- 한국해양정보통신학회논문지
- ㆍ 권/호정보
- 2011년|15권 1호|pp.157-162 (6 pages)
- ㆍ 발행정보
- 한국정보통신학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
이 논문에서는 추상 그래프 기반의 경로 탐색 알고리즘에서 탐색된 경로의 비용이 증가하는 문제점을 보완하기 위해 탐색 영역 확장 기법들을 제안한다. 제안하는 기법들은 버퍼링 셀을 추출하여 유효 셀과 함께 탐색 영역으로 설정하는 기법으로, 단순 버퍼링 기법, 속력 제한 버퍼링 기법, 거리제한 버퍼링 기법을 제안하고 성능 평가하였다. 단순 버퍼링 기법은 유효 셀의 인접 셀들을 버퍼링 셀로 추출하며, 속력 제한 버퍼링 기법과 거리 제한 버퍼링 기법은 단순 버퍼링 기법을 통해 추출된 버퍼링 셀을 속력과 거리에 대해 제한하여 임계값을 미치지 못하는 버퍼링 셀을 제외하는 기법이다. 성능 평가 결과 탐색 영역을 확장함으로써 탐색된 경로의 비용을 줄일 수 있었다. 제안한 기법은 경로탐색, 물류관리 등 텔레매틱스 응용 서비스의 개발에 활용될 수 있을 것으로 기대된다.
In this paper, we propose enhanced methods of path finding based on an abstract graph with extension of search space to improve the quality of path. The proposed methods that are called simple buffering method, velocity constrained method and distance constrained method are to extract buffering-cells for using search space with valid-cells. The simple buffering method is to extract adjacent cells of valid-cells as buffering-cells. velocity constrained method and distance constrained method are based on simple buffering method, these eliminate buffering-cells through each of threshold. In experiment, proposed methods can improve the quality of path. The proposed methods are applicable to develop various kinds of telematics application, such as path finding and logistics.