지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 발행연도
- 2014.7
- 수록면
- 103 - 111 (9page)
이용수
초록· 키워드
오류제보하기
본 논문은 실시간 GPS 항법시스템에서 최단경로 탐색에 일반적으로 적용되고 있는 Dijkstra 알고리즘을 양방향 통행로(무방향그래프)로만 구성된 도로에 적용하고 문제점을 개선한 알고리즘을 제안하였다. Dijkstra 알고리즘은 방향 그래프에서 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단경로를 결정하기 때문에 알고리즘 수행에 많은 메모리가 요구되어 실시간으로 정보를 제공하지 못할 수도 있다. 이러한 문제점을 해결하고자, 본 논문에서는 무방향 그래프에 적합하도록 출발과 목적지 정점을 제외한 경로 정점들에 대해 최단경로를 설정하고, 출발 정점부터 시작하여 정점 유출 간선들에 대해 최단경로 설정 간선들과 일치하는 간선들을 모두 선택하는 방식으로 한 번에 다수의 정점들을 탐색하는 방법을 택하였다. 9개의 다양한 무방향 그래프에 제안된 알고리즘을 적용한 결과 모두 최단경로를 탐색하는데 성공하였다. 또한, 수행 속도 측면에서 Dijkstra 알고리즘보다 약 60%를 단축시키는 효과를 얻었으며, 알고리즘 수행에 필요한 메모리도 월등히 적게 요구되었다.
목차
등록된 정보가 없습니다.
참고문헌 (0)
참고문헌 신청이 논문의 저자 정보
이 논문과 함께 이용한 논문
방향그래프의 점대점 최단경로 탐색 알고리즘
이상운
한국지능시스템학회 논문지
2007
.12
최소신장트리를 적용한 주행시간 기반 내비게이션의 실시간 최단경로 탐색
이상운
한국정보기술학회논문지
2014
.08
Dijkstra 알고리즘을 확장한 효율적인 최단경로 탐색 알고리즘
호효휘
,
문일환
,
서정민
외 2명
한국멀티미디어학회 학술발표논문집
2007
.11
내비게이션 경로설정에서 최단거리경로 탐색을 위한 A*와 Dijkstra 알고리즘의 하이브리드 검색법
이용후
,
김상운
전자공학회논문지
2014
.10
우선순위 큐를 이용한 A* 기반 최단경로 탐색 기법
안진호
,
박민지
,
강성호
외 1명
한국정보기술학회논문지
2010
.08
최근 본 자료
댓글(0)
0