[인공지능] 탐색과 최적화 - 맹목적 탐색

탐색(Search) = 문제의 해(Solution)가 될 수 있는 것들의 집합을 공간(Space)으로 간주하고 문제의 최적해를 찾기 위해 공간을 체계적으로 찾는 것.

• 상태(State) = 특정 시점에 문제의 세계가 처해있는 모습.
• 세계(World) = 문제에 포함된 대상들과 이들의 상황을 포괄적으로 지칭하는 말.
• 해(Solution) = 문제의 요구조건을 최적으로 만족하는 것.
• 상태 공간(State space) = '문제의 초기 상태로부터 도달할 수 있는 모든 상태의 집합', '문제의 해가 될 가능성이 있는 상태들의 집합'
  • 초기 상태(Initial state) = 문제가 주어진 시점의 시작 상태
  • 목표 상태 = 문제에서 원하는 최종 상태
• 상태 공간 그래프(State space graph) = 상태 공간에서 각 행동에 따른 상태의 변화를 나타낸 그래프.

맹목적 탐색(Blind search) = 문제의 상태 공간 정보를 이용하지 않고 정해진 순서에 따라 공간 그래프를 점차 생성해 가면서 해를 찾는 방법.

• 깊이 우선 탐색(depth-first search, DFS)
  • 초기 노드에서 시작하여 깊이 방향으로 탐색
  • 목표 노드에 도달하면 종료
  • 더 이상 진행할 수 없으면, 백트래킹(backtracking, 되짚어가기)
  • 방문한 노드는 재방문하지 않음
  • 메모리 공간 사용 효율적
    • 최단 경로 탐색 보장 불가 (무한 루프 가능성)
• 너비 우선 탐색(breadth-first search, BFS)
  • 초기 노드에서 시작하여 모든 자식 노드를 확장하여 생성
  • 목표 노드가 없으면 단말 노드에서 다시 자식 노드 확장
  • 최단 경로 해 탐색 보장
  • 메모리 공간 사용 비효율
• 반복적 깊이 심화 탐색(iterative-deepening search)
  • DFS는 메모리에 대한 부담은 적지만 최단 경로를 찾는다는 보장이 없고, BFS는 메모리에 대한 부담은 크지만 최단 경로를 찾는다는 것을 보장한다. 반복적 깊이 심화 탐색은 이 두 탐색 방법의 장점을 취한 것이다.
  • 깊이 한계가 있는 DFS를 반복적으로 적용하는 방법
  • 탐색 깊이 한계(Search depth limit)를 0에서 시작하여 점차 1씩 증가시켜 가면서 깊이 우선으로 탐색하여 최단 경로를 찾는 것을 보장한다.
  • 메모리 부담이 적다
  • 반복적으로 노드들이 생성되기 때문에 비효율적인 면이 있으나, 실제로는 비용이 크게 증가하지 않음. (각 노드가 10개의 자식 노드를 갖는 탐색 트리의 경우라도 BFS에 비해 약 11% 정도의 노드를 더 많이 생성하는 정도에 불과하다.)
  • 맹목적 탐색을 해야 하는 상황에서는 반복적 깊이 심화 탐색 방법을 우선적으로 고려하는 것이 바람직하다.

DFS	BFS	iterative-deepening search
메모리 공간 사용 효율적	최단 경로 해 탐색 보장	최단 경로 해 탐색 보장
		메모리 공간 사용 효율적
최단 경로 탐색 보장 불가 (무한 루프 가능성)	메모리 공간 사용 비효율적	반복적인 DFS에 따른 비효율성 * 실제 비용이 크게 늘지 않음. (각 노드당 자식 노드가 10개면 BFS대비 11%↑)
		맹목적 탐색 적용시 우선 고려 대상

※BFS와 iterative-deepening search의 경우 링크당 비용(가중치)이 다를 경우 '최적해'를 찾는다는 보장이 없다.

 

양방향 탐색(bidirectional search)

• 초기 노드와 목적 노드에서 동시에 BFS를 진행.
• 중간에 만나도록 하여 초기 노드에서 목표 노드로의 최단 경로를 찾는 방법.
• 메모리 공간 사용 효율적 (노드당 자식 노드가 10개라고 가정할 경우, BFS에서 10²⁰개의 노드를 생성한다면, 양방향 탐색에서는 2*10¹⁰개의 노드만 생성한다.)