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

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

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

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

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

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

“회전 제한 및 양방향 성질을 가진 네트워크 DB를 활용한 A* 알고리즘”에 대한 4개의 댓글

  1. 안녕하세요! GIS부서에서 일하게된 신입사원입니당

    경로탐색에 관한 알고리즘을 찾다가 글 보게 되었는데요, 뭐하나 여쭤보고싶습니다.

    회전제한이 어떤 정보를 말하는 표인지 궁금합니다!

    1. 안녕하세요, 김형준입니다.
      회전제한이라함은.. 어떤 지점(노드)에서 U턴 금지라던지.. 좌회전 금지라던지 등을 의미합니다.

      1. 빠른 답변 감사합니다!

        그렇다면 저 표에서 시작링크, 종료링크의 뜻이

        A->B->C 의 우회전과 E->B->C의 우회전이 불가능하다는 뜻인가요?

댓글 남기기

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