랜덤 알고리듬이라니...
그래프 관련 알고리듬을 공부할 일이 생겼는데 모든 경우의 수가 너무 많기 때문에 전부 구하기 어려운 계산을 난수를 사용해서 계산하기도 한다는 것을 알게 되었다.
문제는 200개의 노드를 가지는 그래프를 주고 contraction 알고리듬을 사용해서 minimal cut을 구하라는 것인데 반신 반의하며 문제를 풀어보니 대부분의 경우 100번 반복하기도 전에 정답을 구해내는 것을 보니 참 신기하다는 생각이 든다. 그리고 몇번 이상 계산하면 답이 틀릴 확률을 얼마 이하까지 낮출수 있다는 것을 계산하는 건 더 놀랍고... 근데 알고리듬 분석하고 확률적인 계산하는 것은 솔직히 아직까지 잘 모르겠다. 수학적인 배경을 더 갖춰야 할듯...
같은 프로그램을 나의 사랑스러운 에어에서 돌리니 ruby 1.9.3 (p125)에서는 228초가 걸리고 macruby 0.12 (1.9.2)에서는 158초가 걸린 반면 직장의 구닥다리(dual core 2.4G) 데스크탑에서 돌리니 ruby 1.9.3 (p194)에서 131초가 걸린다. 갑자기 에어가 조금 덜 사랑스러워졌다. -.-;
너 그것보다 좀 더 잘할수 있지 않아? 그게 최선이야?
문제는 200개의 노드를 가지는 그래프를 주고 contraction 알고리듬을 사용해서 minimal cut을 구하라는 것인데 반신 반의하며 문제를 풀어보니 대부분의 경우 100번 반복하기도 전에 정답을 구해내는 것을 보니 참 신기하다는 생각이 든다. 그리고 몇번 이상 계산하면 답이 틀릴 확률을 얼마 이하까지 낮출수 있다는 것을 계산하는 건 더 놀랍고... 근데 알고리듬 분석하고 확률적인 계산하는 것은 솔직히 아직까지 잘 모르겠다. 수학적인 배경을 더 갖춰야 할듯...
같은 프로그램을 나의 사랑스러운 에어에서 돌리니 ruby 1.9.3 (p125)에서는 228초가 걸리고 macruby 0.12 (1.9.2)에서는 158초가 걸린 반면 직장의 구닥다리(dual core 2.4G) 데스크탑에서 돌리니 ruby 1.9.3 (p194)에서 131초가 걸린다. 갑자기 에어가 조금 덜 사랑스러워졌다. -.-;
너 그것보다 좀 더 잘할수 있지 않아? 그게 최선이야?
댓글