학술논문
임의형태의 장애물 경계정보를 이용한 최소거리 우회경로 탐색 알고리즘
이용수 5
- 영문명
- A Shortest Bypass Search Algorithm by using Positions of a Certain Obstacle Boundary
- 발행기관
- 한국시뮬레이션학회
- 저자명
- 김윤성(Yunsung Kim) 박수현(Soo-Hyun Park)
- 간행물 정보
- 『한국시뮬레이션학회 논문지』제19권 제4호, 129~137쪽, 전체 9쪽
- 주제분류
- 공학 > 기타공학
- 파일형태
- 발행일자
- 2010.12.30
4,000원
구매일시로부터 72시간 이내에 다운로드 가능합니다.
이 학술논문 정보는 (주)교보문고와 각 발행기관 사이에 저작물 이용 계약이 체결된 것으로, 교보문고를 통해 제공되고 있습니다.
국문 초록
지금까지 연구된 최소비용 경로 알고리즘들은 정점과 정점간의 가중치가 부여된 간선을 갖는 그래프를 이용한다. 그러나, 바다와 같은 넓은 공간에서 시점과 종점사이에 섬과 같은 임의의 형태의 장애물이 존재하고 시점으로부터 종점까지의 최단 거리를 찾고자 할 때, 이 알고리즘들은 최소비용 경로를 구하기 위해 장애물이 없는 공간상의 위치를 모두 정점으로 하고 인접정점들 사이에 가중치를 부여한 간선이 준비되어야 하므로 그 수가 매우 방대해져 공간복잡도가 높아지고 실행시간이 오래 걸리게 된다. 이에 본 논문에서는 정점과 가중치 간선의 그래프 자료구조를 이용하지 않고 장애물의 경계위치와 시점 및 종점위치 정보만을 이용하여 장애물을 우회하는 최소비용 경로를 탐색하는 효율적 알고리즘을 제안하고자 한다. 장애물을 포함하는 최소 경계 사각형의 행과 열의 크기(위치의 수)를 각각 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.
목차
1. 서론
2. 관련연구
3. 제안된 알고리즘
4. 성능분석
5. 결론
해당간행물 수록 논문
- False Alarm Rate 변화에 따른 DoS/DDoS 탐지 알고리즘의 성능 분석
- 이동 환자 상시 모니터링 시스템의 시스템 명세 기법 기반 설계와 검증
- 소부대 교전훈련 Virtual-Constructive 시뮬레이션 연동개념 연구를 위한 테스트베드
- 한국형 CMMS 개발 및 관리시스템의 VV&A 프로세스 설계
- 함정전투 시뮬레이션을 위한 HEAP 기반 지능 에이전트에 관한 연구
- 분포형 합성환경자료의 군사시뮬레이션 적용
- 체계 효과도 분석을 위한 공학/교전 모델 연동 시뮬레이션 기술 연구
- 반도체 생산 성능 향상 및 다양한 이송패턴을 수행할 수 있는 범용 스케줄러 알고리즘에 관한 연구
- 팀 결성 분석을 위한 행위자 기반 시뮬레이션 모형
- 연관 규칙 생성 알고리즘 기반의 개인화 의류 추천 시스템
- SBA를 위한 아키텍처 프레임워크 개념모델에 관한 연구
- 패킷 카운팅을 이용한 DoS/DDoS 공격 탐지 알고리즘 및 이를 이용한 시스템
- SBA 성숙도 측정모형에 관한 연구
- 시뮬레이션 기법을 통한 자동차용 열 수축 튜브 생산공정모델 개발
- 전술객체 위치 모의를 위한 데이터 융합 및 추적 회피 시뮬레이션
- 소프트웨어 프로덕트 라인공학을 적용한 동적 재구성 컴포넌트 개발 : 유도무기체계
- 강제 시스템간 핸드오버 시 QoS 보장 방안
- SIP 프록시 큐의 비선형적 과부하 제어 방법
- 임의형태의 장애물 경계정보를 이용한 최소거리 우회경로 탐색 알고리즘
- 타당성 평가가 보완된 모델 운용상의 전투실험 모의분석 절차 연구
- 무기체계 효과도 분석을 위한 통합 모의 엔진의 서비스 구성 방안 연구
- 전술객체 위치 모의 및 추적을 위한 필터링 알고리즘 연구
- 함정 Crew Mess Room 운용성 검증을 위한 혼잡도 평가 시뮬레이션 사례 연구
- 장애물 회피에 페널티 보행 속도 알고리즘을 적용한 여객선 승객 탈출 시뮬레이션
- 에이전트 기반의 NCW 전투모델링 시스템 설계
- 우주방사능 환경에서 정지궤도 위성시스템 설계에 관한 고찰
- 추이적 행렬을 이용한 사이폰 감지 정책
- 시불변 특징점 추출 및 정합을 이용한 주기 신호의 길이 보정 기법
- SEDRIS기반의 모의자료 표현 표준화
- 수중대잠전 교전모델의 무기체계 효과도 분석을 위한 합성환경기반 가상시험 프레임워크 설계 기술
- 무선 센서 네트워크에서 링크 상태 및 트래픽 분산 정보를 이용한 효과적인 라우팅 방법
- SIP 프록시에서 우선순위를 가지는 INVITE 메시지의 우회 방법
참고문헌
교보eBook 첫 방문을 환영 합니다!
신규가입 혜택 지급이 완료 되었습니다.
바로 사용 가능한 교보e캐시 1,000원 (유효기간 7일)
지금 바로 교보eBook의 다양한 콘텐츠를 이용해 보세요!