근사 알고리즘(2) 작업 스케줄링 문제, 클러스터링 문제

<작업 스케줄링 문제>

작업스케줄링은 시간이 시작 시간이 가장 빠른 것을 기준으로 스케줄링할 때는 해를 구할 수 있지만, 

그렇지 않을 때에는 해를 구할 수 없다.

 

여기서는 배정된 작업에 대해서 가장 빨리 끝나는 기계에 새 작업을 배정한다.

 

-Approx_JobScheduling 슈도 코드-

 

입력: n개의 작업, 각 작업 수행 시간 ti, i = 1,2, ... n, 기계 Mj, j = 1,2, ...m

출력: 모든 작업이 종료된 시간

1  for j = 1to m

2      L[j] = 0         // L[j] = 기계 Mj에 배정된 마지막 작업의 종료 시간

3  for i = 1 to n {

4      min = 1

5      for j = 2 to m {     // 가장 일찍 끝나는 기계를 찾는다.

6         if(L[j] < L[min]) {

7           min = j

           }

8      작업 i를 기계 Mmin에 배정한다.

9      L[min] = L[min] + ti

       }

     }

10  return 가장 늦은 작업 종료 시간

 

line2:  L[기계순번] = 기계가 총 일하는 시간  

line6: L[2] < L[1] 기계1과 기계2부터 비교하기 시작해서 더 작은  기계 인덱스를 min 값에 채워넣으면서 시간이 최소인 기계 인덱스를 찾아나간다.

---

<클러스터링 문제>

 

-Approx_k_Clusters 슈도 코드-

 

입력: 2차 평면상의 n개의 점 xi, i=0,1...,n-1, 그룹의 수 k > 1

출력: k개의 클러스터 및 각 클러스터의 센터

1  C[1] = r, 단, xr은 n개의 점 중에서 랜덤하게 선택된 점이다.

2  for j = 2 to k {

3     for i = 0 to n-1 {  // 모든 점을 한번씩 다 검토

4       if(xi != 센터)

5         xi와 각 센터까지의 거리를 계산하여, xi와 가장 가까운 센터까지의 거리를 D[i]에 저장한다.

       }

6     C[j] = i, 단, i는 배열 D의 가장 큰 원소의 인덱스이고, xi는 센터가 아니다.

    }

7  센터가 아닌 각 점 xi로부터 앞서 찾은 k개의 센터까지 거리를 각각 계산하고 그 중에 가장 짧은 거리의 센터를 찾는다.

     이때 점 xi는 가장 가까운 센터의 클러스터에 속하게 된다.

8  return 배열 C와 각 클러스터에 속한 점들의 리스트