본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

지능형 최단 경로, 최소 꺾임 경로 및 혼합형 최단 경로 찾기
Finding Rectilinear(L1), Link Metric, and Combined Shortest Paths with an Intelligent Search Method

임준식    (경원대학교 전자계산학과  );
  • 초록

    이 논문은 새로운 휴리스틱 탐색(heuristic search)방법을 이용하여, 수평 및 수 직선으로 이루어진 방해 물들이 놓인 가운데 수평 및 수직선으로 구성된 최단 거리 (rectilinear shortestpath)와 꺾이는회수가 가장 적은최소 꺾임경로(link metric shortest path) 및 이 둘을 혼합시킨 혼합형 최단 경로를 구하는 알고리즘을 서술 하고 있다. 최단 경로를 구하는 방법으로 미로 찾기형 알고리즘(maze-running algorithms)과 선형 탐색 알고리즘(line-search algorithms)의 장점만을 이용한 GMD 알고리즘(Guided Minimum Detour algorithm)을 제안하고 있으며 이를 더욱 효율 적으 로 개선한 LGMD 알고리즘 (Line-by-Line Guided Minimum Detour algorithmm)을 개발 하였다. 이들 GMD와 LGMD 알고리즘은 기존의 최단 경로를 내포하고 있는 conection group를 이용하지 않고서도 휴리스틱을 사용한 guided A 탐색(guided A* search)을 이용하여 최적의 최단 경로를 구할 수 있는 장점이 있으며 시간과 메모리 면에서 효 율을 극대화하였다. 이들 GMD와 LGMD 알고리즘은 각각 O(m+eloge+NlogN)와 O(eloge+ NlogN)의 시간과 O(e+N)의 메모리를 사용한다. 여기서 m은 탐색에 사용된 지선 (line segment)들의 수이다. 또한 LGMD는 최소 꺾임 경로(link metric shortest path)와 최단 경로와 최소의 꺾임을 조합한 혼합형 최단 경로를 구하는 데에도 적용될 수 있는 확장성을 가지고 있다.


    This paper presents new heuristic search algorithms for searching rectilinear r(L1), link metric, and combined shortest paths in the presence of orthogonal obstacles. The GMD(GuidedMinimum Detour) algorithm combines the best features of maze-running algorithms and line-search algorithms. The SGMD(Line-by-Line GuidedMinimum Detour)algorithm is a modiffication of the GMD algorithm that improves efficiency using line-by-line extensions. Our GMD and LGMD algorithms always find a rectilinear shortest path using the guided A search method without constructing a connection graph that contains a shortest path. The GMD and the LGMD algorithms can be implemented in O(m+eloge+NlogN) and O(eloge+NlogN) time, respectively, and O(e+N) space, where m is the total number of searched nodes, is the number of boundary sides of obstacles, and N is the total number of searched line segment. Based on the LGMD algorithm, we consider not only the problems of finding a link metric shortest path in terms of the number of bends, but also the combined L1 metric and Link Metric shortest path in terms of the length and the number of bands.


 저자의 다른 논문

  • 임준식 (10)

    1. 1999 "이동형 에이전트와 Java 기반의 Aglets 구현 기술" 한국멀티미디어학회지 3 (2): 70~82    
    2. 2001 "퍼지-기반 낙폭 제한을 적용한 실시간 입찰 에이전트 시스템" 인터넷정보학회논문지 = Journal of Korean Society for Internet Information 2 (2): 95~103    
    3. 2002 "학술전문가 선정을 위한 지식 기반 언어적 접근" 퍼지 및 지능시스템학회 논문지 = Journal of fuzzy logic and intelligent systems 12 (6): 549~553    
    4. 2004 "Finding Fuzzy Rules for IRIS by Neural Network with Weighted Fuzzy Membership Function" International journal of fuzzy logic and intelligent systems : IJFIS 4 (2): 211~216    
    5. 2004 "가중 퍼지 소속함수 기반 신경망을 이용한 Wisconsin Breast Cancer 예측 퍼지규칙의 추출" 정보처리학회논문지. The KIPS transactions. Part B. Part B b11 (6): 717~722    
    6. 2005 "퍼지신경망과 비중복면적 분산 측정법을 이용한 최소의 특징입력 및 퍼지규칙의 추출" 퍼지 및 지능시스템학회 논문지 = Journal of fuzzy logic and intelligent systems 15 (5): 599~604    
    7. 2006 "NEWFM을 이용한 자동 조기심실수축 탐지" 퍼지 및 지능시스템학회 논문지 = Journal of fuzzy logic and intelligent systems 16 (3): 378~382    
    8. 2007 "NEWFM 기반 가중평균 역퍼지화에 의한 비선형 시계열 예측 모델링" 퍼지 및 지능시스템학회 논문지 = Journal of fuzzy logic and intelligent systems 17 (4): 563~568    
    9. 2009 "심박수 변이도와 퍼지 신경망을 이용한 부정맥 추출" 인터넷정보학회논문지 = Journal of Korean Society for Internet Information 10 (5): 107~116    
    10. 2010 "운동 형상 분류를 위한 웨이블릿 기반 최소의 특징 선택" 한국콘텐츠학회논문지 = The Journal of the Korea Contents Association 10 (6): 27~34    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 이용한 콘텐츠
이 논문과 함께 출판된 논문 + 더보기