수색…


가중치 작업 스케줄링 알고리즘

가중치 작업 스케줄링 알고리즘은 또한 가중치 작업 선택 알고리즘으로 표시 될 수 있습니다.

문제는 시작 시간과 종료 시간이있는 특정 작업과 작업 완료시 얻는 수익을 고려해 볼 때 병렬로 두 가지 작업을 실행할 수 없다면 주어진 최대 이익은 얼마입니까?

이것은 Greedy Algorithm을 사용하여 활동 선택과 비슷하게 보이지만 추가 된 것이 있습니다. 즉, 완료된 작업 수를 최대화하는 대신 최대 이익을 얻는 데 집중합니다. 수행 된 작업의 수는 여기에서 중요하지 않습니다.

예제를 살펴 보겠습니다.

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    A    |    B    |    C    |    D    |    E    |    F    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (2,5)  |  (6,7)  |  (7,9)  |  (1,3)  |  (5,8)  |  (4,6)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    6    |    4    |    2    |    5    |    11   |    5    |
+-------------------------+---------+---------+---------+---------+---------+---------+

작업은 이름, 시작 및 종료 시간 및 이익으로 표시됩니다. 몇 차례 반복 한 후에 우리는 Job-AJob-E 를 수행 할 수 있는지를 알 수 있습니다. 최대 이익은 17입니다. 알고리즘을 사용하여이를 어떻게 찾을 수 있습니까?

우리가해야 할 첫 번째 일은 끝내는 순서로 작업을 마무리하는 것입니다. 왜 우리가이 일을합니까? 우리가 끝내는 시간이 덜 걸리는 일을 선택하면 다른 일을 선택하는 데 가장 많은 시간을 둡니다. 우리는 :

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

추가 임시 배열 Acc_Prof 의 크기가 n입니다. 여기서 n 은 총 작업 수를 나타냅니다. 여기에는 작업 수행의 누적 된 최대 이익이 포함됩니다. 이해 못 하겠어? 기다려 봐. 각 작업의 이익으로 배열의 값을 초기화합니다. 즉, Acc_Prof [i]i 번째 작업 수행의 이익을 우선적으로 유지합니다.

+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

이제 위치 2i 로 표시하고 위치 1j 로 표시합니다. 내가 N + 1이 될 때까지 우리의 전략이 반복 될 때마다 I-1 이후 1에서 J를 반복하는 것입니다, 우리는 1 전을 증가합니다.

                               j        i

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

작업 [I]과 작업 [J] 중복, 즉, 작업 [J]의 종료 시간은 작업보다 큰 경우 [I]의 시작 시간은 다음 두 가지 작업을 함께 수행 할 수없는 경우 우리는 확인한다. 그러나 겹치지 않으면 Acc_Prof [j] + Profit [i]> Acc_Prof [i]인지 확인 합니다. 이 경우 Acc_Prof [i] = Acc_Prof [j] + Profit [i]를 업데이트 합니다. 그건:

if Job[j].finish_time <= Job[i].start_time
    if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
        Acc_Prof[i] = Acc_Prof[j] + Profit[i]
    endif
endif

여기서 Acc_Prof [j] + Profit [i] 는이 두 작업을 수행 한 누적 된 이익을 나타냅니다. 우리의 예를 들어 보겠습니다.

여기서 Job [j]Job [i] 와 중복됩니다. 그래서 이것들은 함께 할 수 없습니다. 우리 J는 I-1과 동일하기 때문에, 우리는 3 I + 1 i 값을 증가. 그리고 우리는 j = 1로 만듭니다.

                               j                   i

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

이제 작업 [j]작업 [i] 은 겹치지 않습니다. 이 두 작업을 선택하여 얻을 수있는 총 이익은 다음과 같습니다 : Acc_Prof [j] + Profit [i] = 5 + 5 = 10 이는 Acc_Prof [i] 보다 큽니다 . 따라서 Acc_Prof [i] = 10을 업데이트합니다. 또한 j 를 1 씩 증가시킵니다.

                                         j         i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

여기서 Job [j]Job [i] 와 겹치며 ji-1 과 같습니다. 그래서 i 를 1 씩 증가시키고 j = 1로 만듭니다. 우리는,

                               j                             i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

이제 Job [j]Job [i] 는 겹치지 않습니다. Acc_Prof [i] 보다 큰 5 + 4 = 9 의 누적 이익을 얻습니다. Acc_Prof [i] = 9를 업데이트하고 j 를 1 씩 증가시킵니다.

                                         j                   i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    9    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

다시 Job [j]Job [i] 는 겹치지 않습니다. 축적 된 이익은 6 + 4 = 10 이며 이는 Acc_Prof [i] 보다 큽니다 . Acc_Prof [i] = 10을 다시 업데이트합니다. j 를 1 씩 증가시킵니다.

                                                   j         i
 
+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    10   |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+

이 프로세스를 계속하면 i를 사용하여 전체 테이블을 반복 한 후 테이블이 마침내 다음과 같이 보입니다.

+-------------------------+---------+---------+---------+---------+---------+---------+
|          Name           |    D    |    A    |    F    |    B    |    E    |    C    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)|  (1,3)  |  (2,5)  |  (4,6)  |  (6,7)  |  (5,8)  |  (7,9)  |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Profit          |    5    |    6    |    5    |    4    |    11   |    2    |
+-------------------------+---------+---------+---------+---------+---------+---------+
|         Acc_Prof        |    5    |    6    |    10   |    14   |    17   |    8    |
+-------------------------+---------+---------+---------+---------+---------+---------+

* 문서를 짧게 만들려면 몇 단계를 건너 뛰었습니다.

Acc_Prof 배열을 반복 할 경우 최대 이익은 17이됩니다 ! 의사 코드 :

Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
    for j -> 1 to i-1
        if Job[j].finish_time <= Job[i].start_time
            if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
                Acc_Prof[i] = Acc_Prof[j] + Profit[i]
            endif
        endif
    endfor
endfor

maxProfit = 0
for i -> 1 to n
    if maxProfit < Acc_Prof[i]
        maxProfit = Acc_Prof[i]
return maxProfit

Acc_Prof 배열을 채우는 복잡성은 O (n 2 )입니다. 배열 탐색에는 O (n)이 필요 합니다. 따라서이 알고리즘의 전체 복잡도는 O (n 2 )입니다.

이제 우리는 작업이 최대의 이익을 얻기 위해 수행 된 찾을하려는 경우, 우리는 역순으로 배열을 통과해야하고 Acc_Prof가 maxProfit 일치하는 경우, 우리의 이익을 스택에 작업의 이름을 누르고 빼는 것 그 직업을 maxProfit에서 . maxProfit> 0 이 될 때까지 또는 Acc_Prof 배열의 시작점에 도달 할 때까지이 작업을 수행합니다. 의사 코드는 다음과 같습니다.

Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
    if maxProfit is equal to Acc_Prof[i]
        S.push(Job[i].name
        maxProfit = maxProfit - Job[i].profit
    endif
endfor

이 절차의 복잡성은 다음과 같습니다. O (n) .

한 가지 기억해야 할 것은 최대 이익을 제공 할 수있는 여러 개의 작업 일정이있는 경우이 절차를 통해서만 하나의 작업 일정을 찾을 수 있다는 것입니다.



Modified text is an extract of the original Stack Overflow Documentation
아래 라이선스 CC BY-SA 3.0
와 제휴하지 않음 Stack Overflow