|
길찾기 알고리즘이라고 하면 보통 가장 먼저 떠오르는 알고리즘은 기초적으로 배우는 다익스트라 알고리즘(Dijkstra algorithm)일 것이다. 최단거리를 찾아주는 대표적인 알고리즘이지만 실제 프로그램에 적용하기에 문제가 되는 부분이 있다. 다익스트라 알고리즘은 경로를 찾을 때 각 노드에서 목적지 까지의 소모되는 실제 비용을 계산하여 비교하기 때문에 시간 비용이 많이 든다는 것이다.
이러한 문제를 해결하기 위해서 다음 노드로의 분기를 모든 노드가 아닌 가장 적은 추정 비용을 갖는 노드로 이동할 수 있게 휴리스틱 함수(Heuristic Function)를 적용한다면 각 노드에서 분기를 줄일 수 있다. 이를 대표하는 탐색 알고리즘인 A*A Star에 대해 알아본다.
A* 알고리즘
A* 알고리즘은 추정 비용을 계산해 가장 적은 비용을 갖는 노드를 선택해 탐색하며 다음 노드로의 분기를 줄일 수 있다. 목적지 까지의 예상 비용만을 비교하여 다음 노드를 선택하는 BFSBest First Search와 다른 점은, 노드를 선택하는 기준으로 시작점으로 부터 노드까지 이동하는데 드는 비용과 현재 노드로부터 목적지까지 예상되는 비용을 더한 값을 사용한다는 것이다.
BSF의 선택기준 = 목적지까지 예상 비용
A*의 선택기준 = 추정비용 = 시작점으로 부터의 비용 + 목적지까지 예상 비용
A*는 다음으로 탐색할 노드를 선택할 때 오픈 리스트Open List와 클로즈 리스트Close List라는 개념을 사용한다. 오픈 리스트는 탐색이 아직 안된 추정치만 존재하는 노드들의 집합을, 클로즈 리스트는 탐색이 되어 추정비용이 계산된 비용으로 바뀐 노드들의 집합을 의미한다.
현재 노드에서 클로즈 리스트에 들어있지 않는 인접한 이웃 노드들의 추정지를 계산하고 각 이웃 노드의 부모 노드를 현재 노드로 지정한다. 다음으로 이웃 노드들을 오픈 리스트에 넣는데, 이미 오픈 리스트에 해당 노드가 존재할 경우 추정 비용을 비교해 작은 값을 갖는 노드를 사용한다.
그 후, 오픈 리스트에 저장된 노드 중 가장 작은 추정 비용을 갖는 노드를 다음으로 탐색할 노드로 선택한다. 선택된 노드는 탐색이 된 노드이기 때문에 오픈 리스트에서 클로즈 리스트로 옮기고 다시 현재 노드에 인접한 노드들의 추정 비용을 계산해 오픈 리스트에 넣는다.
목적지 노드가 이웃 노드로 나타날 때 까지 위의 과정을 반복한다.
탐색 과정 예시
가중치를 사용한 A*
앞서 설명한 것처럼 BSF와 달리 A*는 ‘시작점으로 부터의 비용’을 추가적으로 사용한다. 그리고 각각의 요소에 가중치를 적용하면 다음과 같이 표현할 수 있다.
A*의 선택기준 = 추정비용 = a*시작점으로 부터의 비용 + b*목적지까지 예상 비용
일반적으로 말하는 A* 알고리즘의 경우 a와 b의 값을 1:1의 비율을 사용한 알고리즘을 말한다. 눈치가 빠른 사람이라면 알겠지만 BFS는 이 가중치의 비율을 0:1로 사용한 알고리즘이다. 이처럼 요소들을 나누고 가중치를 적용하면 같은 알고리즘으로 다른 결과를 얻을 수 있다.
예제
다른 길찾기 알고리즘을 실행해 보고 싶다면 다음 사이트를 참고하면 된다.
http://qiao.github.io/PathFinding.js/visual/
https://github.com/qiao/PathFinding.js/tree/master/src/finders
|
