서지주요정보
최대 거리 제약이 있는 시맨틱 장소를 경유하는 최단 경로 탐색 방법 = Finding the shortest path via a semantic place with a maximum distance constraint
서명 / 저자 최대 거리 제약이 있는 시맨틱 장소를 경유하는 최단 경로 탐색 방법 = Finding the shortest path via a semantic place with a maximum distance constraint / 김병기.
저자명 김병기 ; Kim, Byungki
발행사항 [대전 : 한국과학기술원, 2016].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8029202

소장위치/청구기호

학술문화관(문화관) 보존서고

MCS 16001

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Many people use GPS navigation systems to find directions when driving a car. Beyond the needs to find the fastest possible routes, there are growing needs to find the shortest path via waypoint such as gas stations. While there have been a number of studies to find the answer to the similar problem, most were concentrated on searching items near a route. In this paper, we propose an algorithm to compute top-k shortest paths among possible routes via waypoint which is located on the route under the maximum distance limit from a starting point. To guarantee that proposed algorithm achieves satisfactory performance, an experiment has been conducted on real dataset.

많은 사람들이 출발지에서 도착지까지 가는 최단 경로를 찾기 위해 내비게이션 시스템을 이용한다. 단순히 출발지에서 도착지까지의 최단 경로를 찾아주는 것에 대한 요구를 벗어나서, 도착지까지 가는 도중에 주유소 등의 경유지를 방문하는 최단 경로를 찾고자 하는 요구가 늘어나고 있다. 기존에 최단 경로를 구하는 여러 연구들이 진행된 반면, 이러한 경유 최단 경로 관련 연구는 도착지까지의 최단 경로 주변의 아이템들에 대한 검색만 대부분 이루어져 있다. 본 논문에서는 출발지에서 일정 이동 거리 범위 내에 있으면서 특정 속성을 만족하는 경유지를 지나는 여러 경로 결과들 중 최상의 k개 결과를 얻어내는 알고리즘을 제안한다. 그리고 제안한 알고리즘을 실세계 데이터에 대해 기초적인 알고리즘과 비교 실험하여 좋은 성능을 보임을 확인한다.

서지기타정보

서지기타정보
청구기호 {MCS 16001
형태사항 iii, 24 p. : 삽도 ; 30 cm
언어 한국어
일반주기 저자명의 영문표기 : Byungki Kim
지도교수의 한글표기 : 김명호
지도교수의 영문표기 : Myoung Ho Kim
학위논문 학위논문(석사) - 한국과학기술원 : 전산학부,
서지주기 참고문헌 수록
주제 최단 경로 탐색
데이크스트라 알고리즘
$A \ast 알고리즘$
양방향 탐색
도로망
Shortest path search
Dijkstra's algorithm
$A \ast algorithm$
Bidirectional search
Road network
QR CODE qr code