[인공지능] 경험적 탐색

반복적 깊이 심화 탐색

 

깊이 한계가 있는 깊이 우선 탐색을 반복적으로 적용하는 방법으로,

메모리 사용이 최적화된 DFS와 최적해를 탐색하는 것이 보장되어있는 BFS의 장점만을 이용해 탐색하는 과정이다.

 

시간을 조금 걸릴 수 있지만,

메모리의 사용량을 줄이고, 최적해를 찾을 수 있다는 장점이 있다.

 

반복적인 깊이 우선 탐색에 따른 비효율성이 클 수 있지만,

실제 비용이 크게 늘지는 않는다.

• 각 노드가 10개의 자식 노드를 가질 때, BFS대비 약 11%의 정도의 추가 노드 생성

반복적 깊이 심화 탐색

 

양방향 탐색

 

초기 노드와 목적 노드에서 동시에 너비 우선 탐색을 진행하는 방법으로,

초기 상태와 목표 상태를 기준으로 너비 우선 탐색을 번갈아 가면서 한 단계씩 탐색 범위를 확장한다.

 

중간에 만나는 노드가 생길 때까지 진행하기 때문에,

너비 우선 탐색과 같이 최적해를 보장하면서 메모리 공간과 시간을 절약할 수 있다.

양방향 탐색

 

경험적 탐색 방법 (Informed Search)

 

상태 공간에 대한 정보를 이용하여 탐색 효율을 높이는 탐색 (heuristic search)

 

휴리스틱 (heuristic)

• 찾다, 발견하다의 그리스어
• 시간이나 정보가 불충분하여 합리적인 판단을 할 수 없거나, 굳이 체계적이고 합리적인 판단을 할 필요가 없는 상황에서 어림짐작 하는 것
• 어떤 노드를 먼저 확장해야 목표 상태에 빨리 도달할 수 있는지를 고려, 즉 특정 상태에서 목표 상태까지의 거리에 대한 정보 제공
• 검색 효율을 고려, 최적해를 찾는다는 보장은 없음

 

목적 함수 (evaluation function)

• 노드의 선택 순서를 조정하기 위해 각 노드의 바람직한 정도를 평가하기 위한 함수
• 특정 상태에서 목표 상태까지의 거리
• 휴리스틱

 

목적 함수의 예

• 최단 경로 문제: 현재 위치에서 목적지까지의 직선 거리
• 8-퍼즐 문제: 제자리에 있지 않는 타일의 개수

 

언덕 오르기 방법 (hill-climbing)

 

목적 함수

• 목표 노드까지의 경로 비용 h(n)을 선택의 기준으로 사용
• 현재 상태까지 도달하는데 소비한 경로비용은 무시하고, 앞으로 남은 목표까지의 비용만을 고려

 

지역 탐색

• 현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드 하나를 확장해 가는 탐색 방법
• 국소 최적해 (local optima) 에 빠질 가능성이 높음
• 주로 uni-modal 문제에서 사용하는 방법
• multi-modal 문제의 경우 초기값만 잘 준다면 굉장히 빠르게 풀 수 있다는 장점이 있음

국소 최적해

 

최상 우선 탐색 (best-first search)

 

Informed search의 가장 기본적인 접근으로 Greedy search이다.

 

노드로부터 목표노드까지 도달하는 과정에 대한 비용의 예측치를 평가함수로 사용한다.

 

Open 리스트를 관리한다는 점에서 언덕 오르기 방법과는 다른데,

리스트 내의 모든 노드를 평가 함수 값에 따라 정렬해 둔다.

이와 같이 하여 가장 유망한 노드가 Open의 제일 앞에 위치하게 한다.

 

그렇기 때문에 메모리에 부담이 큰 방법이기도 하다.

하지만, local optima에 빠질 수도 있다. (휴리스틱에 따라 다르다.)

최상 우선 탐색

 

빔 탐색 (beam search)

 

휴리스틱에 의한 평가값이 우수한 일정 개수의 확장 가능한 노드만을 메모리에 관리하면서 최상 우선 탐색을 적용한다.

 

Best-first search에서 기억 노드의 수를 제한하는 방법이다.

즉, local optima에 빠질 가능성이 존재한다.

빔 탐색

 

A* Search

 

A* 알고리즘은 출발 노드로부터 목표 노드까지의 최적경로를 탐색하기 위한 것이다.

이를 위해서는 각각의 노드에 대한 평가 함수를 다음과 같이 정의한다:

 

평가함수 f(n) = g(n) + h(n)

g(n): 출발 노드로부터 노드 n까지의 경로 비용

h(n): 노드 n으로부터 목표 노드까지의 경로 비용 (휴리스틱)

 

따라서 최소 비용을 보장한다.

A*

 

휴리스틱 함수 정의를 위해 고려할 사항

 

• Admissibility (허용성)
  • 객관적인 휴리스틱을 설정
• Consistency (일관성)
  • Monotonicity
  • h(n) < h(n+1) + c(n, n+1)