AI - 2. Search

1. 탐색

- 알파고는 deeplearning 뿐만 아니라 탐색 알고리즘을 통해 가능한 수들을 탐색하며 최적의 수를 결정한다.

2. 상태공간

- 왼쪽의 초기상태에서 타일을 옮겨 우측의 목표상태를 만든다고 가정해보자. 

- 초기상태에서 여러 연산을 거쳐 목표상태로 도달하는 과정들을 상태공간이라고 한다.

3. 탐색트리

4. Blind Search Method

- 맹목적인 탐색, 목표 노드에 대한 정보를 이용하지 않고 기계적인 순서로 노드를 확장해간다.

 

DFS

- 깊이 우선 탐색

BFS

- 너비 우선 탐색

5. Heuristic Search Method

- 목표 노드에 대한 경험적인 정보를 사용해서 노드를 확장

Hill-Climbing

- 현재 상태에서 평가함수를 통해 cost를 계산하고 이 cost가 가장 적은 노드를 먼저 처리한다.

- 탐색을 진행할 때 휴리스틱 함수 값이 가장 좋은 노드만을 선택해서 탐색을 이어간다.

- 방문여부를 체크하기 위한 open, close 리스트를 사용하지않는다.

- 오직 h(n) 값만을 사용한다. 따라서 위 그림처럼 노드가 더 이상 탐색을 진행하지 못하는 상황이 생길 수 있다.

Best First Search

- hill-climbing algorithm에서 open/closed list도 함께 사용해서 위에서 언급한 문제를 해결한다.

A*

- 평가함수를 더 개선한 방식이다.

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

- g(n) = 현재까지 움직인 타일의 수

- h(n) = 제 자리에 있지 않은 타일의 수

6. A*, BFS 구현 및 비교