벨만 포드 알고리즘 - 네트워크 관련 측면

교수님께서 설명을 반대로 하셨다면 이해가 더 쉽지 않았을까?란 생각이 들고, 질문글에서 글씨체로 인해 y랑 v 오타난거로 꼽주는 교수덕분에 화나서 혼자 공부해서 적고 있다.

처음 이렇게 설명하시는데 좀 억지스럽다. 왜냐면 DP 알고리즘은 진짜 어렵기때문이다.

(DP 알고리즘은 패턴 찾기랑 비슷하다고 생각한다. 그래서 어렵다.)

이 알고리즘은 이전에 나오는 다익스트라 알고리즘과 목적이 동일하다. 검색하면 나오는 결론은 음수에서 최단 경로를 사용하는 알고리즘 정도이니 답답하다. 정말 음수가 나오는 상황에서 쓰려고 이런 알고리즘을 만들었을까? 전혀 아닌 것 같은데... 일단 왜 만들었는지를 중점으로 네트워크 측면에서 상상한 뇌피셜을 바탕으로 적어본다.

먼저 생각해봐야하는 점은 왜 이런 식이 나왔고, 어떤 형태로 굴러가는지이다.

교수님은 무려 노드가 6개인 그래프 친구로 설명을 시작하는데, 이런 방식으로 설명하는지 납득이 되지 않는다.
<= 이는 단순히 공식을 암기하여 수학 문제를 푸는 것과 동일한 것 같다.

왜 납득이 되지 않을까? 저 그림과 식만 봤을 때 왜 c(x,v)를 하고 dv(y)를 하는지 모른다. 

그래서 먼저 왜 저런 식이 나왔는지 생각해보자.
네트워크 라우팅 최단 경로를 구하는 알고리즘에서 다익스트알고리즘은 중앙 집중 알고리즘으로 소개된다. 이 알고리즘은 이미 모든 링크의 비용을 알고 있는 상태에서 사용한다.
벨만포드 알고리즘은 이웃의 노드만 알고 있는 상황에서 사용한다. 이것은 분산형이라고 말을 하고 명백히 다익스트라와 다른 상황이다.

이 차이가 중요하다. 주변 이웃만 알고 있으니 노트에 적어놓아야한다. 그리고 내가 아는 정보가 적으니 친구와 정보를 공유해야한다. 내가 아는 친구 A에게 가는 길의 비용이 얼마인지 조사하여 적고, 친구 A도 자기 나름대로 기록할 것이다. 이런 식으로 한번 적고, 정보를 공유하고, 다시 얼마나 걸리는지 조사하여 적어나간다.

그러니 주변의 값을 c(u,v)와 같이 알 수 있고, dv(z)는 내가 가지고 있는 테이블(노트)을 통해 가져올 수 있다.  DP알고리즘 특징이 테이블을 가지고 이 값을 업데이트해가는 방식이다. 그리고 위에 예제는 노드가 너무 많아서 테이블 그리기가 너무 버겁고 설명하기 힘들다. 그러니 더 복잡하고 알기 힘들다.

이런 노드 3개가 있고 테이블을 그린다.

각 노드는 처음엔 자기 자신이 연결된 비용 밖에 모른다. 그래서 다른 노드들에게 물어본다. 이것을 반복적이라고 책에선 표현하는데 계산이 끝날 때까지 반복적으로 물어본다. 그래서 메시지를 주고 받아 값을 업데이트한다.

먼저 2 0 1, 7 1 0은 y, z 테이블에서 메시지를 받아 업데이트하였고 이 값을 이용하여 자기 자신에서 y와 z를 가는 비용을 계산한다. 

이미 가지고 있는 값을 조사하는 D( )를 사용한다. 그럼으로 2 7에서 2 3으로 7 값이 업데이트된다.

업데이트 된 값은 다음 테이블에서 메시지를 주고 받아 업데이트 된다.

이제 내부가 어떻게 돌아가는지 알게 되었고, 처음 문제로 돌아가자.

여기서 보면 dv(z)가 5인 것은 각 노드 별로 계산하여 테이블에 있는 값을 가져와 계산이 가능한 것이었고, 현재 저렇게 갑자기 5가 되는건 우리가 눈대중으로(추상화)하여 5인 것을 알 수 있는 것이다. 다른 3,3도 다 동일한 이유다.

식 알려주고, 추상화하여 알려주는 건 "왜 저렇게 되는거지?"만 가득차고 이해가 안 되니 수업에 집중이 될리가 있는가?
그리고 수업을 하면서 모르면 책 보세요을 수십번을 한 강의 내에서 말하고 있으니 자기 자신이 수업을 못하는 것을 증명하고 있는게 아닌가? 참..답답하다.