최소 비용 알고리즘 편집하기

최소 비용 알고리즘(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.
==각주==
[[분류:알고리즘]]
[[분류:그래프 이론]]