인공지능은 어떻게 수많은 선택지 중에서 가장 빠른 길을 찾아낼까요?
퍼즐을 풀며 똑똑한 탐색의 원리를 알아봅시다.
모든 길을 다 가보는 '무지성 탐색'은 너무 오래 걸립니다. A* 알고리즘은 두 가지 정보를 합쳐 다음 단계를 결정합니다.
출발지에서 현재 퍼즐 상태까지 오는데 걸린 이동 횟수입니다.
현재 상태에서 정답까지 얼마나 남았는지 예측하는 '휴리스틱'입니다.
※ 8퍼즐에서는 보통 각 숫자가 제자리에서 얼마나 멀리 떨어져 있는지(맨해튼 거리)를 h(n)으로 사용합니다.