[OR-Tools 스터디] Network Flows

cs에서 많은 문제들은 노드들과 그들 사이를 연결하는 링크들로 구성된 그래프에 의해 나타낼 수 있다.

예제들은 network flow문제들로, 철로 시스템과 같은 화물 운송 혹은 네트워크를 통한 자료들을 포함하고 있다. 

 

우리는 노드들이 도시들이고 호가 그들 사이의 철로인 그래프로 network flow를 나타낼 수 있다. 

(그들을 flows라고도 부르는데, 그들의 특성들이 파이프의 네트워크를 통해 흘러가는 물들과 유사하기 때문이다.)

 

network flow들에서 핵심 constraint는 각 호들이 capacity를 가지고 있다는 것이다. 

즉, 고정된 시간 내에 호를 가로질러 수송될 수 있는 최대 양을 말한다. 

 

maximum flow problem은 capacity constraint의 영향을 받는 network 내에서 모든 호들을 가로질러 운송될 수 있는 최대 전체 양을 결정하기 위한 것이다. 

 

이 문제를 가장 처음으로 연구한 사람이 1930년 러시아 수학자 A.N.Tolstoi이다. 

아래 지도는 그가 최대 flow를 찾기를 원했던 실제 철도 network를 보여준다. 

 

OR-Tool은 그래프 라이브러리들에서 network flow 문제에 대한 몇가지 solver들을 제공해준다.

 

추후 섹션들에서는 network flow 문제들의 예제와 그것들을 어떻게 해결하는지를 보여준다. 

• Maximum Flows
• Minimum Cost Flows
• Assignment as a Minimum Cost Flows

 

Reference :

https://developers.google.com/optimization/flow

네트워크 흐름  |  OR-Tools  |  Google Developers