Uninformed Search란 무엇인가?
- Blind Search라고도 불리는 이 방법은 문제 해결을 위한 탐색 전략 중 하나이다 (=search algorithm)
- "uninformed"로 알 수 있듯이 목표 상태(goal state)에 도달하기 위해 탐색 공간(search space) 내에서 결정을 내릴 때, 문제에 대한 사전 지식(heuristic information) 없이 단순히 탐색 공간을 넓혀가는 방식이다
- 이와 대조되는 알고리즘은 "Informed" 혹은 "Heuristic" Search라고 한다
목표 상태? 탐색 공간?
Uninformed Search 알고리즘에 대해 완벽히 이해하기 위해선 State Space의 개념부터 파악할 필요가 있다.
State Space란?
- 탐색문제 (search problem)의 요소 중 하나인 상태공간(state space)은 특정 문제를 해결하기 위해 고려해야 할 모든 가능한 상태들의 집합이다
- 예를 들어, 특정 도시에서 출발하여 목표도시까지 달성하기 위한 탐색문제에서 state space는 이 약도에 있는 모든 도시들이다.
조금 더 복잡한 예시를 들어보자.
- 클래식 게임 PAC-MAN에서 모든 점(dot)을 먹는 탐색 문제가 주어진다면, state space는 무엇으로 구성될까?
- Agent position 팩맨의 위치
- Ghost position 유령의 위치
- Dot boolean 점의 상태 {먹힘,안먹힘}
- Power pellet boolean 파워 펠릿의 상태
Tree Search 트리 탐색?
주로 트리 구조를 사용하여 탐색 알고리즘을 구현한다.
- 탐색문제의 state space를 트리 구조로 모델링하고, 노드를 확장하며 트리를 시스템적으로 탐색하는 방법이다
- 구체적인 탐색 전략에 따라 다양하게 구현될 수 있다 (깊이 우선 탐색할까? 너비 우선 탐색할까?)
아래는 트리 탐색의 유사코드이다:
- 구체적인 탐색 전략이 이 유사코드의 "strategy"가 되고, 탐색 문제가 "problem"이다
- 우선, 탐색트리를 초기화한다. 루트 노드를 생성하여 탐색 대기열(스택, 큐)에 넣는다.
- 다음, 탐색 대기열이 비어있지 않는 동안 루프를 실행하는데,
- 탐색 대기열에서 노드를 선택한다
- 선택된 노드가 목표상태인가? 맞으면 => 탐색을 종료한다
- 아니라면 => 노드를 확장한다 (이때 확장 방법은 각 알고리즘의 전략에 따라 다르다)
- 생성된 후속 노드들을 탐색 대기열에 추가하여 업데이트한다
- 결과 반환: 목표 상태에 도달한 노드를 찾으면 그 노드에서 초기 상태까지의 경로를 역추적하여 해결책을 반환한다
그렇다면, Uninformed Search 알고리즘의 트리 탐색은 어떠한 전략들이 있을까?
Uninformed Search 알고리즘의 Search Strategy
1) 깊이 우선 탐색 Depth-First Search: 탐색 대기열을 Last-in-Last-out 스택으로 관리하는 전략이며, 뿌리하나를 완전히 탐색한 후 다음 트리로 넘어가는 방식이다.
2) 너비 우선 탐색 Breadth-First Search : 탐색 대기열을 First-in-First-out 큐로 관리하는 전략이며, 트리의 루트노드로 시작하여, 한층 한층 씩 탐색하는 방식이다.
3) 비용 기반 탐색 Uniform Cost Search : 탐색 대기열을 우선순위 큐로 관리하며, 누적 비용이 가장 낮은 노드를 가장 먼저 확장한다. 비용 측에서 가장 효율적인 방법이다.
탐색 알고리즘의 고려 요소
탐색 알고리즘들의 특징이나 효율성을 분석하기 위해서 여러 요소들을 고려해야한다.
- Time Complexity: 시간복잡도는 얼마인가?
- Space Complexity: 공간복잡도는 얼마인가?
- Completeness: 완전한가?
- Optimality: 최단 경로인가?
'컴퓨터의 이모저모' 카테고리의 다른 글
macbook air m2에 리눅스 커널 컴파일 (make) 안되는 이유 (5) | 2024.04.09 |
---|---|
컴퓨터구조와 운영체제 기본 중의 기본 개념 파악하기 (What is OS?) (22) | 2024.03.29 |