'Algorithm'에 해당되는 글 1건

  1. 2013.01.07 [Algorithm] Greedy Algorithm (1)

욕심쟁이 기법이라고 번역되는 Greedy Algorithm은 어떤 문제를 해결해나가는 과정에서 


'현재 단계에서 내리는 결정이 다음 단계에 어떤 영향을 줄까'

'이전에 거쳐간 단계에서 다른 걸 선택하는 게 더 좋지 않았나'


이런 걱정 따위 하지않고 현재 주어진 상황에서 최대한의 이익을 얻는 방향을 선택하는 것이다.


앞뒤 가리지 않고 눈 앞의 이득만 보고 달려드는 꼴이긴 하지만, 이 방법은 때때로 구현의 간단함에 비해 매우 효율적이고 정확한 결과를 얻을 수 있다. 


Greedy Algorithm을 문제에 적용하기 위해서는 먼저 내가 얻는 이익을 적절하게 함수화 하는것이 중요하다. 현재 처한 상황에서, 혹은 해답을 찾아가기 시작할 때 내가 선택할 수 있는 모든 경우에 대해 이 함수 값을 계산해두고 가장 큰 값을 리턴하는 경로를 따라가면 된다. 


이익 함수를 어떻게 정의하는지가 중요하다는 것은 다음의 예제를 통해 알 수 있다.


예제1. Scheduling based on greedy algorithm

n개의 일(Job)이 주어지고, 각각의 일에 대한 중요도(w, weight)와 길이(l, length)를 알고 있을 때 가중치가 적용된 업무 완료 시간(weighted completion time)은 다음과 같이 정의된다.


WCT = Sum of wi * ti


i는 1부터 n까지의 값을 가지는 각각의 일에 대한 인덱스이고, ti는 i번째 일이 완료된 시간이다.


2가지의 일 j1, j2가 w1 = 5, l1= 2, w2 = 3, l2 = 1로 주어졌다.

이익함수는 말 그대로 어떤 선택을 했을 때 내가 얻는 이익을 함수화 시킨것이다. 

정확히 말하면 이익 - 손해 즉 알짜이익을 함수로 나타내는 것이다.


중요도가 높으면 이익, 길이가 길면 손해라고 가정했을때, 가장 간단한 이익함수는 다음과 같을 것이다.


함수 A : wi - li

함수 B : wi / li


주어진 2가지 일에 대해 각각의 함수를 적용시켜보면 그 결과는 다음과 같다.


A(j1) = w1 - l1 = 3

A(j2) = w2 - l2 = 2


B(j1) = w1 / l1 = 2.5

B(j2) = w2 / l2 = 3


따라서 이익함수 A로 스케쥴을 정한다면 첫번째 일을 수행한 후 두번째 일을 수행할 것이고, 이익함수 B로 스케쥴을 정한다면 두번째 일을 스행한 후 첫번째 일을 수행할 것이다.


각각의 경우에 대한 WCT는 다음과 같다.


이익함수 A를 사용했을 때의 WCT = 5 * 2 + 3 * (2 + 1) = 19

이익함수 B를 사용했을 때의 WCT = 3 * 1 + 5 * (1 + 2) = 18


따라서 wi / li 를 이익함수로 사용했을 때 더 작은 WCT를 얻는다는 걸 확인할 수 있다.


이제 Greedy Algorithm이 실패하는 경우에 대해 알아보자.




* 작성중인 글입니다.



'Algorithm' 카테고리의 다른 글

[Algorithm] Greedy Algorithm  (1) 2013.01.07

댓글을 달아 주세요

  1. ㅎㅎ  댓글주소  수정/삭제  댓글쓰기

    잘보고 갑니다 ㅎㅎ

    2013.01.09 12:17

1 

글 보관함

카운터

Total : 29,413 / Today : 0 / Yesterday : 14
get rsstistory!