2008년 추계학술대회
Current Result Document :
| 한글제목(Korean Title) |
탐색 영역 추출을 위한 추상 그래프 탐색 알고리즘 설계 |
| 영문제목(English Title) |
A Path-Finding Algorithm on an Abstract Graph for Extracting Estimated Search Space |
| 저자(Author) |
김지수
이지완
문대진
조대수
Ji-Soo Kim
Ji-Wan Lee
Dae-Jin Moon
Dae-Soo Cho
|
| 원문수록처(Citation) |
VOL 12 NO. 02 PP. 0147 ~ 0150 (2008. 10) |
한글내용
(Korean Abstract) |
실제 전체 도로망을 하나의 그리드로 간주하며, 그리드는 여러 개의 고정된 셀로 나누어진다. 경로 탐색 기법은 2단계 탐색으로 나누어진다. 1차 탐색은 실제 도로 네트워크와 고정 셀로부터 생성된 가상 정점과 가상 간선으로 이루어진 추상 그래프에서 우선 탐색한다. 추상 그래프에서 탐색된 가상 경로를 포함하고 있는 영역을 유효 셀이라 하며, 2차 탐색은 추상 그래프에서 제공하는 유효 셀 내에서 A* 알고리즘 탐색을 한다. 즉, 유효 셀을 제외한 무효 셀을 제거함으로서 탐색 비용을 줄일 가능성이 있다. 이 논문에서는 추상 그래프 생성 방법과 탐색 영역 추출을 위한 추상 그래프 경로탐색 알고리즘을 제안한다.
|
영문내용
(English Abstract) |
The real road network is regarded as a grid, and the grid is divided by fixed-sized cells. The path-finding is composed of two step searching. First searching travels on the abstract graph which is composed of a set of psuedo vertexes and a set of psuedo edges that are created by real road network and fixed-sized cells. The result of the first searching is a psuedo path which is composed of a set of selected psuedo edges. The cells intersected with the psuedo path are called as valid cells. The second searching travels with A* algorithm on valid cells. As pruning search space by removing the invalid cells, it would be possible to reduce the cost of exploring on real road network. In this paper, we present the method of creating the abstract graph and propose a path-finding algorithm on the abstract graph for extracting search space before traveling on real road network.
|
| 키워드(Keyword) |
추상 그래프
탐색 영역 추출
A* 알고리즘
|
| 파일첨부 |
PDF 다운로드
|
