[인공지능] 탐색(Search) 요약

맹목적 탐색: 정해진 순서에 따라 상태 공간 그래프를 점차 생성해 가면서 해를 탐색 하는 방법

 

깊이 우선 탐색 (DFS)

해가 존재할 가능성이 존재하는 한 앞으로 계속 전진, 즉 깊이 방향으로 탐색

• 최근에 생성된 노드를 가장 먼저 확장 • 노드의 깊이

• Root node의 깊이는 1
• 자손인 노드의 깊이 = 부모노드의 길이 + 1 • 백트래킹(backtracking)을 위해 깊이 제한을 둔다.

DFS의 알고리즘

1. 출발노드를 OPEN에 넣는다.
2. OPEN에 노드가 남아있는 동안 다음을 반복한다.
   1. OPEN의 제일 앞에 있는 노드를 꺼내어 CLOSED에 넣는다.(이 노드를 n이라고 부름)
   2. n의 길이가 깊이 제한에 도달하지 않았다면 다음을 실행한다.
      1. 노드 n을 확장하여 모든 후계노드를 생성
      2. 생성된 후계노드들에게 부모노드 n을 가리키는 포인터를 첨부한다.
      3. 만일 후계노드 중 목표노드가 존재하면 포인터를 역으로 추적하여 경로를 구성하고, 탐색을 성공적으로 끝낸다.
      4. 후계노드를 OPEN의 앞에 넣는다.
3. 탐색은 실패로 끝난다.

OPEN이라는 리스트에서 노드를 꺼내는 순서

• 삽입된 순서의 역순(나중에 생성된 것이 먼저 확장) → OPEN은 스택 구조

 

넓이 우선 탐색 (BFS)

 

초기 노드에서 시작하여 모든 자식 노드를 확장하여 생성, 이 때 생성된 순서대로 노드를 확장 • 목표 노드가 없으면 단말노드에서 다시 자식 노드 확장 • 넓이우선 방법은, 출발노드에서 목표노드까지의 최단길이경로(shortest-length path)를 찾는 것 을 보장 • 목표 상태를 찾을 때까지 생성된 모든 노드를 관리하기 위해 많은 기억공간을 필요로 함

 

BFS의 알고리즘

1. 출발노드를 OPEN에 넣는다.
2. OPEN에 노드가 남아있는 동안 다음을 반복한다.
   1. OPEN의 제일 앞에 있는 노드를 꺼내어 CLOSED에 넣는다.(이 노드를 n이라고 부름)
   2. n의 길이가 깊이 제한에 도달하지 않았다면 다음을 실행한다.
      1. 노드 n을 확장하여 모든 후계노드를 생성
      2. 생성된 후계노드들에게 부모노드 n을 가리키는 포인터를 첨부한다.
      3. 만일 후계노드 중 목표노드가 존재하면 포인터를 역으로 추적하여 경로를 구성하고, 탐색을 성공적으로 끝낸다.
      4. 후계노드를 OPEN의 뒤에 넣는다.
3. 탐색은 실패로 끝난다.

OPEN으로부터 노드를 꺼내는 순서는, DFS와 반대로 삽입된 순서와 동일.

→ OPEN은 큐 구조

 

반복적 깊이심화 탐색

깊이 한계가 있는 깊이 우선 탐색을 반복적으로 적용 → DFS와 BFS의 장점만을 이용해 탐색하는 과정

→ 깊이가 2라고 친다면, 깊이 2까지 일단 DFS를 했다가 바로 가지 않았던 부분으로 넘어가면 된다.

 

양방향 탐색

초기 노드와 목적 노드에서 동시에 너비 우선 탐색을 진행 • 초기상태와 목표상태를 기준으로 너비우선 탐색을 번갈아 가면서 한 단계씩 탐색 범위를 확장 • 중간에 만나는 노드가 생길 때까지 진행 • 너비 우선 탐색과 같이 최적해를 보장하면서 메모리 공간과 시간을 절약

 

 

지금까지의 탐색들을 서로 비교해보자

 

깊이 우선 탐색(DFS)

• 메모리 공간 사용 효율적
• 최단 경로 해 탐색 보장 불가

넓이 우선 탐색(BFS)

• 최단 경로 해 탐색 보장
• 메모리 공간 사용 비효율적

반복적 깊이심화 탐색

• 최단 경로 해 보장
• 메모리 공산 사용 효율적
• 반복적인 깊이 우선 탐색에 따른 비효율성, 그러나 실제 비용이 크지 늘지 않음
  • 각 노드가 10개의 자식 노드를 가질 때, BFS 대비 약 11% 정도 추가 노드 생성
• 맹목적 탐색 적용시 우선 고려 대상

양방향 탐색

• 최단 경로 해 탐색 보장
• BFS 대비 메모리공간과 시간 사용 효율적

---

 

균일 비용 탐색

 

비용이 명시된 문제에서의 맹목적 탐색 기법

균일비용 탐색은 출발노드로부터 경로비용이 최소인 노드를 선택하여 확장

탐색과정에서 어떤 노드를 확장시켜 후계노드가 생성되었다고 가정하자.

후계노드를 ni(i = 1, 2, … , m)이라고 할 때 경로비용은

g(ni) = g(n) + C(n, ni)

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

C(n, ni): 노드 n부터 노드 ni로 이동하는데 소비되는 비용

 

알고리즘

1. OPEN에 출발노드를 넣는다. 출발노드의 비용은 0
2. OPEN에 노드가 남아 있는 동안 다음을 반복.
   1. OPEN의 제일 앞에 있는 노드를 꺼내어 CLOSED에 넣는다. 이 노드를 n이라고 한다.
   2. 노드 n이 목표 노드라면 탐색은 성공적으로 끝난다. 포인터를 역으로 추적하면 탐색 경로를 얻을 수 있다.
   3. 노드 n을 확장하여 후계노드 n1, n2, …, ni를 생성한다. 이를 후계노드에 부모 노드인 노드 n을 가리키는 포인터를 첨부
   4. 후계노드 n1, n2 … ,ni의 경로비용을 식에 의해 계산한다.
   5. 각각의 후계노드 ni에 대하여 다음을 수행
      1. ni와 동일한 노드가 OPEN에 존재하고, 그 노드의 경로비용이 ni의 경로비용보다 크다면 그 노드를 ni로 대치하고, 그렇지 않으면 ni는 무시
      2. ni와 동일한 노드가 CLOSED에 존재한다면 그 노드의 경로비용은 ni의 경로비용보다 작다. 따라서 ni는 무시한다.
      3. ni와 동일한 노드가 OPEN이나 CLOSED에 존재하지 않으면 ni를 OPEN에 첨가한다.
   6. OPEN에 저장된 노드들을 경로비용의 오름차순으로 정렬한다.

 

경험적 탐색 방법(Informed Search)

 

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

 

휴리스틱(heuristic)

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

목적함수(evaluatioin function)

• 노드의 선택 순서를 조정하기 위해 각 노드의 바람직한 정도를 평가하기 위한 함수
• 특정상태에서 목표상태까지의 거리
• 실제로는 h(n)의 예측치 h^(n)을 사용 ( ^가 h 위에 올라가는 모양이어야 한다.)
• 최단경로 문제에서는 현재 위치에서 목적지까지의 거리,
• 8-퍼즐 문제에서는 제자리에 있지 않는 타일의 개수가 예시가 될 수 있다.

경험적 탐색 방법에는 언덕오르기 기법(hill-climbing), 최상우선탐색(best-first search), 빔 탐색, A* 알고리즘이 있다.

 

 

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

 

목적 함수

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

지역 탐색(local search)

• 현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드 하나를 골라서 확장하는 탐색 방법
• 국소 최적홰(local optima)에 빠질 가능성이 높다.

언덕 오르기 방법의 알고리즘

1. OPEN에 출발노드를 넣는다.
2. OPEN에 노드가 남아 있는 동안 다음을 반복
   1. OPEN의 제일 앞에 있는 노드를 꺼내어 CLOSED에 넣는다. (이 노드는 n)
   2. 노드 n을 확장하여 후계노드 n1, n2, … , ni를 생성한다. 후계노드에 부모노드인 노드 n을 가리키는 포인터를 첨부한다.
   3. 후계노드가 존재한다면
      1. 후계노드 중 목표노드가 있는지 검사한다. 만일 목표노드가 존재하면 탐색은 성공적으로 끝난다.
      2. 후계노드의 평가함수를 계산한다.
      3. 후계노드를 OPEN의 앞에 넣는다. 이 때 가장 유망한 후계노드를 앞에 넣는다.(이번에 생성된 후계노드만 정렬하여 넣음)
3. 탐색은 실패로 끝난다.

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

Informed search의 가장 기본적인 접근, Greedy search

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

OPEN 리스트 관리

• 리스트 내에 모든 노드를 평가함수 값에 따라 정렬해둔다. - 가장 유망한 노드가 OPEN의 제일 앞에 위치

확장순서

언덕오르기 방법 - 현재 진행 방향의 후계노드 중에서 가장 유망한 노드를 확장

최적 우선 탐색 - 전체 노드를 대상으로 가장 유망한 노드를 확장

 

빔 탐색(beam search)

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

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

• 예시: 기억 노드의 수를 2로 제한

 

A* Search

각각의 노드에 대한 평가함수를 다음과 같이 정의한다.

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

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

h(n): 노드 n으로부터 목표 노드까지의 경로 비용 (추정치 사용)

A* Search는 최소 비용을 보장한다.

 

8-퍼즐에서

g(n): 조각을 이동시키는데 소요되는 비용

h(n): 각 노드에서 제 위치에 존재하지 않는 조각의 수

 

 

다시, 휴리스틱(경험)을 이용한 탐색 기법은 3가지가 있다.

• 언덕 오르기 방법 (hill-climbing)
• 최상 우선 탐색 (best-first search)
• A* search

이 기법들은 Memory bounded heuristic search로 발전한다.

실제 최적화/탐색 문제에서 활용되는 탐색 기법은 위의 세 가지 기법과 더불어

• 유전자 알고리즘 (genetic algorithm)
• Simulated annealing

도 있다.