슈도플로우 알고리즘

1992년 Dorit Hochbaum이 개발한 슈도플로우 알고리즘(Pseudoflow Algorithm)은 방향성 비순환 그래프(directed acyclic graph)에서 최대 가중치 폐쇄(maximum weighted closure)를 계산하는 다항 시간 알고리즘입니다. 채광 분야에서 이 알고리즘은 기존 방법보다 효율적으로 최종 채굴 한계(ultimate pit limit) 문제를 해결합니다. 실행 가능한 슈도플로우(feasible pseudoflow)를 유지하고 음수 비용 노드를 반복적으로 제거함으로써, 산업 규모의 블록 모델에서도 거의 최적의 실질적인 성능을 달성합니다.