네트워크와 알고리즘 수업을 듣는데 모형화 후에, 답을 구해보고 싶어서 찾아보니 matlab을 사용하면 쉽게 풀이 가능하네요.
네트워크로 모형화했다고 하더라도 matlab으로 문제를 풀이할 때는 행렬로 자료를 입력해서 답을 구합니다.
방법은 다음 링크를 보시면 있습니다.
최단경로문제 Shortest path problem
http://www.mathworks.co.kr/kr/help/bioinfo/ref/graphshortestpath.html
최대유량문제 Maximum flow problem
http://www.mathworks.co.kr/kr/help/bioinfo/ref/graphmaxflow.html
최단경로문제는 유량문제에서 유량의 lower bound capacity와 upper bound capacity가 각각 0, 1의 정수인 특이한 경우의 문제라고 생각할 수 있다는 재미있는 사실.
수송문제 Transportation problem
http://www.mathworks.co.kr/kr/help/optim/ug/linprog.html#f414218
수송문제는 경영과학에서 선형계획법 Linear programming으로 풀이 가능합니다. 네트워크로 모형화해도 행렬로 나타내야 하는데, 그걸 다시 각각 변수에 따라 행렬로 나타내서 푸는게 자료 입력하는데 편하네요. 다른 방법이 있는지 교수님께 여쭤봐야겠음.
수송문제의 답은 정수로 나와야 하므로 아래를 사용해야함
'노트정리 > 그래프 이론 graph theory' 카테고리의 다른 글
| 자바에서 JGraphT 를 써서 Christofides의 알고리즘 구현하기 (2) (0) | 2018.05.26 |
|---|---|
| 자바에서 JGraphT 를 써서 Christofides의 알고리즘 구현하기 (1) (0) | 2018.05.26 |
| JGraphT를 써서 최소걸침나무(minimum spanning tree)를 구현할 때 주의 점 (0) | 2017.06.27 |
| Robert Sedgewick , Kevin Wayne (2011), Algorithms 4th edition, Pearson. (0) | 2016.05.03 |
| JGraphT. 그래프(graph 또는 네트워크 network) 관련한 알고리즘을 자바에서 구현할 때 편리한 라이브러리 (0) | 2016.04.29 |
