-위키백과 출처-
[A* 알고리즘]
A* 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 (다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프/나무 탐색 알고리즘 중 하나이다.
이 A* 알고리즘은 너비 우선 탐색의 한 예로 분류할 수도 있다.
OpenCV 카페를 둘러보다가 어떤 분께서 최단 경로 알고리즘에 대해서 공부를 하고 있다며 동영상을 올려놓은 것을 보았다. 그 동영상은 무척이나 흥미로웠고, 재미있어 보였다. 그래서 아직 할 일들이 많지만 수면 시간을 줄여서 한 번 이 알고리즘에 대해서 알아보고, 어떻게 코딩할지 생각해보았다.
영상 처리만 공부하다가 갑자기 GUI 쪽을 공부해야 해서 간단하게 JavaFX로 개발할 생각이다.
생각 외로 간단하다고도 생각이 되는데 어떻게 보면 어렵게도 보인다. 알고보니 내가 생각한 방법을 다른 사람들도 많이 사용하는 것 같아 보인다......
출발 지점: A
도착 지점: B
검은색: 장애물
[그림 1: A와 B]
대각선으로 이동할 때는 비용이 15가 들며, 그냥 일직선으로 이동을 하면 비용이 10이 든다고 정하도록 하자.
그리고 A, B 즉, 기준점이 아닌 블럭은 도착까지 가는 비용과 출발로 돌아가는 비용이 있다.
또한 지나왔던 노드는 제외시키며 장애물도 무시하고 도착 비용과 출발 비용을 계산한다.
B까지 가려는 최단 경로를 구해보자. 그러기 위해선 비용=도착+출발의 값이 적은 곳으로 가야한다.
현재 A에서 다음 노드로 가기 위한 가장 적은 비용이 드는 노드는 A의 오른쪽에 있는 비용이 40이 드는 노드이다. A를 이동시켜보자.
[그림 2: 이동 후]
이동하고 나서 다시 비용이 적은 곳으로 노드가 이동해야하는데 두 개의 노드가 있다. 나는 아래가 좋으니 위 아래로 중복이 있을 시에 아래로 이동한다고 정하자. 아래로 내겨가보도록 하겠다.
[그림 3: 3번 째 이동]
이제 A의 위치, 즉 주변의 비용을 보니 다시 똑같은 비용이 보인다. 이럴 때에는 대각선과 진석의 비용이 일치할 때 직선으로 이동한다고 정하자. 그렇다면 A의 아래로 중심이 이동한다.
이렇게 계속 계산하다보면 도착 B의 지점에 최단 경로로 오게 된다.
무척 간단 명로하게 설명했기 때문에 이해가 힘들 수도 있다.
지금 이 알고리즘을 시각화해서 다시 한번 정리하고 마무리하는 시간을 갖도록 하겠다.
참고하면 좋을 블로그, 이해하기 쉬움
: http://cozycoz.egloos.com/9748811