상태공간과 탐색
- 탐색 (search) : 상태 공간에서 시작 상태에서 목표 상태까지의 경로를 찾는 과정
- 상태공간 (state space) : 가능한 모든 상태의 집합
- 연산자 : 상태에서 다음 상태로의 전이 규칙
예시)
1. 8-puzzle
- 상태공간은 퍼즐의 각 배치, 연산자는 퍼즐의 각 타일을 상하좌우로 움직이는 것
2. N-Queen 문제
- N*N 체스판에 N개의 퀸을 배치하는 문제
- 상태는 퀸의 위치, 연산자는 퀸의 이동
- 상태 공간 : 각각의 퀸을 정해진 열에서만 움직이게 한다.
- 연산자 :
탐색 트리 (Search Tree)
- 노드 : 상태를 나타내는 트리의 각 지점
- 루트 : 탐색 트리의 시작 상태
- 간선 : 연산자를 나타내는 트리의 연결
- 탐색 과정에서 트리는 상태를 확장하며 목표 상태를 찾는다.
기본적인 탐색 기법
1. 맹목적인 탐색 (Blind Search Method)
- 목표 노드에 대한 정보를 사용하지 않고 기계적인 방법으로 상태를 확장
2. 경험적 탐색 (Heuristic Search Method)
- 목표 노드에 대한 경험적 정보를 사용하여 효율적인 탐색이 가능
- 경험적인 정보 = 휴리스틱 (Heuristic)
탐색 성능 측정
- 완결성 : 문제에 해답이 있다면, 반드시 해답을 찾을 수 있는지 여부
- 최적성 : 가장 비용이 적은 해답을 찾을 수 있는지 여부
- 시간 복잡도 : 해답을 찾는데 걸리는 시간
- 공간 복잡도 : 탐색을 수행하는데 필요한 메모리의 양
맹목적인 탐색
1. 깊이 우선 탐색(DFS)
- 탐색 트리에서 목표가 있을 가능성이 있는 노드를 찾아 계속 전진
- 문제점 : 중복된 상태를 방문할 수 있으므로 이를 방지하기 위한
Open List(확장된 상태)와 Closed List(탐색 완료된 상태)가 필요
DFS 알고리즘 :
1. 루트 노드를 Open List에 추가하고 탐색을 시작
2. 목표 상태에 도달하면 SUCCESS를 반환하고, 아니면 자식 노드를 생성하여 Open List에 추가
시험 문제 !!!!!!!!!!
2. 너비 우선 탐색(BFS)
- 루트 노드의 모든 자식 노드를 탐색한 후, 그 다음 레벨로 내려가며 탐색을 계속함
- BFS 알고리즘도 DFS와유사하지만, 자식 노드를 큐처럼 처리하여 확장 순서를 관리
맹목적 탐색 알고리즘 분석
1. 깊이 우선 탐색 알고리즘(DFS) 분석
- 완결성 : 무한한 상태 공간에서는 완결적이지 않음 BUT 유한한 상태공간에서는 완결성 보장
- 최적성 : 보장되지 않음
- 시간 복잡도 : O(b^m)
- b : 각 단계에서 확장되는 상태의 가지 수
- m : 트리의 최대 깊이
- 공간 복잡도 : O(bm)
2. 너비 우선 탐색 알고리즘(BFS) 분석
- 완결성 : 유한한 상태공간에서는 완결성 보장
- 최적성 : 보장
- 시간 복잡도 : O(b^d)
- b : 각 단계에서 확장되는 상태의 가지 수
- d : 목표 노드의 깊이
- 공간 복잡도 : O(b^d)
깊이 우선 탐색 vs 너비 우선 탐색
- 깊이 우선 탐색은 최적해를 보장하지 않지만, 적은 메모리로 수행 가능
- 너비 우선 탐색은 최적해를 보장하지만, 메모리 요구량이 지수적으로 커짐
시험문제!!!!
3. 깊이 제한 탐색 (DLS - Depth Limited Search)
- DFS의 단점인 높은 시간 복잡도와 높은 비용을 해결하기 위해 깊이를 제한하여 탐색을 수행
- 완경성이 보장되지 않는 한계가 있음
Quiz ) 루마니아 Map 경로 찾기 문제를 푼다면 깊이 제한을 몇으로 하는 것이 적절할까?
Answer ) Map에 있는 도시의 수 (모든 도시를 탐색할 수 있기 때문에)
4. 반복 심화 탐색 (Iterative Deepening DFS)
- DLS의 깊이 제한을 순차적으로 완화하여 탐색하는 기법
- 이 방식은 깊이 우선 탐색의 장점과 너비 우선 탐색의 장점을 결합한 형태
5. 균일 비용 탐색 (Uniform Cost Search - Dijstra's Algorithm)
- 다익스트라 알고리즘을 사용하여 간선 비용을 고려한 최적 경로를 찾음
- 비용이 가장 적은 경로를 선택하여 탐색을 진행
시험문제!!!! 최적의 경로와 그 때의 비용은?
경험적 탐색 알고리즘 분석
휴리스틱 예시 (8-Puzzle)
휴리스틱1의 경우는 4, 휴리스틱 2의 경우는 6 이다.
1. 언덕 등반 방법 (Hill Climbing Method)
- 최적화된 값을 찾기 위해 가장 좋은 평가 값을 가진 자식 노드를 선택하여 탐색을 진행
- 적용 휴리스틱 : 현재 제 위치에 있지 않은 타일의 수 (휴리스틱은 문제의 조건)
지역 최소/최대 문제 (Local Mimimum/Maximum Problem)
- 이 방법은 휴리스틱 값에만 의존하므로, 목표 상태가 아닌 지역 최소값에 도달할 위험이 존재
- 생성된 자식 노드의 휴리스틱 값이 부모 노드보다 더 높거나 같은 경우가 나올 수 있음
2. A* 알고리즘
- 힐 클라이밍의 한계를 극복 (힐 클라이밍은 오직 목표 노드와의 h(n)만을 고려)
(시작 노드에서 멀어지게 되면 그만큼 비용이 더 드는 것이기 때문에 경로의 비용도 평가 함수에 추가 필요)
- f(n) = g(n) + h(n) (시작 노드에서 현재 노드까지 오는 비용 + 현재 노드에서 목표 노드까지의 추정 거리)
- 적용되는 휴리스틱이 허용성 (Admissibility)을 갖추면 최적의 비용으로 해를 찾는다
연습문제)
'지능형 시스템' 카테고리의 다른 글
| 지시 ch6) 머신러닝 기초 (0) | 2025.04.09 |
|---|---|
| 지시 ch5) 유전 알고리즘 (0) | 2025.04.02 |
| 지시 ch3) 게임 트리 (1) | 2025.03.24 |