상태 공간과 탐색
탐색
문제의 해가 될 수 있는 것들의 집합을 공간으로 간주하고, 문제에 대한 최적해를 찾기위해 공간을 체계적으로 찾아보는 것
상태(state)
특정 시점에 문제의 세계가 처해있는 모습
세계(world)
문제에 포함된 대상들과 이들의 상황을 포괄적으로 지칭
상태 공간(state space)
문제 해결 과정에서 초기 상태로부터 도달할 수 있는 모든 상태들의 집합
문제의 해가 될 가능성이 있는 모든 상태들의 집합상태 공간 그래프(state space graph)
상태 공간에서 각 행동에 따른 상태의 변화를 나타낸 그래프 (노드: 상태, 링크: 행동)
일반적인 문제에서는 상태 공간이 매우 큼
그래서 탐색 과정에서 필요한 부분의 그래프를 생성하여 사용함
맹목적 탐색(blind search)
정해진 순서에 따라 상태 공간 그래프를 확장해나가면서 해를 탐색하는 방법
-> 깊이우선 탐색, 너비우선 탐색, 반복적 깊이심화 탐색, 양방향 탐색깊이 우선 탐색(depth-first search, DFS)
- 초기 노드에서 시작하여 깊이 방향으로 탐색, 목표 노드에 도달하면 종료
- 더 이상 진행할 수 없으면, 백트랙킹(backtracking)
- 방문한 노드는 재방문하지 않음
너비 우선 탐색(breadth-first search, BFS)
- 초기 노드에서 시작하여 모든 자식 노드를 확장하여 생성
- 목표 노드가 없으면 단말노드에서 다시 자식 노드 확장
깊이 제한 탐색(depth-limited search)
- 깊이 우선 탐색이 무한루프에 빠질 수 있는 단점을 극복하기 위해 깊이에 한계를 두는 탐색
- 한계 L을 정해 놓고 깊이가 L에 도달하면 백트랙킹(backtracking) 하게 됨
반복적 깊이심화 탐색(iterative-deepening search)
- 깊이 한계를 증가시켜 가며 깊이 제한 탐색을 반복적으로 적용
양방향 탐색(bidirectional search)
- 초기 노드와 목적 노드에서 동시에 너비 우선 탐색을 진행
- 중간에 만나도록 하여 초기 노드에서 목표 노드로의 최단 경로를 찾는 방법
| 깊이 우선 탐색 | 너비 우선 탐색 | 반복적 깊이심화 탐색 |
|---|---|---|
| 메모리 공간 사용 효율적 | 최단 경로 해 탐색 보장 | 최단 경로 해 보장 |
| 최단 경로 해 탐색 보장 불가 | 메모리 공간 사용 비효율 | 메모리 공간 사용 효율적 |
정보이용 탐색(informed search)
휴리스틱 탐색, 언덕 오르기 방법, 최상 우선 탐색, 빔 탐색, A* 알고리즘
휴리스틱 탐색(heuristic search)
- 그리스어로 찾다, 발견하다라는 뜻으로 특정 상황에서 신속하게 어림짐작하는 것을 의미한다.
언덕 오르기 방법(hill climbing method)
- 현재 노드에서 휴리스틱에 의한 평가값이 가장 좋은 이웃 노드 하나를 확장해 가는 탐색 방법
- 국소 최적해(local optimal solution)에 빠질 가능성이 있음
최상 우선 탐색(best-first search)
- 확장 중인 노드들 중에서 목표 노드까지 남은 거리가 가장 짧은 노드를 확장하여 탐색
- 탐욕적인(greedy) 알고리즘
- 남은 거리를 정확히 알 수 없으므로 휴리스틱 사용
빔 탐색(beam search)
- 휴리스틱에 의한 평가 값이 우수한 일정 개수(K)의 확장 가능한 노드만을 메모리에 관리하면서 최상 우선 탐색을 적용
- 일정 개수만을 유지하는 것이 포인트
A* 알고리즘
- 최상 우선 탐색의 개선 알고리즘
- 추정한 전체 비용( f(n) )을 최소로 하는 노드를 확장해 가는 방법
- f(n): 노드 n을 경유하는 전체 비용
현재 노드 n까지 이미 투입된 비용( g(n) )과 목표 노드까지의 남은 비용( h(n) )의 합
f(n) = g(n) + h(n)- h(n): 실제로 남은 비용으로 정확한 예측 불가
성