A* 알고리즘, IDA* 알고리즘

학교에서 인터넷 프로그래밍 및 실습 강의에서 과제로 슬라이딩 퍼즐을 푸는 알고리즘을 구현해본 적이 있다.

• 당시 코드

이번에 모 기업의 지원서를 쓰면서 그때의 경험을 썼는데 이번 기회에 당시 과제를 해결하면서 사용했던 알고리즘인 A, IDA 알고리즘에 대해 정리하고, 슬라이딩 퍼즐 Solver를 다시 구현해보려고 한다.

A* 알고리즘

A Star 알고리즘이라고 읽으며 최단 경로를 탐색하는데 사용하는 알고리즘이다.

시작 노드를 정해 다른 모든 노드에 대해 최단 경로를 찾는 Dijkstra 알고리즘과는 달리 시작 노드와 도착 노드를 설정하고, 이 두 노드간의 최단 경로를 찾는 알고리즘이다.

그 당시 과제에서는 슬라이딩 퍼즐의 상태 하나하나를 노드로 보고 퍼즐이 섞인 상태를 시작 노드로, 퍼즐이 맞춰진 상태를 도착 노드로 보고 알고리즘을 적용하였다.

동작 과정은 다음과 같다.

1. 시작 노드를 닫힌 목록 (Close List)에 추가한다.

2. 시작 노드와 연결된 노드들은 열린 목록 (Open List)에 추가한다. 이때 알고리즘에서 사용할 휴리스틱 값과 부모 노드가 무엇인지도 함께 넣어주어야 하는데, 그때 과제에서는 휴리스틱 추정값으로 맨해튼거리, 정답과 타른 타일의 개수, 선형 충돌 3가지 방식을 사용하였다. 이에 대해선 뒤에서 자세하게 서술한다.

3. 열린 목록의 휴리스틱 값이 가장 작은 노드를 닫힌 목록에 추가하고, 이 노드와 연결된 노드들을 열린 목록에 추가한다.