최소 비용 알고리즘

최소 비용 알고리즘(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.