상태 표현(State Representation)#
상태 표현은 문제 해결 과정에서 현재까지의 결정과 남은 선택지를 효과적으로 나타내는 방법이다.
Branch and Bound 알고리즘에서 상태 표현은 다음과 같은 중요한 역할을 한다:
- 문제 공간 표현: 가능한 모든 해결책(solution space)을 체계적으로 표현한다.
- 탐색 진행 상황 추적: 알고리즘이 문제 공간을 탐색하는 과정에서 현재 위치를 나타낸다.
- 한계값(bound) 계산 지원: 각 상태에서 가능한 최적값의 상한 또는 하한을 계산할 수 있게 한다.
- 가지치기(pruning) 결정 기반: 더 이상 탐색할 가치가 없는 상태를 식별하는 데 사용된다.
상태 표현의 주요 특성 및 고려 사항#
상태 표현의 완전성(Completeness)
상태 표현은 문제의 모든 가능한 해결책을 표현할 수 있어야 한다.
불완전한 상태 표현은 최적해를 놓치게 할 수 있다.
상태 표현의 간결성(Conciseness)
효율적인 상태 표현은 불필요한 정보를 제외하고 필수적인 정보만 포함해야 한다.
상태의 크기가 크면 메모리 사용량이 증가하고 알고리즘의 성능이 저하될 수 있다.
상태 전이의 효율성(Transition Efficiency)
한 상태에서 다른 상태로의 전이가 효율적으로 계산될 수 있어야 한다.
전이 연산이 복잡하면 알고리즘의 실행 시간이 증가한다.
한계값 계산의 용이성(Bound Calculation)
상태 표현은 해당 상태에서 가능한 최적값의 상한 또는 하한을 쉽게 계산할 수 있도록 설계되어야 한다.
정확하고 효율적인 한계값 계산은 가지치기의 효과를 높인다.
중복 상태 처리(Duplicate State Handling)
일부 문제에서는 서로 다른 경로로 동일한 상태에 도달할 수 있다.
효과적인 상태 표현은 이러한 중복을 식별하고 처리할 수 있어야 한다.
효율적인 상태 표현을 위한 설계 지침#
- 상태 표현 설계 단계
- 문제 분석: 문제의 특성과 제약조건을 명확히 이해한다.
- 필수 정보 식별: 문제 해결에 필요한 최소한의 정보를 식별한다.
- 표현 방식 선택: 문제 특성에 가장 적합한 상태 표현 방식을 선택한다.
- 한계값 함수 설계: 효율적이고 정확한 한계값 계산 방법을 설계한다.
- 상태 전이 함수 구현: 한 상태에서 다른 상태로의 전이를 효율적으로 구현한다.
- 중복 상태 처리 메커니즘 설계: 필요한 경우 중복 상태를 식별하고 처리하는 방법을 구현한다.
- 효율적인 상태 표현의 특성
- 최소성(Minimality): 필요한 정보만 포함하고 중복 정보는 제거한다.
- 구별성(Distinguishability): 서로 다른 해결책은 서로 다른 상태로 표현되어야 한다.
- 효율성(Efficiency): 상태 표현과 관련된 연산(생성, 전이, 비교 등)이 효율적이어야 한다.
- 계산 용이성(Computability): 한계값과 같은 중요한 메트릭을 쉽게 계산할 수 있어야 한다.
- 확장성(Scalability): 문제 크기가 커져도 효율적으로 처리할 수 있어야 한다.
- 상태 표현 최적화 기법
- 증분 계산(Incremental Computation): 상태 전이 시 전체를 다시 계산하는 대신 변경된 부분만 업데이트한다.
- 상태 압축(State Compression): 불필요한 정보를 제거하고 효율적인 자료구조를 사용한다.
- 해시 기반 중복 탐지(Hash-based Duplicate Detection): 해시 함수를 사용하여 중복 상태를 효율적으로 탐지한다.
- 지연 계산(Lazy Evaluation): 필요할 때만 계산을 수행하여 계산 비용을 줄인다.
- 메모이제이션(Memoization): 이전에 계산한 결과를 저장하여 재사용한다.
주요 상태 표현 방식#
벡터 기반 상태 표현(Vector-based Representation)#
벡터 기반 상태 표현은 여러 변수나 결정 사항을 벡터의 요소로 표현하는 방식.
1
2
3
4
5
6
7
| # 배낭 문제에서의 벡터 기반 상태 표현 예시
class State:
def __init__(self, level, weight, value, items_included):
self.level = level # 현재 결정 레벨
self.weight = weight # 현재까지의 무게
self.value = value # 현재까지의 가치
self.items_included = items_included.copy() # 포함된 항목 목록(0/1 벡터)
|
특징:
- 직관적이고 구현이 상대적으로 간단.
- 각 차원이 의사 결정 변수에 해당.
- 상태 간 전환이 벡터 요소의 변경으로 표현.
예시: 배낭 문제(Knapsack Problem)#
배낭 문제에서 각 물건의 포함 여부를 벡터로 표현할 수 있다.
1
2
3
| 상태 표현: [x₁, x₂, x₃, …, xₙ]
- xᵢ = 1: i번째 물건을 배낭에 포함
- xᵢ = 0: i번째 물건을 배낭에 포함하지 않음
|
시각화#
1
2
3
4
5
6
| [0,0,0,0] (초기 상태: 빈 배낭)
/ \
[1,0,0,0] (물건1 포함) [0,0,0,0] (물건1 제외)
/ \ / \
[1,1,0,0] [1,0,0,0] [0,1,0,0] [0,0,0,0]
(물건1,2 포함) (물건1만) (물건2만) (물건 없음)
|
이 표현에서 각 노드는 부분 해결책을 나타내며, 리프 노드는 가능한 완전한 해결책을 나타낸다.
분기 과정에서 상한(bound)을 계산하여 유망하지 않은 노드를 가지치기한다.
트리 기반 상태 표현(Tree-based Representation)#
트리 기반 상태 표현은 결정 트리의 노드로 상태를 표현하며, 각 분기는 다른 결정 경로를 나타낸다.
1
2
3
4
5
6
7
| # 외판원 문제(TSP)에서의 트리 기반 상태 표현 예시
class TSPState:
def __init__(self, path, cost, remaining_cities):
self.path = path.copy() # 현재까지의 경로
self.cost = cost # 현재까지의 비용
self.remaining_cities = remaining_cities.copy() # 방문해야 할 도시 목록
self.lower_bound = self.calculate_bound() # 하한값
|
특징:
- 계층적 구조로 문제의 분할을 자연스럽게 표현.
- 부모-자식 관계가 결정의 순서와 의존성을 명확히 보여준다.
- 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 등 다양한 트리 탐색 알고리즘을 적용할 수 있다.
예시: 외판원 문제(TSP)#
1
2
| 상태 표현: (현재 도시, 방문한 도시 집합)
예: (3, {1, 2, 3})은 도시 1, 2를 방문한 후 현재 도시 3에 있음을 의미
|
시각화#
1
2
3
4
5
6
7
| (1, {1}) (시작 도시 1)
/ | \
(2, {1,2}) (3, {1,3}) (4, {1,4})
/ \ / \ / \
(3, {1,2,3}) (4, {1,2,4}) … … …
/ \
… …
|
각 노드는 현재까지의 경로와 방문한 도시들을 나타낸다. 여기서 분기는 다음에 방문할 수 있는 도시들에 대해 이루어지며, 각 경로의 하한(lower bound)을 계산하여 가지치기를 수행한다.
비트마스크 기반 상태 표현(Bitmask-based Representation)#
비트마스크 기반 상태 표현은 이진 비트열을 사용하여 선택/비선택 상태를 효율적으로 표현하는 방식.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| # 집합 커버링 문제에서의 비트마스크 기반 상태 표현 예시
def set_covering_branch_and_bound(universe, subsets, costs):
n = len(subsets)
# 상태 표현: (선택된 부분집합의 비트마스크, 커버된 원소의 비트마스크, 비용)
initial_state = (0, 0, 0) # 아무것도 선택되지 않은 초기 상태
# 비트마스크를 이용한 집합 연산
def get_coverage(subset_mask):
coverage = 0
for i in range(n):
if (subset_mask & (1 << i)) != 0: # i번째 부분집합이 선택된 경우
coverage |= subsets[i] # 비트 OR 연산으로 커버 업데이트
return coverage
|
특징:
- 메모리 효율적인 표현이 가능(n개 항목을 n비트로 표현).
- 비트 연산을 통해 집합 연산(합집합, 교집합 등)을 빠르게 수행할 수 있다.
- 작은 크기의 문제(일반적으로 요소 수가 32개 또는 64개 이하)에 적합.
예시: 집합 커버 문제(Set Cover Problem)#
1
2
| 상태 표현: 정수의 비트 표현
예: 13(10진수) = 1101(2진수)는 첫 번째, 세 번째, 네 번째 요소가 선택됨을 의미
|
시각화#
1
2
3
4
5
6
7
8
9
| 0 (0000)
/ \
1 (0001) 0 (0000)
/ \ / \
3 (0011) 1 (0001) 2 (0010) 0 (0000)
/ \
7 (0111) 3 (0011)
/ \
15 (1111) 7 (0111)
|
각 노드는 비트마스크로 표현된 상태를 나타내며, 1인 비트 위치의 요소가 선택된 상태이다.
이 표현은 메모리 사용이 효율적이고 집합 연산(합집합, 교집합 등)이 비트 연산으로 빠르게 수행될 수 있다.
행렬 기반 상태 표현(Matrix-based Representation)#
행렬 기반 상태 표현은 2차원 이상의 배열을 사용하여 복잡한 관계와 제약조건을 표현하는 방식.
1
2
3
4
5
6
| # 작업 할당 문제에서의 행렬 기반 상태 표현 예시
class AssignmentState:
def __init__(self, assignment_matrix, cost):
self.matrix = assignment_matrix.copy() # 할당 행렬(0/1 값)
self.cost = cost # 현재까지의 비용
self.next_person = self.find_next_unassigned() # 다음 할당할 사람
|
특징:
- 2차원 이상의 관계를 표현하기에 적합.
- 행렬 연산을 활용하여 상태 전이나 한계값 계산이 가능.
- 할당 문제, 스케줄링 문제 등에 자주 사용.
예시: 8-퍼즐 문제(8-Puzzle Problem)#
1
2
3
4
5
| 상태 표현: 3x3 행렬
예:
2 8 3
1 0 4 (0은 빈 공간)
7 6 5
|
시각화#
1
2
3
4
5
6
7
8
9
10
11
12
13
| ┌─────────┐
│ 2 8 3 │
초기 상태 → │ 1 0 4 │
│ 7 6 5 │
└─────────┘
│
┌─────────┴─────────┐
↓ ↓
┌─────────┐ ┌─────────┐
│ 2 8 3 │ │ 2 0 3 │
│ 0 1 4 │ │ 1 8 4 │ ← 가능한 다음 상태들
│ 7 6 5 │ │ 7 6 5 │
└─────────┘ └─────────┘
|
각 노드는 퍼즐 보드의 상태를 나타내며, 분기는 빈 공간(0)과 인접한 숫자를 교환하여 생성된다.
맨해튼 거리와 같은 휴리스틱을 사용하여 목표 상태까지의 하한을 계산한다.
그래프 기반 상태 표현(Graph-based Representation)#
그래프 기반 상태 표현은 노드와 엣지를 사용하여 상태와 상태 간의 전이를 표현하는 방식.
1
2
3
4
5
6
| # 최소 신장 트리 문제에서의 그래프 기반 상태 표현 예시
class MSTState:
def __init__(self, selected_edges, total_weight, connected_components):
self.selected_edges = selected_edges.copy() # 선택된 엣지 목록
self.total_weight = total_weight # 현재까지의 가중치 합
self.connected_components = connected_components.copy() # 연결 컴포넌트 정보
|
특징:
- 그래프 구조를 가진 문제(최단 경로, 최소 신장 트리 등)에 자연스럽게 적용.
- 노드와 엣지의 관계를 명시적으로 표현할 수 있다.
- 그래프 알고리즘과 결합하여 효율적인 탐색이 가능.
예시: 최소 신장 트리(MST) 문제#
1
2
| 상태 표현: (선택된 간선 집합, 연결된 노드 집합)
예: ({(1,2), (2,3)}, {1, 2, 3})은 간선 (1,2)와 (2,3)이 선택되어 노드 1, 2, 3이 연결됨을 의미
|
시각화#
1
2
3
4
5
| ({}, {}) (초기 상태: 간선 없음)
/ \
({(1,2)}, {1,2}) ({(1,3)}, {1,3})
/ \ / \
({(1,2),(2,3)},{1,2,3}) … … …
|
각 노드는 현재까지 선택된 간선과 연결된 노드의 집합을 나타낸다.
분기는 새로 추가할 수 있는 간선에 대해 이루어지며, 최소 신장 트리의 비용에 대한 하한을 계산하여 가지치기를 수행한다.
상태 표현 방식의 비교#
| 특성 | 벡터 기반 | 트리 기반 | 비트마스크 기반 | 행렬 기반 | 그래프 기반 |
|---|
| 메모리 효율성 | 중간 | 낮음 | 높음 | 낮음 | 낮음 |
| 구현 복잡성 | 낮음 | 중간 | 중간 | 중간 | 높음 |
| 계산 효율성 | 중간 | 중간 | 높음 | 중간 | 중간 |
| 확장성 | 높음 | 높음 | 제한적 | 높음 | 높음 |
| 중복 상태 탐지 | 중간 | 어려움 | 쉬움 | 중간 | 어려움 |
| 상태 전이 용이성 | 높음 | 높음 | 높음 | 중간 | 중간 |
| 한계값 계산 적합성 | 높음 | 높음 | 중간 | 높음 | 높음 |
| 적합한 문제 유형 | 일반적인 최적화 문제 | 계층적 문제 | 부분집합 선택 문제 | 할당, 스케줄링 문제 | 경로, 네트워크 문제 |
| 최대 문제 크기 | 중간 | 중간~큼 | 작음~중간(≤64) | 중간 | 중간~큼 |
| 병렬화 가능성 | 중간 | 높음 | 낮음 | 중간 | 높음 |
| 메모리 사용량 | O(n) | O(n) ~ O(n²) | O(1) ~ O(log n) | O(n²) | O(n + e) |
| 상태 표현 예시 | [0,1,0,1,1] | 경로 트리 | 10110 (비트열) | 2차원 배열 | 노드와 엣지 |
| 장점 | 직관적, 유연함 | 계층 구조 표현에 적합 | 메모리 효율적, 빠른 연산 | 복잡한 관계 표현 가능 | 관계 표현에 자연스러움 |
| 단점 | 큰 문제에서 비효율적 | 메모리 사용량 많음 | 크기 제한, 구현 복잡 | 희소 행렬에서 비효율적 | 구현 복잡, 메모리 많이 사용 |
각 상태 표현 방식은 특정 문제 유형에 더 적합할 수 있다:
- 벡터 기반: 선택/비선택 결정이 많은 문제 (배낭 문제, 자원 할당)
- 트리 기반: 계층적 의사결정이 필요한 문제 (게임 트리, 의사결정 트리)
- 비트마스크 기반: 이진 선택이 많고 집합 연산이 필요한 문제 (부분집합 문제)
- 행렬 기반: 공간적/지역적 관계가 중요한 문제 (퍼즐, 격자 기반 문제)
- 그래프 기반: 연결성과 네트워크 구조가 중요한 문제 (경로 찾기, 네트워크 설계)
적절한 상태 표현을 선택하면 문제 해결의 효율성을 크게 향상시킬 수 있으며, 이는 분기한정법을 적용할 때 특히 중요하다. 문제의 특성을 잘 파악하여 가장 적합한 상태 표현 방식을 선택하는 것이 알고리즘 설계의 핵심이다.
다양한 문제에서의 상태 표현 적용 예시#
배낭 문제(Knapsack Problem)의 상태 표현#
배낭 문제는 제한된 무게 내에서 최대 가치를 가진 물건들을 선택하는 문제.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| def knapsack_branch_and_bound(weights, values, capacity):
n = len(weights)
# 상태 정의: (레벨, 현재 무게, 현재 가치, 포함된 항목 목록)
class State:
def __init__(self, level, weight, value, includes):
self.level = level # 결정 레벨(몇 번째 항목까지 고려했는지)
self.weight = weight # 현재까지의 무게
self.value = value # 현재까지의 가치
self.includes = includes.copy() # 포함된 항목 목록(0/1 벡터)
# 상한값 계산
self.bound = self.calculate_bound()
def calculate_bound(self):
if self.weight > capacity:
return 0
bound_value = self.value
j = self.level
total_weight = self.weight
# 남은 항목들을 가치/무게 비율이 높은 순으로 최대한 추가
while j < n and total_weight + weights[j] <= capacity:
total_weight += weights[j]
bound_value += values[j]
j += 1
# 마지막 항목은 분수로 추가(분할 가능 가정)
if j < n:
bound_value += (capacity - total_weight) * (values[j] / weights[j])
return bound_value
|
이 상태 표현은 현재까지의 결정(어떤 항목을 포함했는지)과 그에 따른 무게와 가치를 추적한다.
또한 남은 공간에 추가할 수 있는 최대 가치를 상한값으로 계산한다.
외판원 문제(TSP)의 상태 표현#
외판원 문제는 모든 도시를 한 번씩 방문하고 출발 도시로 돌아오는 최단 경로를 찾는 문제.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| def tsp_branch_and_bound(distance_matrix):
n = len(distance_matrix)
# 상태 정의: (경로, 비용, 방문하지 않은 도시 목록)
class State:
def __init__(self, path, cost, unvisited):
self.path = path.copy() # 현재까지의 경로
self.cost = cost # 현재까지의 비용
self.unvisited = unvisited.copy() # 방문하지 않은 도시 목록
# 하한값 계산
self.lower_bound = self.calculate_lower_bound()
def calculate_lower_bound(self):
# 현재까지의 비용 + 방문하지 않은 도시들의 최소 진입 비용 + 최소 탈출 비용
lb = self.cost
# 각 미방문 도시의 최소 진입 비용
for city in self.unvisited:
min_in = float('inf')
for i in range(n):
if i != city and (i in self.path or i in self.unvisited):
min_in = min(min_in, distance_matrix[i][city])
lb += min_in
# 각 미방문 도시의 최소 탈출 비용
for city in self.unvisited:
min_out = float('inf')
for i in range(n):
if i != city and (i in self.path or i in self.unvisited):
min_out = min(min_out, distance_matrix[city][i])
lb += min_out
return lb / 2 # 각 비용이 두 번 계산되었으므로 2로 나눔
|
이 상태 표현은 현재까지의 경로, 비용, 그리고 아직 방문하지 않은 도시 목록을 포함한다.
하한값은 현재까지의 비용과 미방문 도시들의 최소 진입/탈출 비용을 기반으로 계산된다.
5.3 작업 할당 문제(Job Assignment Problem)의 상태 표현#
작업 할당 문제는 n개의 작업을 n명의 작업자에게 최적으로 할당하는 문제.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| def job_assignment_branch_and_bound(cost_matrix):
n = len(cost_matrix)
# 상태 정의: (할당된 작업자 목록, 총 비용)
class State:
def __init__(self, assignments, cost):
self.assignments = assignments.copy() # 각 작업별 할당된 작업자(-1은 미할당)
self.cost = cost # 현재까지의 총 비용
self.next_job = len([a for a in self.assignments if a != -1]) # 다음 할당할 작업
# 하한값 계산
self.lower_bound = self.calculate_lower_bound()
def calculate_lower_bound(self):
lb = self.cost
# 각 미할당 작업에 대해 최소 비용을 추가
for job in range(self.next_job, n):
# 이미 할당된 작업자를 제외한 최소 비용 찾기
min_cost = float('inf')
for worker in range(n):
if worker not in self.assignments:
min_cost = min(min_cost, cost_matrix[job][worker])
lb += min_cost
return lb
|
이 상태 표현은 각 작업별로 할당된 작업자와 현재까지의 총 비용을 추적한다.
하한값은 현재까지의 비용과 미할당 작업의 최소 비용을 합산하여 계산한다.
8. 실제 사례 연구: 15-퍼즐 문제의 상태 표현#
15-퍼즐은 4x4 그리드에 1부터 15까지의 숫자와 한 개의 빈 칸이 있으며, 빈 칸을 이동하여 숫자를 정렬하는 퍼즐이다.
이 문제에 대한 Branch and Bound 접근법과 상태 표현.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| def solve_15_puzzle(initial_state):
# 상태 표현: (보드 배열, 빈 칸 위치, 이동 횟수, 이전 이동 방향)
class PuzzleState:
def __init__(self, board, empty_pos, moves, prev_dir=None):
self.board = board.copy() # 4x4 보드 배열
self.empty_pos = empty_pos # 빈 칸 위치 (row, col)
self.moves = moves # 현재까지의 이동 횟수
self.prev_dir = prev_dir # 이전 이동 방향
# 휴리스틱 계산(맨해튼 거리)
self.h = self.calculate_heuristic()
# f(n) = g(n) + h(n)
self.f = self.moves + self.h
def calculate_heuristic(self):
h = 0
for i in range(4):
for j in range(4):
if self.board[i][j] != 0: # 빈 칸이 아닌 경우
# 목표 위치 계산
val = self.board[i][j]
goal_row, goal_col = (val - 1) // 4, (val - 1) % 4
# 맨해튼 거리 추가
h += abs(i - goal_row) + abs(j - goal_col)
return h
# 다음 가능한 상태 생성
def generate_next_states(self):
next_states = []
row, col = self.empty_pos
# 가능한 이동 방향: 상, 하, 좌, 우
directions = [(-1, 0, 'U'), (1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R')]
for dr, dc, dir_name in directions:
new_row, new_col = row + dr, col + dc
# 유효한 위치인지 확인
if 0 <= new_row < 4 and 0 <= new_col < 4:
# 반대 방향으로 되돌아가는 것 방지
if (self.prev_dir == 'U' and dir_name == 'D') or \
(self.prev_dir == 'D' and dir_name == 'U') or \
(self.prev_dir == 'L' and dir_name == 'R') or \
(self.prev_dir == 'R' and dir_name == 'L'):
continue
# 새 보드 상태 생성
new_board = self.board.copy()
new_board[row][col] = new_board[new_row][new_col]
new_board[new_row][new_col] = 0
# 새 상태 생성
next_state = PuzzleState(new_board, (new_row, new_col),
self.moves + 1, dir_name)
next_states.append(next_state)
return next_states
|
이 예시에서 상태 표현은 다음 요소를 포함한다:
- 보드 배열: 현재 퍼즐 상태를 나타내는 4x4 배열
- 빈 칸 위치: 빈 칸의 (행, 열) 좌표
- 이동 횟수: 현재까지 수행한 이동 횟수(g(n))
- 이전 이동 방향: 중복 이동을 방지하기 위한 정보
또한 맨해튼 거리 휴리스틱을 사용하여 목표 상태까지의 최소 이동 횟수를 추정하고, 이를 한계값으로 사용한다.
참고 및 출처#