[인공지능] Uninformed Search

* 탐색 (search)

- 어떤 문제가 있을 때, 해 공간 (solution space) 에서 최적의 해를 찾기 위 한 방법

- Solution space: 해 (solution)가 될 수 있는 것을 모아놓은 집합

- 해 (solution): 일련의 동작 또는 하나의 상태로 구성

 

* 탐색 (search)의 문제 예시

 

* State Space

- State (상태): 특정 시간에 주어진 문제가 당면해 있는 상황

예: missionary-cannibals 문제의 initial state

- World (세계): 문제에 포함된 객체 (objects)와 처한 상태 등 필요한 정보

- State space (상태 공간): 문제를 해결하기 위해 필요한 objects, state, world 등의 정보.

초기 상태, 문제 해결의 상태, 가능한 모든 상태의 집합

예:  Initial state/goal state

 

* 상태 공간 그래프(state space graph)

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

-> 노드 : 상태 , 링크 : 행동

-> 해 (solution): initial state에서 goal state로 도달하기 위한 path

상태 공간 그래프의 예시, 식인종이 더 많을 경우 선교사는 잡아먹힌다, 잡아먹히지 않고 강을 건너기 위한 해 찾기

 

: 일반적인 문제에서 상태 공간이 매우 큼

-> 미리 상태 공간 그래프를 만들기 어려움

-> 탐색과정에서 그래프 생성

 

* 맹목적 탐색(Uninformed search) = Blind Search

정해진 순서에 따라 상태 공간 그래프를 탐색하는 방법으로 해를 찾는다

현재 상태에서 목표 상태까지의 노드의 개수를 알지 못하고 해를 찾아 나가는 탐색 방법

예시) 깊이 우선 탐색(depth-first search, DFS), 너비 우선 탐색(breath-first search, BFS), 깊이 제한 탐색 (depth-limited search), 점차적 깊이제한 탐색 (iterative deepening search), 일정량 탐색 (uniform-cost search), 양방향 탐색 (bidirectional search)

 

* 탐색 방법의 평가

• Complete: 해를 찾아주는가?

• Optimal: 찾은 해가 최적해임을 보장하는가?

• Time & space complexity: 알고리즘의 시간, 공간 복잡성

 

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

• 초기 노드에서 시작하여 깊이 방향으로 탐색

• 목표 노드에 도달하면 종료

• 더 이상 진행할 수 없으면, 백트랙킹(backtracking, 되짚어가기)

• 방문한 노드는 재방문하지 않음

O : 시간복잡도,  b: number of child node m: maximum depth

 

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

• 초기 노드에서 시작하여 모든 자식 노드를 확장하여 생성

• 목표 노드가 없으면 단말노드에서 다시 자식 노드 확장

O : 시간복잡도,  b: number of child node

 

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

: 깊이 한계가 있는 깊이 우선 탐색을 반복적으로 적용

 

4) 양방향 탐색(bidirectional search) :

초기 노드와 목적 노드에서 동시에 너비 우선 탐색을 진행

중간에 만나도록 하여 초기 노드에서 목표 노드로의 최단 경로를 찾는 방법

 

- 깊이 우선 탐색 (DFS)

• 메모리 공간 사용 효율적

• 최단 경로 해 탐색 보장 불가

- 너비 우선 탐색 (BFS)

• 최단 경로 해 탐색 보장

• 메모리 공간 사용 비효율

- 반복적 깊이심화 탐색 (IDS)

• 최단 경로 해 보장

• 메모리 공간 사용 효율적

• 반복적인 깊이 우선 탐색에 따른 비효율성

• 실제 비용이 크게 늘지 않음

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

• 맹목적 탐색 적용시 우선 고려 대상

 

분류	Breadth First	Depth First	Depth Limited	Iterative Deepening	Uniform Cost
Complete	O	X	X	O	O
Optimal	O	X	X	O	O