기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
임의형태의 장애물 경계정보를 이용한 최소거리 우회경로 탐색 알고리즘
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 임의형태의 장애물 경계정보를 이용한 최소거리 우회경로 탐색 알고리즘
저자명
김윤성,박수현,Kim. Yun-Sung,Park. Soo-Hyun
간행물명
한국시뮬레이션학회논문지
권/호정보
2010년|19권 4호|pp.129-137 (9 pages)
발행정보
한국시뮬레이션학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

지금까지 연구된 최소비용 경로 알고리즘들은 정점과 정점간의 가중치가 부여된 간선을 갖는 그래프를 이용한다. 그러나, 바다와 같은 넓은 공간에서 시점과 종점사이에 섬과 같은 임의의 형태의 장애물이 존재하고 시점으로부터 종점까지의 최단거리를 찾고자 할 때, 이 알고리즘들은 최소비용 경로를 구하기 위해 장애물이 없는 공간상의 위치를 모두 정점으로 하고 인접정점들 사이에 가중치를 부여한 간선이 준비되어야 하므로 그 수가 매우 방대해져 공간복잡도가 높아지고 실행시간이 오래 걸리게 된다. 이에 본 논문에서는 정점과 가중치 간선의 그래프 자료구조를 이용하지 않고 장애물의 경계위치와 시점 및 종점위치 정보만을 이용하여 장애물을 우회하는 최소비용 경로를 탐색하는 효율적 알고리즘을 제안하고자 한다. 장애물을 포함하는 최소 경계 사각형의 행과 열의 크기(위치의 수)를 각각 m과 n이라 할 때, 제안한 알고리즘은 최대 O(mn)의 시간 복잡도를 가진다. 이 성능은 제안한 알고리즘이 기존 알고리즘에 비해 효율적임을 보여준다.

기타언어초록

Currently used shortest path search algorithms involve graphs with vertices and weighted edges between each vertex. However, when finding the shortest path with a randomly shaped obstacle(an island, for instance) positioned in between the starting point and the destination, using such algorithms involves high memory inefficiency and is significantly time consuming - all positions in the map should be considered as vertices and every line connecting any of the two adjacent vertices should be considered an edge. Therefore, we propose a new method for finding the shortest path in such conditions without using weighted graphs. This algorithm will allow finding the shortest obstacle bypass given only the positions of the obstacle boundary, the starting point and the destination. When the row and column size of the minimum boundary rectangle to include an obstacle is m and n, respectively, the proposed algorithm has the maximum time complexity, O(mn). This performance shows the proposed algorithm is very efficient comparing with the currently used algorithms.