<탐색 알고리즘 분류>
1. 맹목적 탐색 방법 (Blind Search Method)
-
목표 노드에 대한 정보를 이용하지 않고 기계적인 순서로 노드를 확장하는 방법
-
uninformed search
-
종류 : DFS (깊이 우선 탐색) / BFS (너비 우선 탐색) / 균일 비용 탐색
2. 경험적인 탐색 방법 (Heuristic Search Method)
-
목표 노드에 대한 경험적인 정보(heuristic)를 사용하는 방법
-
효율적인 탐색이 가능
-
종류 : 탐욕적인 탐색 / A* 탐색
DFS
■ 탐색 트리 상에서 해가 존재할 가능성이 있는 한 앞으로 계속 전진하여 탐색한다. 만약 더 이상 진행할 경로가 없는 경우, 이전 상태 중 다른 경로로 갈 수 있는 위치로 복귀하여 탐색을 계속한다.
■ 목표 노드가 깊은 곳에 있으면 빠르게 해를 구할 수 있지만, 반대로 해가 없는 경로로 빠지면 나오지 못할 수도 있다. 따라서 일반적으로는 최대 깊이를 설정하고, 그 깊이까지만 탐색하도록 한다.
■ 무한 반복을 피하기 위해 중복된 상태는 배제할 수 있도록 한다. 참고로 탐색에서는 중복 상태를 막기 위해 open 리스트와 closed 리스트를 사용한다.
(1) open 리스트 : 확장은 되었으나 아직 탐색하지 않은 상태들이 들어있는 리스트
(2) closed 리스트 : 탐색이 끝난 상태들이 들어있는 리스트
■ DFS에서는 open 리스트를 스택처럼 이용한다. (LIFO)
# Pseudo code
depth_first_search()
open ← [시작노드]
closed ← []
while open != [] do
X ← open 리스트의 첫 요소
if X == goal then return SUCCESS
else
X의 자식 노드 생성
X를 closed 리스트에 추가
X의 자식노드가 이미 open이나 closed에 있다면 버린다.
나머지 자식 노드들을 open의 맨 앞(위)에 추가 (stack)
return FAILBFS
■ 루트 노드의 모든 자식 노드들을 탐색한 후 해가 발견되지 않으면 한 레벨 내려가서 동일한 방법으로 탐색을 계속한다. 즉, 목표노드를 만날 때까지 가로 방향으로 진행된다.
■ 장점 : 목표 노드에 이르는 최단 경로를 찾을 수 있다. 또한, 만약 목표 노드가 존재한다면 반드시 찾을 수 있다.
■ 단점 : 한 단계씩 내려갈 수록(트리가 깊어질수록) 노드 개수가 많아져서 탐색 시간이 길어질 가능성이 높다.
■ BFS에서는 open 리스트를 큐처럼 이용한다. (FIFO)
# Pseudo code
breadth_first_search()
open ← [시작노드]
closed ← []
while open != [] do
X ← open 리스트의 첫 요소
if X == goal then return SUCCESS
else
X의 자식 노드 생성
X를 closed 리스트에 추가
X의 자식노드가 이미 open이나 closed에 있다면 버린다.
나머지 자식 노드들을 open의 맨 뒤(밑)에 추가 (queue)
return FAIL맹목적 탐색 방법은 시작 노드에서 목표 노드까지 경로를 찾기 위해 많은 시간을 소모한다. 이는 간단하기는 하지만 실제 복잡한 문제에서는 거의 쓸모가 없다. 따라서 경험적 탐색 방법(Heuristic Search Method)의 사용을 고려해야 한다.
8-puzzle 문제에 휴리스틱 정보를 이용해서 해결해보자.
(1) h1(N) = 현재 제 위치에 있지 않은 타일의 개수, 값이 작을 수록 좋은 노드이다. 빈칸은 제외
(2) h2(N) = 각 타일의 목표 위치까지의 거리, 값이 작을 수록 좋은 노드이다.
예를 들어, 위와 같이 노드가 각각 주어져 있을 때, 위는 현재 노드의 상태이고, 아래는 목표 노드의 상태이다. 이 때 h1과 h2를 각각 구해보면 다음과 같다.
h1(N) = 현재 제 위치에 없는 타일의 수 = 1 + 1 + 0 + 1 + 0 + 0 + 0 + 1 = 4
h2(N) = 각 타일이 제 위치로 찾아가기까지의 거리 = 1 + 1 + 0 + 2 + 0 + 0 + 0 + 2 = 6
■ 평가 함수(Evaluation Function) : 현재 상태를 받아 휴리스틱 값을 계산하여 반환하는 함수
Hill-Climbing Search
앞서 수행한 맹목적 탐색 방법은 무조건 정해진 순서대로 다음에 처리할 노드를 선택하였다. 하지만 각 노드를 평가하는 값이 있다면, 이를 이용해 더 빠르게 탐색을 할 수 있을 것이다. 이러한 전략 중 하나가 언덕 등반(Hill-Climbing) 기법이다. Hill-Climbing 기법에서는 평가 함수의 값이 좋은 노드(=휴리스틱 값이 작은 노드)를 먼저 처리한다.
■ 순수한 Hill-Climbing 기법
순수한 Hill-Climbing 기법은 open 리스트나 closed 리스트를 사용하지 않고 오직 h(n)만을 사용한다.
while True:
1. 노드의 확장 : 현재 위치 기준으로 각 방향의 높이를 판단
2. 목표 상태인지 검사 : 만약 모든 위치가 현 위치보다 낮다면, 현재 위치를 정상이라고 판단
3. 자식 노드 선택 : 만약 현 위치가 정상이 아니라면, 확인된 위치 중 가장 높은 곳으로 이동순수한 Hill-Climbing 기법을 사용할 경우, 생성된 자식 노드의 평가 함수 값이 부모 노드보다 더 높거나 같은 값을 갖는 경우가 나올 수 있다. 즉, 평가함수 값을 낮추는 방향으로 진행하는 것이 불가능해질 수 있다는 의미이다. 이를 "지역 최소 문제(local minimum problem)"라고 한다.
Best-First Search
최고 우선 탐색(Best-First Search)은 Hill-Climbing 기법을 약간 개선한 것이다. 여기서는 평가함수와 open / closed 리스트를 함께 사용한다. Best-First Search 기법에서는 open 리스트에 저장된 노드 중 평가함수의 값이 가장 좋은 노드를 먼저 선택한다.
Hill-Climbing 기법의 경우 생성된 자식 노드를 어딘가에 저장해두는 작업을 하지 않는다. (open, closed 리스트가 없기 때문). 따라서 한 번 선택되지 않으면 다시 고려되지 않는다. 하지만 Best-First Search에서는 open 리스트를 사용하기 때문에 처음에 선택되지 못한 노드들도 다음에 선택될 가능성을 갖게 된다.
# Pseudo code
best_first_search()
open ← [시작노드]
closed ← []
while open != [] do
X ← open 리스트에서 평가 함수 값이 제일 좋은 요소
if X == goal then return SUCCESS
else
X의 자식 노드 생성
X를 closed 리스트에 추가
if X의 자식노드가 이미 open이나 closed에 있지 않다면,
자식 노드의 평가 함수 h(n)의 값을 계산
자식 노드들을 open 리스트에 추가
return FAILA* 알고리즘
Best-First Search에서는 평가함수로 오직 h(n)만을 고려하였다. 하지만 A의 경우, 평가 함수에 "경로의 비용"까지 추가시켰다. (결국 구해야 하는 것은 최소 비용의 경로이기 때문) 따라서 A 알고리즘의 평가 함수 값을 다음과 같이 나타낼 수 있다.
f(n) = g(n) + h(n)
h(n) : 현재 노드에서 목표 노드까지의 거리
g(n) : 시작 노드에서 현재 노드까지의 비용(시작노드에서 0. 아래로 갈수록 1씩 증가)
이처럼 A* 알고리즘은 최소 비용 경로를 반환하는 것이 보장된다.
# Pseudo code
astar_search()
open ← [시작노드]
closed ← []
while open != [] do
X ← open 리스트에서 평가 함수 값이 제일 좋은 요소
if X == goal then return SUCCESS
else
X의 자식 노드 생성
X를 closed 리스트에 추가
if X의 자식노드가 이미 open이나 closed에 있지 않다면,
자식 노드의 평가 함수 f(n) = g(n) + h(n) 값을 계산
자식 노드들을 open 리스트에 추가
return FAIL[References]
- 인공지능 - 파이썬으로 배우는 머신러닝과 딥러닝-
