알고리즘 기법[부분 탐색] - 탐욕적 방법(Greedy method)

탐욕적 방법(Greedy method)

전체 문제가 여러 단계로 구성되어 있는 경우에 각 단계별로 최적 해를

구함으로써 전체 문제를 해결하려는 알고리즘 설계 방법.

 

  -수학적으로 탐색 영역을 배제함.

  -문제를 해결하기 위해서 해가 될 수 있는 모든 부분(전체적 최적화)을 탐색하는 것이 아니라,

    탐색할 부분을 제한(부분적 최적해하여 원하는 해를 구하는 방법.

  -전체적 최적화에 도달하지 못하는 경우가 있을 수 있음.

  -올바른 해를 구하기 위해 탐색을 배제한 부분에 대한 수학적 검증이 필요.

Greedy 예시 및 알고리즘

1. CPU 스케줄링(scheduling) 문제

 선점을 허용하지 않는 하나의 CPU와 n개의 작업이 있을 때 CPU 스케줄링은 작업 시간의 크기를 기준으로 오름차순 정렬하여 작업 시간이 가장 짧은 작업을 먼저 처리하도록 하는 최소 작업 우선(shortest job first) 알고리즘이 대기 시간의 합을 최소화하는 최적 해이다.

  → 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식.

  → 평균 대기시간을 최소로 만드는 걸 최적으로 두고 있음.

 

 만일 여러 개의 CPU를 사용하는 컴퓨터인 경우, 대기 시간을 최적화하는 방법도 작업시간의 크기를 기준으로 오름차순 정렬하여 최소 작업 우선(shortest job first) 알고리즘을 적용할 수 있으나 이 경우에는 여러 개의 최적 해가 있을 수 있다.

3개의 CPU가 있을 때 시간 최소화

2. 온라인 빈팩(bin-packing) 알고리즘

n개의 S1, S2, ..., Sn(0 ≤ Si ≤ 1) 자료를 최소의 가방(bin)에 사용하여 넣는(packing) 방법을 찾는 알고리즘.

 

자료가 {0.3, 0.6, 0.4, 0.8, 0.1, 0.7, 0.1}순으로 입력될 때 온라인으로 처리되는 Next-Fit, First-Fit, Best-Fit 알고리즘과 Offline-First-fit 알고 리즘이 있다.

 ① Next-Fit: 빈 자리에 입력 순으로 넣는다.

 ② First-Fit: 자료를 이미 사용한 상자에 넣을 수 있을 때는 사용 가능한 최초의 상자에 넣고, 그렇지 않으면

     새로운 상자에 넣는다.

 ③ Best-Fit: 자료를 이미 사용한 상자에 넣을 수 있을 때는 상자를 차례로 검색하여 가장 적합한

     (1에 가까운 = 꽉 채울 수 있는) 상자에 넣고, 그렇지 않으면 새로운 상자에 넣는다.

 ④ off-line First-fit: 자료를 내림차순으로 정렬하여 가장 효율적으로 집어넣는다.

  -온라인 알고리즘은 자료 하나씩 입력 즉시 처리해야 하고, 처리한 결과는 수정할 수 없으며, 대부분 최적화가 어렵다.

  -온라인 알고리즘의 예로 CPU 스케줄러, bin-packing(가방에 물건 넣기) 알고리즘에서 Next-Fit, First-Fit, Best-Fit 등이

    있다.

  -오프라인 알고리즘은 자료를 모아서 가공(정렬)하여 처리하기 때문에 최적화가 용이하다.

 

*온라인, 오프라인 알고리즘에 관한 자세한 내용은 후에 포스팅을 할 예정.