[인공지능] 언덕 등반 기법 (Hill-Climbing)

 

경험적인 탐색 방법

 

정보를 기반으로 탐색하는 알고리즘이다. 휴리스틱 정보(Heuristic Information)를 이용하여 휴리스틱 탐색 방법으로도 불린다. ( * 휴리스틱 정보 : 사람이 유용할거라 판단한 정보 )

 

 

휴리스틱 정보(Heuristic Information)

 

 

현재상태와 목표상태가 주어졌다. 여기서 휴리스틱 정보를 뽑아보자.

 

h1(N) : 현재상태를 목표 상태와 비교했을 때, 목표상태와 일치하지 않은 현재상태의 타일의 개수 

2, 1, 8, 4 타일은 목표상태와 위치가 다른 타일이다. 그러므로 h1(N)은 4가 된다.

 

h2(N) : 각 타일의 목표 위치간 거리

2, 1, 8, 4 타일이 목표 위치와 얼마나 떨어져 있는지 계산해야 한다.

 

 

2 와 1은 한 칸, 8 과 4는 두 칸이므로 h2(N)은 6이다. 

 

 

언덕등반기법(Hill-Climbing)

 

DFS 탐색기법에서 휴리스틱 정보가 좋은 노드부터 탐색하는 기법이다. 

 

 

 

OPEN-CLOSED 리스트

 

확장이 가능한 상태(노드)는 동적으로 생성된다. 동적으로 생성된 노드 중 이미 탐색했던 상태와 동일한 상태가 존재할 수 있다. 동일한 상태를 검사하는 오버헤드를 줄이기 위해 두 가지 리스트를 사용한다. 

 

- OPEN 리스트 : 확장은 되었으나 탐색되지 않은 상태 리스트

- CLOSED 리스트 : 탐색이 끝난 상태 리스트

 

 

언덕등반 기법 알고리즘

 

1. OPEN 리스트에 시작 노드를 넣는다.

 

 

 

2. 탐색과정은 OPEN 리스트가 비워지거나 목표 노드를 찾을 때까지 반복(while)된다. 

 

 

3. OPEN 리스트에서 H(N)이 가장 낮은 노드를 가져온다. 목표 노드가 아니라면 자식 노드를 생성하여 확장한다.

 

 

 

4. 생성된 자식노드는 OPEN리스트와 CLOSED 리스트에서 중복검사를 한 후 중복되지 않으면 OPEN리스트에 추가한다. 부모 노드는 CLOSED 리스트에 추가한다. 

 

 

 

5. OPEN 리스트에서 H(N)이 가장 낮은 노드를 가져온 뒤 위 과정을 반복한다.

 

 

 

 

 

지역 최대 최소 문제

 

 

 

언덕등반 기법은 오로지 휴리스틱 정보(H(N))만 이용한 DFS이다. 위 그림 같이 탐색과정이 길어진다면 목표 상태를 탐색하는 '비용'이 커져버린다. 목표상태를 찾더라도 최적의 방법이 아닐 수도 있다. 언덕 등반 기법은 시작노드에서 목표 노드까지 가는 '비용'을 고려하지 않은 알고리즘이다. 단순히 현재노드에서 휴리스틱정보만을 기준으로 판단하기에 지역성(local)의 문제가 나타난다.

 

이런 취약점을 보완하기 위한 알고리즘이  A* 알고리즘이다. 이는 다음 포스팅에서 다루겠다.