회전 제한 및 양방향 성질을 가진 네트워크 DB를 활용한 A* 알고리즘

실제 도로망은 U턴 제한이나 우회전 제한 등과 같은 회전 제한에 대한 성질과 좌측 및 우측 차로에 대한 방향에 대한 성질을 가집니다. 이러한 성질에 대한 속성값을 가지는 네트워크 데이터는 지능형 교통체계 표준 노드링크 관리시스템(http://nodelink.its.go.kr)에서 제공하고 있습니다.

이 글은 지능형 교통체계 표준 노드링크 관리시스템에서 제공하는 네트워크 DB에 대해 A* 알고리즘을 적용하는 각 단계별 과정에 대한 상태정보를 기록한 자료에 대한 글입니다. A*에 대한 자세한 설명은 기존의 최단 경로 탐색 – A* 알고리즘이라는 글을 참고하시기 바랍니다. 본 글은 A* 알고리즘을 확장하고 응용한 글이므로 반드시 A* 알고리즘을 완전하게 이해하고 있는 상태에서만 의미있게 이해될 수 있는 글이라는 점을 알려드립니다.

해결하고자 하는 네트워크 DB에서의 최적경로에 대한 문제는 아래 그림과 같습니다.

위의 문제에 대해 확장된 A* 알고리즘을 통해 최종적으로 도출된 그 결과는 아래의 그림과 같습니다.

해결하고자 하는 문제와 그 결과 도출을 위한 알고리즘의 각 단계를 정리한 내용은 아래의 pdf 파일에 담겨 있습니다.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다