정보통신공학개론(차량항법장치)

① 다익스트라법
이 계산 방법은 그래프 탐색 수법으로 널리 알려져 있는 방법이다. 목적지를 설정하면 , 현재 위치의 노드를 출발점으로 하여 가장 가까운 노드를 찾는다. 그리고 또 그 노드에 가장 가까운 노드를 찾고 , 다시 동심원 모양으로 점차 넓혀 가는 계산 방법이다. 수면에 돌을 던졌을 때 생기는 파문처럼 , 출발지에 해당하는 노드를 중심으로 한 동심원상으로 경로 코스트를 계산하는 방법이다. 그러나 이 방법을 이용하여 최적의 경로를 찾으려면 , 다수의 노드와 넓은 면적의 계산을 필요로 한다. 검색 면적을 줄이는 한가지 방법으로서 , 이 프로세스를 출발지측과 목적지측에서 교대로 계산하여 , 마지막으로 이어진 경로를 선택하는 효율적인 방법이 있다. 이 경우 , 출발지측은 목적지로 어떤 노드로 가면 좋은지? 목적지측은 어떤 노드로 오면 좋은지? 라고 하는 본질적으로 다른 중요한 문제에 대해 각각 출발지측은 순방향 링크 , 목적지측은 역방향 링크 계산을 실행한다.
② A*법
이 계산 방법은 그래프 탐색 수법으로 널리 알려져 있는 방법이다. 경로 계산을 동심원상으로 전개하는 다익스트라법에 대해 , 출발지와 목적지의 방향성을 …