메모장/알고리즘 (1) 썸네일형 리스트형 A* Algorithm (에이스타 알고리즘) 개요 길 찾기 알고리즘으로 유명한 A* 알고리즘이다. 게임에서 많이 사용된다. 기본적으로 다익스트라 알고리즘의 변형이다. A*알고리즘은 휴리스틱 이론을 사용한다. 휴리스틱 이론은 정확한 값이 아닌 어림짐작을 통해 값을 추정하는 방법이다. A*알고리즘은 목표까지의 거리를 정확하게 측정하지 않고 어림짐작하여 연산 시간을 줄이는 것이 핵심이다. A*알고리즘을 통해 최단 거리를 찾기 위해 목표까지의 경로를 분할해야 하며, 이때 분할된 구역들이 노드가 된다. 초록색 노드가 시작노드, 빨간색 노드가 목표노드이며, 파란색은 지나갈 수 없는 장애물이다. 시작노드에 인접한 노드들 부터 확인하며, 비용이 작은 노드부터 탐색하게 되는데, 비용은 다음과 같이 정해진다. 비용 = (시작노드-현재노드 사이의 가중치) + (현재노.. 이전 1 다음
