기말고사를 위하여

그래프에 대한 기초적인 지식은 생략

 

최소비용흐름과 최단경로문제는 같은 문제이고 

 

최대 흐름 문제는 조금 다르다 (책에서는 같다고 설명 되어 있는데 이건 좀 어거지임 내가 봤을 때)

 

최소비용 흐름 = 최단경로 문제

 

경로의 비용을 경로의 거리와 동일하게 생각하면 됨 .

 

이때 우리는 최단경로문제를 푸는 알고리즘을 배웠음 

 

다익스트라 알고리즘임 

 

다익스트라 알고리즘을 사용하기 위해선 조건이 있음. 

 

모든 마디 (edge) 의 값 (최단경로 문제에서는 거리, 최소비용 흐름 문제에서는 비용) 이 0보다 커야한다는 것임 

(0이 되는지는 좀 더 생각해봐야함)

 

다익스트라 알고리즘이 어떻게 진행되는지는 잘 알거니까 넘어가고 

 

다익스트라가 최단경로문제를 해결하기 위한 알고리즘이란걸 상기하고 넘어가자.

 

만약에 edge의 값이 음수가 존재한다면 어떻게 될까?

 

이는 벨만포드 알고리즘으로 해결이 가능함

 

벨만포드 알고리즘의 답은 크게 2개로 나뉘어짐 

 

1. 정확한 최소비용 경로를 구한다.

 

2. 최소비용의 경로를 따라가다보면 그 값이 음의 무한대로 발산하게 되며, 회로를 벗어나지 못하고 순환함.

 

 

 

음수가 있어도 눈으로 보다보면 엥 이게 최소비용 아냐? 하고 나오는게 1번 케이스

 

계속 돌려도 엥 이상하다 싶으면 2번 케이스임 

 

이렇게 값이 나뉘는 지점은 "음수 회로" 의 존재여부임 . 

 

"음수회로" 가 존재한다면 음수 회로를 계속 돌게되고, 값은  -  로 발산하게 됨.

 

min 비용  

 

sub. to  ???

 

에서 min 이 자꾸 감소하니까 발산한다고 표현한거임 

 

 

근데 벨만포드 알고리즘은 수업시간에 다루지 않았음 시험에 안 나옴 

 

그러니까 우리는 다익스트라 알고리즘만 잘 풀면 될것으로 추측됨 . (중간고사에 안 나왔으니까 + 데알에 나오는 걸 모를거임)

 

 

그럼 지금 문제가 총 3개중에서 2개가 풀린거임 즉, 최대흐름문제만 남은거임

 

 

최대흐름 문제는 말 그대로 "흐름을 최대화" 하는 문제임 .

 

처음 이 문제를 볼 때 아무것도 배우지 않은 상태여도 문제를 풀 순 있음

 

생명과학 유전마냥 귀류법 노가다를 통해서 음 ? 이게 더 큰데 하면서 찾으면 됨 

 

근데 직관적으로 봤을 때 보낼 수 있는 흐름중에서 제일 큰 것만 골라서 보내면 값이 제일 커질 것 같음

 

이걸 "그리드 알고리즘" 이라고 함. 근데 이건 항상 최적해 = 최대 흐름 을 찾아낼 수 없음

 

따라서 "잔여용량" 이라는 개념을 도입함

 

잔여용량이랑 그 방향으로 더 보낼 수 있는 양을 의미함 

 

용량이 8인 마디에 흐름을 6만큼 증가시키면 잔여 용량은 2인거임 

      잔여용량 : 2                 8에  6만큼 흘렸으니 2만큼 더 보낼 수 있음 

           --------------------> 

          <---------------------

                        6                 역방향으로 6만큼 흘려보낼 수 있음 

 

이때----------------> 방향 잔여용량이 0이면 더 흐름을 보낼 수 없다는 소리니까 

 

max 용량 

 

sub .to  ?? 

 

개선이 불가능하다 .> 최적해다 .

 

문제에서 최대흐름을 구하라? 라고 하면

 

1. 잔여용량 네트워크를 잘 그린다.

 

여기는 내가 설명해줄게 

 

 

 

이제 다음에 공부할 건 

 

최소비용 "흐름" 문제이다.

 

최소 비용으로 물건을 운반해야하는데, 제약조건에 흐름의 양 이란 것이 추가된 거라고 생각하면 편하다.

 

s 에서 t 까지 물을 5만리터 보내고 싶은데, 경로가 다양하고,  그 경로는 배수관의 사이즈가 제각각인 상황이다.

 

이때 물 1리터를 그 배수관을 통해 보낼려면 비용이 x만큼 든다는 것임.