Set Covering 문제는 주어진 특정 집합의 부분집합들을 선택하여, 해당 부분집합들의 합집합을 통해 특정 집합의 모든 요소를 포함시키는 문제입니다. 이때 가능한 적은 수의 부분집합을 골라내는 것이 목표입니다.
예를 들어, 특정 집합에 5개의 요소가 있을 때, 5개의 요소를 포함하는 여러가지의 부분집합이 있다고 가정해 보겠습니다.
아래 그림과 같은 상황이라면 두 개의 부분집합만으로도 5개의 모든 요소를 커버할 수 있습니다.
신도시 계획을 예로 들어보면, 소방서의 최적 위치를 정하는 문제에 Set Covering 알고리즘을 활용할 수 있습니다.
신도시의 주요 지점을 노드로 표현하고, 화재 발생 시 이동 가능한 시간 정보를 이용하여 노드를 커버할 수 있는 집합을 구성합니다.
이를 통해 몇 개의 소방서를 설치해야 모든 주요 지점을 커버할 수 있을지 시뮬레이션할 수 있습니다.
예를 들어, A, B, C, D 네 개의 주요 지점이 있고, 소방서 후보 위치가 X, Y, Z 세 곳이라고 가정할 수 있습니다.
X 소방서는 A와 B를, Y 소방서는 B와 C를, Z 소방서는 C와 D를 커버할 수 있다면, {X, Z} 두 곳에 소방서를 설치하는 것이 최소 개수의 소방서로 모든 지점을 커버하는 최적 해가 됩니다.
이러한 Set Covering 문제는 다양한 분야에서 활용되며, 특히 최소한의 자원으로 최대 범위를 커버해야 하는 상황에서 효과적으로 사용이 가능합니다.
이를 해결하기 위해 Mixed Integer Programming (MIP)이나 메타휴리스틱(Meta-heuristic) 알고리즘을 사용할 수 있습니다.
MIP는 문제를 선형 계획법으로 모델링하고, 변수 중 일부를 정수로 제한하여 최적 해를 찾는 방법입니다.
메타휴리스틱 알고리즘은 다양한 탐색 기법을 활용하여 최적 해에 근접한 해를 효율적으로 찾는 방법입니다.
이번에는 휴리스틱 방법을 이용한 해결 방안을 살펴보겠습니다.
이 방법은 완벽한 최적해를 보장하지는 않지만, 복잡한 문제를 빠르고 간단하게 풀 수 있는 실용적인 접근 방식입니다.
def setCover(allset, subsets):
# allset: 전체 요소의 집합
# subsets: 각 집합들이 포함하고 있는 요소의 집합 리스트
# solution: 선택된 최소한의 부분집합
allset = set(allset) # 집합으로 변환
selectedSubsets = [] # 최종 선택된 부분집합 리스트
coveredElements = set() # 현재까지 커버된 요소
while coveredElements != allset:
# 아직 커버되지 않은 요소가 남아있으면 반복
bestSubset = max(subsets, key=lambda s: len(s - coveredElements))
selectedSubsets.append(bestSubset)
coveredElements |= bestSubset # 새로운 집합을 커버된 요소에 추가
subsets.remove(bestSubset) # 선택된 집합은 목록에서 제거
return selectedSubsets
allset = {0, 1, 2, 3, 4}
subsets = [{0, 1, 4}, {1, 2}, {1, 3}, {2, 3}]
solution = setCover(allset, subsets)
print(solution)
Python
복사
결과는 아래와 같습니다.
[{0, 1, 4}, {2, 3}]
Python
복사
Keyword: Logistics Optimization, 물류 최적화, 파이썬, Python, 선형계획법, Linear Programming, Mixed Integer Programming, Google OR Tools
Reference
[1]
