2개의 댓글이 있습니다.
-
-
JongMan -
http://mathworld.wolfram.com/RelaxationMethods.html 아무래도 이쪽에서 연유한 것 같은데 :3
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
JongMan
Bellman-Ford 같은 그래프 알고리즘들은, 여러 간선에 대해서 완화(relax) 를 실행함으로써 이루어집니다. '완화'라는 것은 간선 (u,v) 에 대해서 최단거리 후보 d[u], d[v] 그리고 해당 간선의 가중치 w 가 있을 때 d[v] = min(d[v], d[u] + w) 라는 연산을 하는 것인데요. (아시겠지만)
CLRS 등의 유명한 교과서를 살펴보아도 왜 relax 라는 모호한 단어가 쓰이게 되었는지에 대한 설명은 없네요. 과연 이 애매한 단어는 왜 알고리즘 설명에 들어오게 되었을까요?
원고를 하다가 궁금해졌는데 혹시 여기에 대해서 아시는 분 있으신지? 수업시간에 교수님이 말씀하셨다던지, 뭐 이런 것에 희망을 걸어 봅니다.. ^^;;
덧. 제 추측은 선형계획법 문제를 해결할 때 쓰는 완화기법에서 이 이름이 따라온게 아닐까 하는 건데요. (Bellman-Ford 알고리즘이 Difference constraint system 을 푸는 데도 쓰인다는 데서 좀 더 그럴 듯 한.. ^^;;) Bellman 옹이 처음에 쓴 논문 원본을 찾을 수가 없어서.. 알 도리가 없네요 ㅜㅜ
16년 전