[인공지능] A* 알고리즘

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

 

 

언덕 등반 기법은 지역 최대-최소 문제가 발생했다. 오로지 현재노드의 휴리스틱 정보만을 기준으로 DFS 탐색이 이루어졌기 때문이다. 지역 최대-최소 문제를 해결하기 위한 기법이 A* 알고리즘이다. 

 

 

A* 알고리즘

 

언덕 등반 기법의 단점은 시작노드에서 목표노드까지 가는 '비용'을 고려하지 않는 것이다. 그러므로 A* 알고리즘의 평가함수는 '비용'을 추가한다.

 

F(N) = G(N) + H(N)(휴리스틱 정보)

 

G(N) : 시작 노드에서 현재노드까지의 비용 

H(N) : 현재 노드에서 목표노드까지의 거리 

 

 

OPEN-CLOSED 리스트

 

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

 

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

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

 

 

A* 알고리즘

 

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

 

 

 

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

 

 

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

 

 

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

 

 

 

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

 

 

 

 

휴리스틱 값(H(N))이 좋아도 G(N)이 높으면 결국 F(N)이 커진다. 그래서 휴리스틱 값이 높아도 G(N)이 낮은 다른 노드로 탐색 루트가 바뀐다. 이렇게 시작노드에서 현재 노드 까지의 '비용'을 추가하면 지역성의 문제가 해결된다. 

 

 

이런 특성 때문에 A* 알고리즘은 최단경로 알고리즘에 사용된다. 

 

 

 

 

시작노드에서 1번 노드를 거쳐 3번 노드까지 갔다고 가정해보자. 직관적으로 다음 노드는 4번이나 5번일 것 같지만 F(N) 값이 2번 노드가 적합하다면 OPEN 리스트에서 2번 노드가 추출되어 탐색이 이루어진다.

 

4번 노드 H(N) 값이 2이고 2번노드 H(N) 값이 3이면 언덕등반기법에서는 4번 노드를 탐색한다. A* 스타 알고리즘은 G(N)도 고려하므로 4번 노드는 F(N) 값이 5이고 2번 노드는 F(N) 값이 4가 된다. 그러므로 2번 노드를 탐색한다. 이렇듯 시작노드부터 현재 노드까지의 비용을 추가하여 지역성의 문제를 해결한 알고리즘이 A* 알고리즘이다.