Earticle

초록

영어

In transportation networks, searching speed and result accuracy are becoming more critical on searching minimum path algorithm. Current A* algorithm has a big advantage of high searching speed. However, it has disadvantage of complicated searching network and low accuracy rate of finding the minimum path algorithm. Therefore, this study developed A* algorithm’s heuristic function and focused on improving it’s disadvantages. Newly developed function in this study contains the area concept, not the line concept. During the progress, this study adopts the idea of a heavier node that remains lighter to the target node is better that the lighter node that becomes heavier when it is connected to the other. Lastly, newly developed algorithm has the feedback function, which allows the larger accuracy value of heuristic than before. This developed algorithm tested on real network, and proved that developed algorithm is useful.

한국어

교통 네트워크에서 하나의 노드로부터 다른 노드로 가는 최단 경로 탐색은 탐색속도와 함께 정확성도 매우 중요시 되고 있다. 기존 A* 알고리즘은 빠른 탐색속도가 큰 장점이기는 하지만, 분석네트워크가 다소 복잡하고, 링크수가 많은 대규모 네트워크에서는 최단 통행경로를 가까운 노드의 순서대로 단계적으로 찾아내는 데 정확도가 다소 낮은 약점을 갖고 있다. 따라서 본 연구에서는 A* 알고리즘의 평가함수와 알고리즘을 수정하여 정확성을 높일 수 있도록 하였다. 구 체적으로는 평가함수를 선적인 개념에서 면적인 개념으로 전환하였고, 계산단계의 진행과정에서 실제 부하량이 적을수 록 무조건 좋은 것이 아니라, 부하량이 커도 목표노드에 가까운 것이라면 더욱 최단경로에 유리하다는 개념을 도입한 것이다. 마지막으로 평가함수 값은 반복계산을 수행할수록 적어야 하는데, 이렇지 못할 경우, 피드백 기능을 부가하여 탐색 정확도를 높이도록 알고리즘을 수정하였다. 이렇게 개선된 알고리즘을 실제 네트워크상에서 적용해 본 결과, 유용 성이 있는 것으로 밝혀졌다.

목차

요약
 ABSTRACT
 Ⅰ. 서론
 Ⅱ. A* 알고리즘의 평가함수 연구 고찰
 Ⅲ. A* 알고리즘의 적용상 취약점
 Ⅳ. 평가함수의 개선
 Ⅴ. 새로운 알고리즘의 개발
 Ⅵ. 평가함수의 유용성 검증
  1. 검증방법
  2. 탐색 소요시간
  3. 정확성
 Ⅶ. 결론
 REFERENCES

키워드

저자

• 정병두 [ Jung, Byung-Doo | 계명대학교 교통공학과 교수 ] 주저자
• 유영근 [ Ryu, Yeong-Geun | 영남교통정책연구원 원장 ] 교신저자

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국ITS학회논문지 [The Journal of The Korean Society of Intelligent Transport Systems]

• 간기

  격월간

• pISSN

  1738-0774

• eISSN

  2384-1729

• 수록기간

  2003~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 326 DDC 338