검색결과

검색조건
좁혀보기
검색필터
결과 내 재검색

간행물

    분야

      발행연도

      -

        검색결과 1

        1.
        2005.05 구독 인증기관 무료, 개인회원 유료
        2차원 평면에 원형 장애물들이 주어져 있을 때, 주어진 시작점과 끝점을 잇는 최단 경로를 구하는 문제를 다룬다. 이 때, 원형 장애물들은 서로 교차하지 않으며, 반지름이 각기 다르다고 가정한다. 최단 경로를 효율적으로 구하기 위해서, 본 논문에서는 두 가지의 필터를 제안한다. 첫 번째는 타원 필터이고, 두 번째는 컨벡스-헐 필터이다. 장애물들을 피하면서 주어진 두 점을 연결하는 최단 경로를 구하기 위해서는, 주어진 2차원 공간을 탐색하여야 하는데, 위의 두 필터는 최단 경로와 만나지 않게 되는 원형 장애물들을 미리 걸러냄으로써, 탐색 공간을 효율적으로 줄여준다. 또한 보로노이 다이어그램을 이용하면, 장애물들 간의 인접 정보를 효과적으로 활용할 수 있다. 필터링을 한 후에는 다익스트라 알고리즘을 이용하여 최단 거리를 구한다.
        3,000원