Origin of A* Algorithm

오늘 인공지능 수업 을 들으면서 A*알고리즘 에 대해서 배웠는데, 수업 중간에 문득 한가지 의문이 떠올랐습니다.

왜 A* 알고리즘 이라는 이름을 지었을까?

점점 궁금해지더군요. 결국 교수님께 물어보긴 했는데 교수님도 그 유래는 잘 모르셔서 제가 한번 알아봤습니다.

일단 위키피디아의 A*알고리즘 페이지 를 살펴보니 처음으로 이 알고리즘이 소개 된 것은 1968년에 한 논문 을 통해서였습니다.

The algorithm was first described in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael. In their paper, it was called algorithm A. Since using this algorithm yields optimal behavior for a given heuristic, it has been called A*.

- from wikipedia A* Algorithm page

"A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs" 라는 제목의 논문 이었는데요, 간단히 말해서 "그래프 상에서 최소 비용의 경로의 휴리스틱 결정을 위한 기초 원리" 정도로 해석할 수 있겠습니다. 논문의 내용들이야 A*알고리즘에 대한 일반적인 설명(지금 시점에서는요)이지만 한가지 눈여겨 볼 부분이 있습니다. 논문 2페이지의 오른쪽 단의 하단 부분에 아래와 같은 내용이 있습니다.

We call an algorithm admissible if it is guaranteed to find an optimal path from s to a preferred goal node of s for any 8 graph. Various admissible algorithms may differ both in the order in which they expand the nodes of G, and in the number of nodes expanded.

- from "A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs", page 2

인용문의 강조 표시는 제가 했습니다. 바로 강조 표시된 부분이 유래라고 설명 될 만한 부분이죠. 일단 A*의 A가 어디서 유래했는지는 알 수 있게 되었습니다. admissible 이라는 단어에서 유래한거죠. 사전에서 그 뜻을 찾아보면 "자격이 있는" 정도로 해석되는데 적합한 혹은 최적이라는 정도의 뜻으로 이해하면 될 것 같습니다. 왜 그런 이름을 붙였는지는 모르겠지만, 일단 위키피디아에 언급된 algorithm A는 알게 되었죠. 그리고 위키피디아에 언급된 것처럼 논문에서 A*라는 단어가 처음으로 언급되는 부분은 algorithm A라고 명명했던 알고리즘에 휴리스틱한 함수를 사용하도록 하면서 A*라고 부르게 됩니다.

결론은 그냥 A 알고리즘의 발전형이라서 A*라고 부른 것 같네요.