[인공지능] 정보 이용 탐색 (휴리스틱 탐색)

맹목적 탐색의 경우에는 공간이 크지 않을 때는 좋을 수 있다. 최적의 수를 보장할 수 있기 때문이다.

하지만 바둑과 같이 경우의 수가 커지게 되면 이를 활용하기 어렵다. 

평생 연산해도 부족할 만큼의 경우의 수가 발생하기 때문이다.

 

바둑을 두는 경우에 바둑에는 정석과 같은 수들이 있다. 즉, 확률적으로 높은 수가 있다는 이야기이다.

우리는 이러한 것들을 정보라고 보고 이를 이용해서 탐색해야 한다.

 

# 휴리스틱

휴리스틱은 그리스어에서 기원한 단어이다. 찾다, 발견하다라는 말을 뜻하는데 신속하게 어림짐작해서 찾는 것을 말한다.

사람으로 치면 직관을 이용하는 것이다. 직관을 이용하면 항상 최적일 수는 없지만 빠른 시간 안에 괜찮은 결과가 나온다.

컴퓨터도 이와 비슷한 방식을 이용한다.

 

우리의 관심 사는 어떤 노드를 먼저 확장해야 빨리 목표 상태에 도달할 수 있는지이다. 

특정 상태에서 목표 상태까지의 거리에 대한 정보를 제공하는 것을 의미한다.

 

휴리스틱은 설정하기 나름이라 문제마다 적당한 휴리스틱을 찾아 사용해야 한다.

어떤 휴리스틱을 사용하는가에 따라서 탐색 성능 차이가 날 수 있는 것이다. 

 

## 언덕 오르기 방법

언덕 오르기 방법은 현재 노드에서 확장 가능한 이웃 노드들 중에서 휴리스틱에 의한 평가값이 가장 좋은 것 하나만을 선택해서 확장해 가는 탐색 방법이다.

 

여러 개의 확장 중인 노드를 관리하지 않고, 현재 확장 중인 노드만을 관리한다. 때문에 그리디 알고리즘이라고 부르기도 한다.

휴리스틱 탐색을 통해서 어떤 노드가 가장 좋을 지를 평가하고 가장 좋은 이웃노드를 확장 시킨다. 그리고 이 과정을 반복한다.

 

하지만 이 방법의 경우에 국소적인 최적해, Local Optimal Solution에 빠질 위험이 있다. 

초기 설정이 없다면 초기 설정을 바꾸어 가면서 최적해를 찾을 가능성을 높일 수 있다고 한다.

 

## 최상 우선 탐색

최상 우선 탐색은 확장 중인 노드 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색하는 것이다. 

 

하지만 당연하게도 남은 거리를 정확하게 알 수 없으니까 휴리스틱을 사용하여 추정한다. 이것 또한 얼마나 좋은 휴리스틱을 사용하는 가에 따라서 결과가 달라진다.

 

예를 들어서 8 퍼즐 문제가 있다.

 

 

다음과 같은 퍼즐을 8 퍼즐이라고 하는데 본 적이 있을 것이다. 

여기서 목표 상태와 다른 퍼즐의 개수를 거리라고 두고 진행하는 것이 휴리스틱의 일종이다. 

 

이를 하나 하나 움직였을 때 거리가 줄어드는 방향으로  움직이는 것이다.

 

## 빔 탐색

빔 탐색의 경우에는 최상 우선 탐색을 적용할 때, 탐색 트리의 깊이가 깊어지면서 확장 되는 노드의 개수가 너무 많아져서 메모리에 대한 부담이 커지기 때문에 사용한다. 

 

빔 탐색은 휴리스틱에 의해 평가값이 우수한 일정 개수의 노드만을 탐색하는 것이다. 가망이 없어 보이는 노드를 떨군다고 생각하면 될 것이다.

 

이렇게 하면 메모리를 효율적으로 사용할 수 있어서 만약 트리 구조가 커지면 이러한 방법을 사용하는 모양이다. 

 

## A* 알고리즘

정말 많이 사용하는 알고리즘인 것 같다. 

 

추정한 전체 비용을 최소로 하는 노드를 확장하는 알고리즘이다. 

 

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

 

이 식을 사용한다. g(n) 은 이미 투입된 비용이고 h(n)은 앞으로 남은 비용이다.

하지만 이 역시 남은 비용을 정확하게 계산하는 것은 불가능할 수 있다 (경우의 수가 너무 커서).

때문에 우리는 휴리스틱을 사용하는데 이 때의 휴리스틱 함수는 개발자가 만들어야 한다. 

 

이 휴리스틱 함수가 항상 실제 남는 비용보다 적거나 같으면 최적해를 찾는다고 한다. 

휴리스틱 함수는 개발자가 어떻게 만드느냐에 따라 달라지므로 우리는 이것을 어떻게 만들지 고민해야 한다.