[Search] 정보이용 탐색

1 minute read

개요

지난 탐색 포스팅에서 맹목적 탐색에 대해 알아보았습니다.

이번에 알아볼 탐색의 종류는 정보이용 탐색으로, 휴리스틱 탐색이라고도 하는 탐색 기법입니다.

정해진 규칙에 따라 탐색을 진행하는 맹목적 탐색과 달리, 정보이용 탐색은 앞으로 남은 거리에 대한 정보를 이용합니다.

이 때의 정보는 실제 남은 거리에 대한 것이 아니라, 남은 거리에 대한 예측값입니다.

그리고 예측을 할 때 시간 또는 정보가 불충분하여 정확한 판단보다는 신속한 판단이 요구될 때 어림짐작 식으로 판단하는 것을 휴리스틱이라 합니다.

예를 들어 지도 상의 최단 경로 문제에서 목적지까지의 실제 경로의 길이가 아닌 직선 경로의 길이를 정보로 사용하는 경우 등이 그렇습니다.

언덕 오르기 방법(hill climbing method)은 다음과 같습니다.

매 위치마다 연결된 노드들 중 가장 최적의 노드로 이동하는 그리디 알고리즘의 일종이며, 목적지를 향해 다가가는 것이 언덕을 오르는 것과 비슷하다 하여 언덕 오르기 방법이라고 불립니다.

최상 우선 탐색(best-first search)은 다음 특징을 갖습니다.

빔 탐색(beam search)은 앞서 살펴본 최상 우선 탐색에 더하여 휴리스틱에 의한 평가값이 우수한 일정 개수(K)의 이웃 노드만을 탐색하는 방법입니다.

확장 노드의 개수에 제한을 둠으로써 메모리를 효율적으로 관리할 수 있지만, 원하는 답을 찾지 못하게 될 수도 있습니다.

마지막 정보이용 탐색 방법으로 A* 알고리즘(A star algorithm)이 있습니다.

A* 알고리즘은 지금까지 온 경로의 비용도 판단의 기준에 포함시킨다는 점에서 앞서 살펴본 방법들과 차이가 있습니다.

이 알고리즘에서 사용하는 수식은 다음 모양과 같습니다.

f’(n) = g(n) + h’(n)

여기서 g(n)은 현재 노드까지 오는데 사용된 비용인 실제 값이고, h'(n)은 현재 노드에서 목적지 노드까지 가는 비용에 대응하는 휴리스틱 함수, 즉 예측 값입니다.

g(n)과 h'(n)을 이용하여 f'(n)을 구함으로써 판단의 기준으로 사용하는 것입니다.

다음은 A* 알고리즘을 이용하여 8-puzzle 문제를 푸는 모습을 나타낸 것입니다.