최소 비용 알고리즘(Minimum cost algorithm, 最小費用算法)은 주어진 조건하에서 전체 비용의 합을 최소화하는 경로, 흐름, 또는 네트워크 구조를 찾기 위한 알고리즘이다.
개요
최소 비용 알고리즘은 그래프 이론, 네트워크 최적화, 물류 계획, 공급망 설계 등 다양한 분야에서 사용된다. 이 알고리즘들은 주어진 그래프에서 비용 함수에 따라 특정 조건을 만족시키면서 전체 비용을 최소화하는 경로 또는 구조를 구하는 데 사용된다.
최소 비용 경로 문제 유형
최소 비용 경로(Min-Cost Path) 문제는 입력 그래프 G = (V, E; C)에서 정의된 비용 함수 C에 따라 다음과 같은 세 가지 유형으로 분류된다.
- 단일 쌍(Single Pair): 정점 s에서 정점 t로의 최소 비용 경로 C*(s, t)를 구함
- 단일 시작점(Single Source): 정점 s에서 그래프 내 모든 정점 j ∈ V까지의 최소 비용 C*(s, j)를 구함
- 모든 쌍(All Pairs): 그래프 내 모든 정점 쌍 (i, j)에 대한 최소 비용 C*(i, j)를 구함
이들 문제는 모두 동적 계획법(dynamic programming)의 원리에 기반하며, C*(i, j)를 구할 수 있는 알고리즘은 최적 경로 또한 복원할 수 있다.
주요 문제 유형
- 최소 비용 네트워크 흐름 문제: 용량이 정의된 네트워크에서 흐름을 최대화하면서 총 비용을 최소화
- 최소 비용 최대 흐름 문제: 유량과 비용의 복합 최적화 문제
- 최소 비용 스패닝 트리 문제: 모든 정점을 포함하는 최소 비용의 트리 구조 탐색
- 운송 문제: 공급지와 수요지 간 운송 비용 최소화
- 할당 문제: 최소 비용으로 작업을 자원에 배정
주요 알고리즘
- 벨만-포드 알고리즘: 음의 가중치를 포함한 최소 경로 계산
- 존슨 알고리즘: 모든 쌍 최단 경로 문제에서 효율적
- 크루스칼 알고리즘: 최소 비용 스패닝 트리 구성
- 프림 알고리즘: 점진적 방식의 최소 스패닝 트리 탐색
- 포드-풀커슨 알고리즘: 최대 유량 계산, 최소 비용 흐름 알고리즘과 병행 사용 가능
예시
다음은 최소 비용 흐름의 간단한 예시이다.
그래프:
A --(용량 5, 비용 2)--> B --(용량 3, 비용 1)--> C A --(용량 4, 비용 3)--> C
A에서 C로 가능한 경로 중 최소 비용은 A → B → C로, 총 비용은 2 + 1 = 3이다. 직접 연결된 경로 A → C의 비용은 3이므로 동일하지만, 흐름 제한 등 조건에 따라 최적 경로는 달라질 수 있다.
응용
- 물류 및 운송 최적화
- 통신 및 전력 네트워크 설계
- 생산 및 자원 계획
- 교통 흐름 설계 및 비용 절감 분석
같이 보기
참고 문헌
- Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.