2. 탐색과 최적화 - 맹목적 탐색

탐색

: 문제의 해가 될 수 있는 것들의 집합을 공간으로 간주, 

문제에 대한 최적의 해를 찾기 위한 공간을 찾는 것

 

상태 공간

: 초기 상태로부터 도달할 수 있는 모든 상태들의 집합

문제의 해가 될 가능성이 있는 모든 상태들의 집합

 

상태 공간 그래프

: 상태 공간에서 각 행동에 따른 상태의 변화를 나타낸 그래프

 

맹목적 탐색 

: 정해진 순서에 따라 상태 공간 그래프를 생성해 가며 해를 탐색하는 방법

• 깊이 우선 탐색
• 너비 우선 탐색
• 반복적 깊이심화 탐색
• 양방향 탐색

 

 

1) 깊이 우선 탐색(depth-first search, DFS)

• 백트랙킹이 주로 이 방법 사용
• 깊이 방향으로 탐색
• 메모리 공간 사용 효율적 
• 최단 경로 해 탐색 보장 불가 ( 무한 루프 가능성)

 

2) 너비 우선 탐색(breadth-first search, BFS)

• 목표 노드를 찾을 때까지 같은 깊이의 모든 자식 노드를 확장하며 탐색
• 최단 경로 해 탐색 보장 
  단, 모든 링크의 길이/비용이 동일한 경우만
• 메모리 공간 사용 비효율

 

3) 깊이 제한 탐색(depth-limited search)

• DFS는 무한루프에 빠질 수 있다는 단점이 있음
• 이를 극복하기 위해 깊이에 한계를 두고 탐색
• 한계 L을 정해놓고 현재 깊이가 L에 도달하면 더 깊은 노드는 탐색하지 않고
  부모 노드로 되돌아 감

 

4) 반복적 깊이심화 탐색(iterative-deepening search)

• 깊이 제한 탐색을 반복적으로 적용
• 한계 L까지 탐색 후 목표 상태를 찾을 때까지 한계 L+1을 반복 탐색
• 최단 경로 해 탐색 보장 
  단, 모든 링크의 길이/비용이 동일한 경우만
• 메모리 공간 사용 효율적
  실제 비용이 크게 늘지 않음
  -> 각 노드가 10개의 자식노드를 가질 때, BFS 대비 약 11% 추가 생성
• 맹목적 탐색 적용 시 우선 고려 대상

 

5) 양방향 탐색(bidirectional search)

• 초기 노드와 목적 노드에서 동시에 너비 우선 탐색을 진행
• 중간에 만나도록 하여 최단 경로를 찾는 방법