최소 단어 이상 선택하여야 합니다.
최대 10 단어까지만 선택 가능합니다.
다음과 같은 기능을 한번의 로그인으로 사용 할 수 있습니다.
NTIS 바로가기한국인터넷방송통신학회 논문지 = The journal of the Institute of Internet Broadcasting and Communication, v.12 no.4, 2012년, pp.131 - 140
The shortest path search algorithm of navigation is generally based on Dijkstra algorithm and considers only the distance using the weight. Dijkstra algorithm based on the distance mainly ought to perform the 'number of nodes 1' and requires a lot of memory, for it is to start from the starting node...
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
핵심어 | 질문 | 논문에서 추출한 답변 |
---|---|---|
Dijkstra 알고리즘이란 무엇인가? | 이와 같은 이유로 내비게이션에는 Dijkstra 알고리즘이 가장 널리 활용되고 있다.[1,6,7] Dijkstra 알고리즘은 양의 가중치를 갖는 호들로 구성된 방향 그래프에 대해 단일 출발 노드부터 다른 모든 노드까지의 최단 경로 (Single-Source Shortest Path)를 찾는 알고리즘이다[3-5]. | |
방향 그래프는 어디에 활용되는가? | 방향 그래프는 최단 경로 (Shortest Path, SP)와 임계 경로 (Critical Path, CP) 등을 구하는데 활용된다. 본 논문은 최단 경로에 초점을 맞춘다. | |
내비게이션에는 Dijkstra 알고리즘이 가장 널리 활용되는 이유는 무엇인가? | [1,2] 이들 알고리즘은 일반적으로 호의 가중치로 거리 (Length) 정보를 활용한다. Bellman Ford 알고리즘은 그래프 크기가 커짐에 따라 Dijkstra 알고리즘보다 많은 시간이 소요되지만 좋은 결과를 얻을 수 있다. 위상순서 알고리즘은 선형 시간대에 최단 경로를 찾을 수 있지만 최적의 경로를 찾지 못할 수 도 있다. A* 알고리즘은 Dijkstra 알고리즘과 같이 좋은 결과를 얻으며 메모리를 적게 요구하지만 알고리즘 구현이 보다 어렵다. 이와 같은 이유로 내비게이션에는 Dijkstra 알고리즘이 가장 널리 활용되고 있다. |
M. Abboud, L. Mariya, A. Jaoude, and Z. Kerbage, "Real Time GPS Navigation System," 3rd FEA Student Conference, Department of Electrical and Computer Engineering, American University of Beirut, 2004.
T. H. Cormen, C. E. Leserson, R. L. Rivest, and C. Stein, "Introduction to Algorithms," 2nd Edition, MIT Press and McGraw-Hill, 2001.
E. W. Dijkstra, "A Note on Two Problems in Connection with Graphs," Numerische Mathematik, Vol. 1, pp. 269-271, 1959.
Wikipedia, "Dijkstra's Algorithm," http://en.wikipedia.org/wiki/Dijkstra_algorithm, Wikimedia Foundation Inc., 2012.
J. Misra, "A Walk Over the Shortest Path: Dijkstra's Algorithm Viewed as Fixed-Point Computation," Department of Computer Science, University of Texas at Austin, USA, 2000.
Y. T. Lim and H. M. Kim, "A Shortest Path Algorithm for Real Road Network Based on Path Overlap," Department of Civil Engineering, Institute of Transportation Studies, University of California, Irvine, USA, http://www.its.uci.edu/-hyunmyuk/library/(2005)20EAST(k-path). pdf, 2005.
F. B. Zhan, "Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures," Journal of Geographic Information and Decision Analysis, Vol. 1, No. 1, pp. 69-82, 1997.
K. S. Lee, "Shortest Path Algorithm," http://www.geocities.com/leekinseng1/
*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.
출판사/학술단체 등이 한시적으로 특별한 프로모션 또는 일정기간 경과 후 접근을 허용하여, 출판사/학술단체 등의 사이트에서 이용 가능한 논문
※ AI-Helper는 부적절한 답변을 할 수 있습니다.