명지대학교 산업경영공학과 경영과학1 7주차 강의내용

소개

"명지대학교 산업경영공학과 경영과학1 7주차"에 대한 강의내용입니다.

목차

없음

본문내용

조합적 해법(Combinatorial Algorithm)
흐름증가경로 알고리듬(augmenting path algorithm)
s에서 t까지 흐름을 보낼 수 있는 경로가 있으면, 그 경로를 통해 흘려보낼 수 있는 최대 흐름양을 계속해서 보낸다.

잔여용량 네트워크

붉은색 경로로 20만큼 보낸다.
(1번 → 2번 → 4번 → 5번)

20, 40, 40 → 0, 20, 20

이번엔 두 번째 붉은 경로로 5만큼 보낸다.
(30, 5, 20 중 가장 작은 값)

30, 5, 20 → 25, 0, 15

세 번째 붉은 경로로 10만큼 보낸다. min{25, 10} = 10

min{20, 40, 40} = 20
min{30, 5, 20} = 5
min{25, 10} = 10

경로에 대한 업데이트가 이뤄지는 위 방식에 대해 다른 전송 경로도 계속해서 찾아내는 작업을 진행한다. : 흐름증가 알고리즘
이 경로 중 최적인 경로는 어떻게 찾는가? : 역방향 흐름

부분적으로 현재 흐름을 감소시키는 역방향 흐름
호의 방향(정방향)과 반대되는 흐름을 취해보는 것

역방향흐름 = 잔여흐름

노드1 → 노드2의 용량은 10이고 현재 7이 흐르고 있음.
잔여 흐름양 = 3

노드1 → 노드2로 3만큼 흘려주고 기존의 7은 반대로 흘려줌

즉 현재 흐름량만큼 줄여줄 수 있음을 의미함.

참고자료

· 없음