[탐색 알고리즘] BFS, DFS, 반복적 깊이 심화, 양방향 탐색, 균일 비용 탐색 특징

1. 탐색

• 문제에 대한 최적의 해를 찾기 위하여 상태 공간을 체계적으로 찾아보는 것
• 초기상태에서 시작하여 목표상태에 도달할 수 있게 하는 일련의 연산자를 찾는 것
• 최적의 해는 일련의 동작이나 하나의 상태로 구성된다.

 

2. 상태공간의 표현

• 방향성 그래프를 이용한 상태공간의 표현
  • 노드 – 상태
  • 아크 – 연산자
  • C(N_i, N_j) : N_i 노드와 N_j 노드 사이의 경로에 소요되는 비용

 

3. 탐색의 종류

• 탐색/최적화
  • 탐색
    • 맹목적 탐색 : 정해진 순서에 의해 탐색
    • 경험적 탐색 : 정해진 순서+경험(=정보)활용
    • game tree search : winner-loser 개념 이용
  • 최적화
    • 조합 최적화 : 해의 조합을 이용하여 탐색
    • 함수 최적화 : 목적함수 최적화를 이용하여 탐색

 

4. 탐색 中 맹목적 탐색

• 정해진 순서에 따라 상태공간 그래프를 점차 생성해가면서 해를 탐색하는 기법
  • 깊이 우선 탐색 (DFS : depth first search)
  • 너비 우선 탐색 (BFS : breath first search)
  • 반복적 깊이심화 탐색 (iterative-deepening search)
  • 양방향 탐색 (bidirectional search)
  • 균일 비용 탐색 (uniform-cost search)

 

5. 탐색 中 맹목적 탐색 中 깊이우선탐색 (DFS)

• 해가 존재할 가능성이 존재하는 한 앞으로 전진 (깊이 방향으로 탐색)
• 최근에 생성된 노드를 다시 확장하는 기법 (stack – LIFO, FILO 사용)
• 메모리 효율적 👍
• 최적해 보장하지 못함 👎
  

출처 : http://www.aistudy.com/heuristic/iterative_deepening_dfs.htm

6. 탐색 中 맹목적 탐색 中 너비우선탐색 (DFS)

• 초기 노드에서 시작하여 모든 자식 노드를 확장하여 생성한다.
• 생성된 노드 순서대로 확장한다 (queue – FIFO, LILO)
• 메모리 비효율적 👎
• 최적해 보장 👍

    

7. 탐색 中 맹목적 탐색 中 반복적 깊이 심화 (추천⭐)

• 깊이 한계가 있는 DFS를 반복적으로 수행
• 메모리 효율적 👍(DFS보다는 비효율적이나, BFS보다 효율적)
  • DFS보다는 비효율적이나, 실제 비용이 DFS에 비해 크게 늘지 않는다.
• 최적해 보장 👍
• DFS + BFS의 장점만을 취하는 알고리즘
• 맹목적 탐색 수행한다고 하면 보통 이것을 우선적으로 수행

 

8. 탐색 中 맹목적 탐색 中 양방향 탐색

• 초기 노드와 목적 노드에서 동시에 BFS 진행
• 중간에 만나는 노드가 생길 때까지 확장
• 메모리 효율적 😊 (기존 BFS보다는 효율적이라는 의미)
• 최적해 보장 😊

 

9. 탐색 中 맹목적 탐색 中 균일비용탐색

• 비용이 명시된 문제에서의 맹목적 탐색 기법
• 출발 노드로부터 경로 비용이 최소인 노드를 선택하여 확장
• 최적해를 보장하지는 못한다.
• 비용 함수 g(n_i) = g(n)+C(n, n_i)