효율적인 휴리스틱 계산 처리를 위한 가중치 기반의선수행 A* 알고리즘 (A Weighted based Pre-Perform A* Algorithm for Efficient Heuristics Computation Processing)

서지정보

· 발행기관 : 한국게임학회
· 수록지 정보 : 한국게임학회 논문지 / 13권 / 6호 / 43 ~ 52페이지
· 저자명 : 오민석, 박성준

초록

경로 탐색은 인공지능의 매우 중요한 요소 중의 하나이며, 여러 분야에서 두루 쓰이는 과정이다. 경로 탐색은 매우 많은 연산이 필요하기 때문에 성능에 매우 중대한 영향을 미친다. 이를 해결하기 위해서 연산량을 줄이는 방식의 연구가 많이 진행되었고, 대표적으로 A* 알고리즘이 있으나 불필요한 연산이 있어 효율성이 떨어진다. 본 논문에서는 A* 알고리즘 중 연산 비용이 높은 노드 탐색 수 등 연산량을 줄이기 위해서 가중치 기반의 선수행 A* 알고리즘을 새롭게 제안한다. 제안한 알고리즘의 효율성을 측정하기 위해 시뮬레이션을 구현하였으며, 실험 결과 가중치를 이용하는 방법이 일반적인 방법보다 약 1～2배 높은 효율을 보였다.

영어초록

Path finder is one of the very important algorithm of artificial intelligence and is aprocess generally used in many game fields. Path finder requires many calculation, so itexerts enormous influences on performances. To solve this, many researches on theways to reduce the amount of calculate operations have been made, and the typicalexample is A* algorithm but it has unnecessary computing process, reducing efficiency.
In this paper, to reduce the amount of calculate operations such as node search withcostly arithmetic operations, we proposes the weight based pre-processing A* algorithm.
The simulation was materialized to measure the efficiency of the weight basedpre-process A* algorithm, and the results of the experiments showed that the weightbased method was approximately 1～2 times more efficient than the general methods.

참고자료

· 없음