친구가 인공지능, 검색, 게임등에 공통적으로 쓰일 수 있는 가장 요긴한 알고리즘을 알려달라고 부탁하더군요. 뭐 가장 처음 떠오르는 것이 바로 이 A* 알고리즘이더군요. 컴퓨터쪽 전공자 또는 게임쪽 전공자라면 누구나 한번쯤은 거쳐갔을 알고리즘이죠.
A* 알고리즘은 기본적으로 트리구조에서 많이 쓰이고 Best First Search의 방법을 쓰기 때문에 효율성도 갖추면서 코드도 깔끔히 만들 수 있는 장점이 있죠. 특히 휴리스틱(Heuristic) 접근법이라 제한된 시간과 제한된 컴퓨팅 리소스로 최적의 해답과 근접한 만족할 만한 솔루션을 찾아낼 수 있으면서도 그다지 복잡하지 않다는 것이 매력적인 점입니다.
아주 간단히 알고리즘으로 표현하면 다음과 같습니다. 알고리즘으로 표현한 것이기 때문에 구현은 어떤 언어로든 가능하죠. 교육용이니 아카데믹 한 면이라고만 생각 할수도 있지만 실제 코드로 만들어도 g,h function만 잘만들면 놀라운 성능을 보이죠.
기본적으로 Data Structure의 큐(Queue) 개념과 알고리즘을 읽고 이해할 수 있는 능력, 그리고 recursive function에 대한 거부감이 없어야 이해하기 쉬울 듯 하네요...
1. 주요 함수
(출처는 제가 대학다닐때 썼던 교재입니다 : (Russell, Stuart, and Peter Norvig. Artificial Intelligence. New Jersey: Prentice Hall, 1995)
Evaluation,기본 함수 개념
f (n) = g(n)+h(n)
g(n) = 루트부터 현재의 노드 까지의 웨이트 값
**** 거리를 찾는 소프트웨어라면 출발지부터 현재 지점까지의 자동차 미터에 찍힐 값
h(n) = 현재 노드부터 목표점까지의 최선의 선택으로 갔을때 가질 수 있는 웨이트 값.
**** 가장 핵심적인 함수로 목적에 따라자알~ 정해야 합니다.
**** 거리로 말하자면 현재 지점에서 목적지까지의 직선거리라 할 수 있겠죠. 주의할점은 절대로 실제 나올값 보다 큰 값을 가질수 있는 함수로 만들면 안됩니다. Admissible Heuristic이라고 불리우는데 예를들면 A 지점부터 B지점의 실제 도로상 주행 거리가 10km라고 할때 h(n)으로 estimate한 값이 절대로 10km보다 크면 안된다는 이야기죠. 그래서 거리를 측정하는 소프트웨어에서는 h(n)=직선거리 로 쓰는 것입니다.
Queueing-Fn : 언제나 그렇듯 병렬컴퓨팅이 아니라면 순차적으로 문제를 풀어야 겠죠. 그래서 큐에 문제를 푸는 순서를 정해 넣습니다. A*의 경우 위의 f(n)이 그 순서를 정하게 되죠. 뭐 데이터 구조까지 설명은 안하겠습니다. 데이터 구조론(Data Structure)시간에 최소한 큐는 배웠을테니깐요. 큐의 형성은 최초에 General-Search 함수에서 Make-Queue에서 형성되고 loop 안에서 각 노드마다 child노드를 f(n)에 의거하여 큐에 추가시킵니다.
알고리즘 함수
function A*-SEARCH(problem) returns a solution or failure
return BEST-FIRST-SEARCH(problem, g+h)
(Russell 97)
function BEST-FIRST-SEARCH(problem,EVAL-FN) returns a solution sequence
inputs: problem, a problem
EVAL-FN, an evaluation function
Queueing-Fn <- a function that orders nodes by EVAL-FN
return GENERAL-SEARCH(problem, Queueing-Fn)
(Russell 93)
function GENERAL-SEARCH(problem,QUEUING-FN) returns a solution, or failure
nodes<- MAKE-QUEUE(MAKE-NODE(INITIAL-STATE[problem]))
loop do
if nodes is empty then return failure
node<- REMOVE-FRONT(nodes)
if GOAL-TEST[problem] applied to STATE(node) succeeds then return node
nodes <- QUEUING-FN(nodes, EXPAND(node, OPERATORS[problem]))
end
(Russell 73)
2. 간단한 그림으로 본 예제
위의 함수들만으로는 거의 패닉상태에 빠져들 것 같아 간단히 그림으로 설명하도록 하겠습니다. 그림의 출처는 저(bgyuh)입니다.
** 각 노드는 도시들입니다.
** 붉은색 h= 에 적힌 값은 현재 도시에서 목적지까지의 직선거리입니다.
** 붉은색 g= 에 적힌 값은 출발지에서 현재 노드도시의 자동차 미터거리를 나타냅니다.
** 붉은 색 선은 도시 사이의 길이 있음을 표시합니다. 선위에는 도시사이의 실제적인 자동차 미터 거리를 나타냅니다.
** 도시 뒤의 d는 노드의 depth (깊이)입니다.
** 서치의 목적은 출발지부터 목적지까지 최단 주행거리를 가지는 경로를 찾는 것입니다.
간단히 프로그램이 서치과정에서 노드를 선택하는 과정을 보면 출발점에서는 당연히 도시 1 d 1를 선택하겠죠. Eval 함수 f(n) = g(n)+h(n)=110+300 = 410으로 2 d 1의 560보다 더 짧으니깐요. 그다음은 3가지 선택(11,12,13) 중에서 f 값 즉 총 거리의 Estimate 값이 가장 작은 도시 13 d 2를 선택 할 겁니다. 그다음은 물론 목적지라 직선거리 0인 131 도시를 선택하고 검색을 종료하겠죠.
좀더 자세히 들여다 보면
1. 루트에서 출발해서 첫번째 선택과정에서 보면 알 수 있듯이 노드 자체에 모든 값이 저장이 되어 있지는 않습니다. (즉 루트에서는 모든 브랜치 노드의 정보를 알 수 없고 바로 밑 자녀들의 정보만 알 수 있죠)
h값은 실시간으로 계산되는 estimate 값이고 단지 루트(출발도시)와 도시 1, 2간의 거리만이 실제값이 저장이 되어있죠. 만약에 모든 데이터를 저장해놓고 검색한다면 가장 정확하고 빠른 결과 (hash테이블처럼)를 얻을 수 있겠지만 경우의 수는 b^depth (예:바이너리트리의 경우 2^depth) 가 되므로 거의 무한정의 리소스가 필요합니다. g(n)은 물론 조금만 머리쓰면 쉽게 계산할 수 있죠.
정리해 보자면 각 노드에 저장된 정보는 도시의 좌표, 도시 이름, 각 인접 도시간의 도로와 그 도로로 갈 경우 인접도시간 거리 정도가 됩니다. 물론 더 고급기술로 가면 인덱싱을 이용하여 서치시간을 팍 단축시킬수도 있지만 생략하도록 하겠습니다.
2. 도시 13 d 2와 12 d 2를 비교할 경우 g값은 12 d 2가 더 작지만 h값을 더한 f값이 13 d 2가 더 작으므로 프로그램은 13 d 2를 선택하게 됩니다. 확실한 선택이었나를 따진다면 컴퓨터는 모르죠. 12 d 2의 노드를 검색 하지 않았기 때문입니다. 그러나 최적값에 가까운 값을 얻는 것이 목적이므로 그정도의 오차는 허락 할 수 있는 문제에 A* 알고리즘 사용해야 겠죠.
따라서 A* 알고리즘을 사용할 경우 Heuristic Function인 h(n)을 얼마나 잘 만드는 가에 따라 성능이 좌우됩니다.
3. f 값이 가장 작은 노드를 따라가더라도 목적지 (h=0)인 곳에 도착하지 못한다면 failure 를 return 하고 위 노드로 거슬러 올라가 다음으로 가능성이 높은 노드들을 따라 갑니다.
4. f (n) = g(n) + h(n) 값이 출발점부터 목적지까지의 자동차 미터거리를 Estimate한 값인데 노드가 진행될수록 커져야만 합니다. Admissible Heuristic 조건 때문이죠. Russell 교수님의 책에 이 조건이 왜 필요하고 A*가 왜 Optimal한가를 수학적으로 증명해 놓았는데 관심있으신분은 책을 사서 보셔도 좋을 듯 합니다.
5. 도시 132 d 3의 경우 h값이 더 커졌는데 뭔가 돌아가게 된다는 암시가 되겠죠. Make-Node Function에 아예 이런 노드를 제거해서 큐에 안들어가게 하면 그만큼 시간이 절약되겠지만 굉장히 특이한 경우 산에 가로막혀서 반드시 돌아가는 외길만 존재한다면 제거하기도 뭐하죠. 그러니 특수케이스를 만들어 실험해 봐야 합니다. 솔루션이 존재하는데 프로그램이 찾아내지 못하면 그것 또한 버그죠.
위의 검색과정은 단순하고 가장 이상적인 적용례이지만 실제 적용과정에서 고려해야만 할 점들은 훨씬 많고 다양하죠
가장 흔하게 겪을 수 있는 버그들의 예입니다.
1. 갔던 노드를 또 가게 될 경우 무한 순환의 오류에 빠질 수 있으니 꼭 위에 알고리즘에서 그 부분을 추가 해 줘야죠.
2. 만약 h값이 작은 노드들로 서치하다가 어느순간 h 값이 Parent 노드보다 커진다면 의심해 보아야 합니다. 실제로 현재노드에서 목적지까지 절벽, 바다등으로 가로막혀서 목적지까지 돌아가야만 하는 경로만이 존재하고 부모나 그위의 노드에서 다른 경로를 선택할 경우 더 짧은 경로를 찾을 수 있었다면 최적의 솔루션과 상당히 동떨어진 결과를 얻을 수도 있겠죠. 그래서 h값이 부모노드보다 커진다면 부모노드나 그 윗 노드에서 재검색을 하여 더 나은 솔루션이 있나 찾아보는 것도 나쁘지는 않을 것입니다.
이 밖에도 실제 적용을 할때에는 수많은 테스트를 케이스를 만들어 고쳐가면서 해야지 그냥 덥석 알고리즘만 코드로 만들다가는 이놈의 네이버처럼 글쓰는데 한글변환도 잘 안되던가 사진올리다 포스트 날아가는 버그들을 양산하게 되겠죠.
친구의 부탁으로 자료를 좀 만들다가 그냥 심심해서 포슷에 끄적거려 봤습니다. 몇시간만에 예제를 만든거라 혹시 오류나 오타가 있을지도 모르겠네요. 책에 있는 예제도 좋은데 특수케이스들을 설명하기 뭐해서 새로 만들어 봤습니다.
[출처] A* 알고리즘에 대한 간단한 설명|작성자 방글
