A* 알고리즘
최근 수정 시각: (5년 전)
에이스타에서 넘어옴
분류
1. 개요 [편집]
다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다.
에이스타 알고리즘 이라고 읽는다.
지금까지 가장 최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로, A* 알고리즘은 현재 상태의 비용을 , 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 라고 할 때, 둘을 더한 가 최소가 되는 지점을 우선적으로 탐색하는 방법이다. 이 가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다. 휴리스틱 함수 에 따라 성능이 극명하게 갈리며, 일 때는 다익스트라 알고리즘과 동일하다.
다만 사용된 휴리스틱에 따라서 최단거리를 도출할 수 없기도 하기 때문에 개량하여 사용하는 경우가 많다. 따라서 IDA*, Jump Point Search 등 A*의 파생형 또한 많은 편이다.
A*를 사용하는 이유는 다익스트라의 현실 적용이 매우 어렵기 때문이다. 당장에 네트워크 같은 디지털적인 공간이 아닌, 현실의, 사람이 사는 공간을 생각해보자. 사람이 다닐 수 있는 "거리"는 명백히 아날로그하다. 이것들을 전부 노드화시키기에는 그 수가 엄청나게 많아질 수 있다. 그렇다면 탐색해야 하는 공간도 그만큼 커지게 되고, 시간 복잡도 역시 아득히 커질 것이다. 또한 어찌어찌 잘 노드화시켜서 다익스트라를 사용할 수 있는 상황을 만들어서 경로를 발견했다고 치자. 그렇게 탐색한 경로가 자동차 정체 구간, 출근길 등 다양한 변수로 인해 오히려 더 느려질 수 있는 경우도 발생하기 마련이다. 이러한 변수 때문에 A* 알고리즘을 사용하는 것이다. 그리고 A*를 발전시킨 형태가 D*(Dynamic A*)알고리즘인데, 현세대의 대부분의 차량 내비게이션은 이를 활용한다고 보면 된다.
에이스타 알고리즘 이라고 읽는다.
지금까지 가장 최소의 비용으로 도달한 지점부터 탐색하는 다익스트라 알고리즘의 원리를 차용한 것으로, A* 알고리즘은 현재 상태의 비용을 , 현재 상태에서 다음 상태로 이동할 때의 휴리스틱 함수를 라고 할 때, 둘을 더한 가 최소가 되는 지점을 우선적으로 탐색하는 방법이다. 이 가 작은 값부터 탐색하는 특성상 우선순위 큐가 사용된다. 휴리스틱 함수 에 따라 성능이 극명하게 갈리며, 일 때는 다익스트라 알고리즘과 동일하다.
다만 사용된 휴리스틱에 따라서 최단거리를 도출할 수 없기도 하기 때문에 개량하여 사용하는 경우가 많다. 따라서 IDA*, Jump Point Search 등 A*의 파생형 또한 많은 편이다.
A*를 사용하는 이유는 다익스트라의 현실 적용이 매우 어렵기 때문이다. 당장에 네트워크 같은 디지털적인 공간이 아닌, 현실의, 사람이 사는 공간을 생각해보자. 사람이 다닐 수 있는 "거리"는 명백히 아날로그하다. 이것들을 전부 노드화시키기에는 그 수가 엄청나게 많아질 수 있다. 그렇다면 탐색해야 하는 공간도 그만큼 커지게 되고, 시간 복잡도 역시 아득히 커질 것이다. 또한 어찌어찌 잘 노드화시켜서 다익스트라를 사용할 수 있는 상황을 만들어서 경로를 발견했다고 치자. 그렇게 탐색한 경로가 자동차 정체 구간, 출근길 등 다양한 변수로 인해 오히려 더 느려질 수 있는 경우도 발생하기 마련이다. 이러한 변수 때문에 A* 알고리즘을 사용하는 것이다. 그리고 A*를 발전시킨 형태가 D*(Dynamic A*)알고리즘인데, 현세대의 대부분의 차량 내비게이션은 이를 활용한다고 보면 된다.
2. 원리 [편집]
가장 기본이 되는 식은 다음과 같다.
동작은 다음과 같이 된다.
동작은 다음과 같이 된다.
- 를 오름차순 우선순위 큐에 노드로 삽입한다.
- 우선순위 큐를 pop한다.
- 해당 노드에서 이동할 수 있는 노드를 찾는다.
- 그 노드들의 를 구한다.
- 그 노드들을 우선순위 큐에 삽입한다.
- 목표 노드에 도달할 때까지 반복한다.
의사코드는 다음과 같다.
PQ.push(start_node, g(start_node) + h(start_node)) //우선순위 큐에 시작 노드를 삽입한다. while PQ is not empty //우선순위 큐가 비어있지 않은 동안 node = PQ.pop //우선순위 큐를 pop한다. if node == goal_node //만일 해당 노드가 목표 노드이면 반복문을 빠져나온다. break for next_node in (next_node_begin...next_node_end) //해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안 PQ.push(next_node, g(node) + cost + h(next_node)) //우선순위 큐에 다음 노드를 삽입한다. print goal_node_dist //시작 노드에서 목표 노드까지의 거리를 출력한다.
3. 예시 [편집]
8-puzzle, 15-puzzle이 좋은 예시가 된다.
파일:depthfirstsearch.jpg
[출처]
이와 같은 상황은 을 이동 횟수, 현재 퍼즐의 상태를 노드로 하고 알고리즘을 시행한다면 해결이 가능하다.
보통 현재 퍼즐의 상태는 해시로 노드화한다. 그리고 은 N-Puzzle의 유명한 휴리스틱 함수인 Manhattan distance function으로 한다. Manhattan distance, 즉 택시거리는 2차원 평면 좌표계에서의 두 정점을 라고 할 때, 를 의미한다.
이때의 이다. 이때 는 두 위치 사이의 택시거리, 는 어떤 숫자의 현재 위치, 는 그 노드가 원래 있어야 할 위치이다.
Manhattan distance는 Admissible하다.
파일:depthfirstsearch.jpg
[출처]
이와 같은 상황은 을 이동 횟수, 현재 퍼즐의 상태를 노드로 하고 알고리즘을 시행한다면 해결이 가능하다.
보통 현재 퍼즐의 상태는 해시로 노드화한다. 그리고 은 N-Puzzle의 유명한 휴리스틱 함수인 Manhattan distance function으로 한다. Manhattan distance, 즉 택시거리는 2차원 평면 좌표계에서의 두 정점을 라고 할 때, 를 의미한다.
이때의 이다. 이때 는 두 위치 사이의 택시거리, 는 어떤 숫자의 현재 위치, 는 그 노드가 원래 있어야 할 위치이다.
Manhattan distance는 Admissible하다.
4. 기타 [편집]
라이선스를 별도로 명시하지 않은 문서는 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다.
기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다.
문서의 기여자는 역사 탭에서 확인할 수 있습니다.
접두어의 N: - 나무위키 사용자, R: - 리그베다 위키의 사용자를 뜻합니다.
자세한 사항은 나무위키에서 동일한 문서의 역사를 참고하시기 바랍니다.