인공지능 4. 경험적 탐색 알고리즘

언덕 오르기 기법이 무엇인가?

인접한 노드를 평가하고, 가장 좋은 평가치만을 선택하는 탐색 기법이다. 일단 빠르다. 그리고 open 공간을 사용하지 않으므로, 메모리도 절약된다. 구현도 간단하다.

항상 좋은가? 그렇지 않다. 우리의 목표는 많은 경우 전역 최적해를 찾길 바란다. 하지만, 힐 클라이밍은 대부분 국소 최적해에 빠진다. 또, 평가치가 같으면 어떤 해가 Local Maximum인가?

만약 운 좋게 초기 위치를 잘 잡으면, Global Maximum을 찾을 수 있다. 어떻게 잘 잡는가? 시작점을 여러개 잡아서 나온 해 중에 가장 좋은 것을 선택하는 것도 개선책이 될 수 있다.

1. 시작 노드를 Current 노드로 설정한다.
2. 다음 과정을 무한 반복한다.
   1. Current 노드의 후계 노드 (인접한 노드) 중 평가치가 가장 좋은 노드를 찾는다. 이 노드를 \(n\)이라고 하자.
   2. \(\hat{h}(c) > \hat{h}(n)\)이면, 탐색을 종료한다. Local 최적해는 Current 노드이다.
   3. \(\hat{h} (c) = \hat{h}(n)\)이면, 탐색을 종료한다. Local 최적해는 Current, n 노드이다.
   4. 그렇지 않으면, Current 노드를 n으로 설정한다.

최상 우선 탐색은 무엇인가?

힐 클라이밍 기법에서, Local Maximum한 해는 찾았지만 목표 노드가 아니라면 어떻게 해야할까? 이전 분기점을 기억해뒀다가, 그 위치로 백트래킹 하는게 합리적이다. 즉, Open 공간을 사용해서 Open 공간 내의 평가치가 가장 좋은 것들을 선택해 나가는 방법이 최상 우선 탐색이다.

이전 분기를 기억하기 때문에 힐 클라이밍보다 당연히 메모리 효율이 좋지 않다. 그렇다고 찾은 해가 최적해인가? 그렇지 않다. 항상 답은 찾아 주겠지만, 비용을 고려하지 않기 때문에 최적해는 아니다.

A* 알고리즘은 무엇인가?

그럼 최적해를 찾으려면, 평가함수 뿐만 아니라 비용까지 고려하면 되지 않을까? 최상 우선 탐색에서 평가 함수를 휴리스틱 함수 + 비용 함수로 바꾼 알고리즘이 A* 알고리즘이다.

\[-f(n)= g(n) + h(n)\]

\(g(n)\)이 비용 함수, \(h(n)\)가 목적 함수다. 이제 비용을 고려하기 때문에, 항상 최적해를 찾을 수 있다. 그만큼 경험적 탐색 알고리즘 중에 제일 많은 리소스를 사용한다.

균일 비용 탐색과, A* 알고리즘은 둘 다 경로의 비용이 정의되고, 최적해를 찾아준다는 공통점이 있다. 그렇다면, 차이점이 무엇일까?

• 균일 비용 탐색은 현재 노드에서 모든 노드에 대한 최단 거리를 찾는다.
• A* 알고리즘은 현재 노드에서 목표 노드까지의 최단 거리만을 찾는다. A*가 균일 비용보다 더 효율적이다. 대부분의 경우, 균일 비용 탐색보다 A* 알고리즘을 사용하는 것이 더 낫다.

항상 A*가 좋은가?

결과만 최적이면 되는가? 찾는 과정까지 최적이어야 하는가? 에 따라 다르다. 전자의 경우 A* 알고리즘은 좋은 선택이다. 후자의 경우는 좋은 선택이 아니다. 예를 들어, 네비게이션의 경우가 있다.

또, 게임 인공지능 같은 경우 제한 시간 내의 적당한 해를 찾는 것도 중요하다. A* 알고리즘은 제한 시간 내에 적당한 해를 찾는 것은 보장해주지 않는다.

빔 탐색이 무엇인가?

최상 우선 탐색은 Open 공간에 가능한 모든 노드를 넣는다. 그렇지 말고, Open 공간에 평가치가 가장 좋은 몇 개의 노드만 들어가도록 제한해볼까? 이것이 Beam Search다.

예를 들어, 기억할 노드의 수를 2개로 제한하면 Open 공간에는 2개의 노드만 들어갈 수 있다. 그 상태에서 최상 우선 탐색을 하는거다. 기억할 노드의 수를 1로 제한하면 힐 클라이밍과 똑같다. Beam Search의 핵심은 Beam의 개수를 적당히 잘 선택하는 것이다.

그런데, 이 방법은 항상 해를 찾아주는 것을 보장해 주진 않네? 하지만 힐 클라이밍에 비해 높은 확률로 더 좋은 해를 찾을 수 있다. 그리고 최상 우선 탐색보다 메모리도 더 효율적으로 관리된다. 따라서, 경험적 탐색에서 우선적으로 고려 해볼 알고리즘이다.

beam search는 close 공간을 활용하지 않는다. 그냥 항상 가장 유망해보이는 노드 몇개만 탐색해 나간다.

적대적 탐색이란 무엇인가?

두개 이상의 에이전트가 서로 적대적인 상황일 때 탐색 기법. 둘의 전략은 같다. 본인의 이익을 최대화 하는게 목적. 적대적 탐색으론 Min-max search가 있다.