상태공간 탐색
1. 상태묘사 (State Representation)
정의
- 상태묘사는 문제의 "현재 상황"을 컴퓨터가 이해할 수 있도록 표현한 것.
- 즉, 문제의 한 순간을 나타내는 데이터 구조.
목적
- 탐색 알고리즘이 이 상태를 읽고, 비교하고, 다음 상태를 계산할 수 있도록 하기 위해 필요함.
예시
- 8퍼즐 문제: 3x3 배열로 퍼즐의 배치 상태 표현
- 예:
[['1','2','3'], ['4','5','6'], ['7','8',' ']]
- 예:
- 미로 탐색: 현재 위치를
(x, y)좌표로 표현 - 체스: 말들의 위치를 다차원 배열이나 비트보드로 표현
2. 연산자 (Operator)
정의
- 연산자는 한 상태를 다른 상태로 전이시키는 규칙이나 함수.
예시
- 8퍼즐 문제에서 빈 칸을 상하좌우로 이동하는 것
- 미로에서 한 칸 위/아래/왼쪽/오른쪽으로 이동하는 것
구현 방식
- 명시적 테이블: 가능한 모든 상태 전이 경우를 미리 나열
- 암시적 규칙: 코드나 수식으로 일반적인 변환 규칙 정의
3. 상태공간 (State Space)
정의
- 가능한 모든 상태들의 집합.
- 초기 상태에서 연산자를 반복 적용하면 만들어지는 전체 상태들.
표현
- 상태공간은 그래프 형태로 생각하면 됨.
- 노드: 상태
- 간선: 연산자에 의한 상태 전이
특징
- 탐색 알고리즘은 이 상태공간 그래프에서 경로를 찾는 것.
- 상태가 중복될 수 있으므로 방문한 상태는 따로 기록해야 함.
탐색 알고리즘
4. 깊이우선탐색 (DFS: Depth-First Search)
핵심 아이디어
- 가능한 한 깊이 있는 방향으로 먼저 탐색.
- 더 이상 갈 수 없으면 되돌아가서 다른 경로를 탐색.
자료구조
- 스택 (Stack) 또는 재귀함수
장점
- 구현이 간단하고 메모리 사용량이 적음
단점
- 해가 깊은 곳에 없으면 불필요한 탐색을 많이 하게 됨
- 최단 경로 보장 안됨
시간복잡도
- O(b^m)
(b: branching factor, m: 최대 깊이)
5. 너비우선탐색 (BFS: Breadth-First Search)
핵심 아이디어
- 현재 상태의 모든 이웃 노드를 먼저 탐색한 다음, 그 다음 단계로 넘어감
자료구조
- 큐 (Queue)
장점
- 해가 존재하면 최단 경로를 반드시 찾을 수 있음
단점
- 메모리를 많이 사용함 (모든 노드를 큐에 보관해야 하기 때문)
시간복잡도
- O(b^d)
(d: 해까지의 깊이)
6. 균일비용탐색 (UCS: Uniform-Cost Search)
핵심 아이디어
- 누적 비용이 가장 적은 경로부터 탐색
- BFS랑 비슷하지만 간선마다 비용이 다를 때 사용함
자료구조
- 우선순위 큐 (Priority Queue, 보통 heap)
장점
- 최소 비용 경로를 반드시 찾아줌
단점
- 속도가 느릴 수 있음 (비용 계산 때문에)
시간복잡도
- O(b^d) 이상
(경로비용의 다양성에 따라 더 커질 수 있음)
탐색 알고리즘 비교표
| 알고리즘 | 자료구조 | 최단 경로 보장 | 비용 고려 | 시간복잡도 | 메모리 사용량 |
|---|---|---|---|---|---|
| DFS | 스택 | ❌ | ❌ | O(b^m) | 적음 |
| BFS | 큐 | ✅ | ❌ | O(b^d) | 많음 |
| UCS | 우선순위 큐 | ✅ | ✅ | O(b^d)~ | 많음 |
코드 (Python)
# 코드 (Python)
---
## 공통 예제 그래프 (인접 리스트로 표현)
# 예제에서 사용할 그래프는 다음과 같다:
# A
# / \
# B C
# / \ \
# D E F
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': []
}
---
## DFS (깊이우선탐색)
def dfs(graph, start, visited=None):
if visited is None:
visited = []
# 현재 노드를 방문 처리
visited.append(start)
print(f"방문: {start}") # 현재 노드 출력
# 인접한 노드들에 대해 재귀적으로 방문
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
# 실행
print("DFS 탐색 결과:")
dfs(graph, 'A')
# 설명:
# - 시작 노드에서 가능한 한 깊게 들어감
# - D, E, F와 같이 끝 노드까지 간 후에 백트래킹함
# - 결과 예시: A → B → D → E → C → F
---
## BFS (너비우선탐색)
from collections import deque
def bfs(graph, start):
visited = [] # 방문한 노드 저장
queue = deque([start]) # 시작 노드를 큐에 넣기
while queue:
node = queue.popleft() # 큐에서 노드 꺼내기
if node not in visited:
visited.append(node)
print(f"방문: {node}") # 현재 노드 출력
# 인접 노드를 큐에 추가
for neighbor in graph[node]:
queue.append(neighbor)
return visited
# 실행
print("BFS 탐색 결과:")
bfs(graph, 'A')
# 설명:
# - 시작 노드와 가까운 순서대로 탐색 (너비 우선)
# - A → B → C → D → E → F 순으로 방문
# - 항상 먼저 들어온 노드를 먼저 처리함 (Queue 사용)
---
## UCS (균일비용탐색)
import heapq
# 가중치가 있는 그래프 정의 (비용 있음)
weighted_graph = {
'A': [('B', 1), ('C', 4)],
'B': [('D', 2), ('E', 5)],
'C': [('F', 1)],
'D': [],
'E': [],
'F': []
}
def ucs(graph, start, goal):
visited = set()
pq = [] # 우선순위 큐 사용
heapq.heappush(pq, (0, start, [])) # (총 비용, 현재 노드, 경로)
while pq:
cost, node, path = heapq.heappop(pq)
if node in visited:
continue
visited.add(node)
path = path + [node]
print(f"방문: {node}, 현재 비용: {cost}")
if node == goal:
print(f"목표 노드 {goal}에 도달! 총 비용: {cost}")
print(f"경로: {' -> '.join(path)}")
return
for neighbor, weight in graph[node]:
if neighbor not in visited:
heapq.heappush(pq, (cost + weight, neighbor, path))
# 실행
print("UCS 탐색 결과 (A → E):")
ucs(weighted_graph, 'A', 'E')
# 설명:
# - 항상 누적 비용이 가장 적은 노드를 먼저 확장함
# - Priority Queue
Working Abroad ...