dynamic-programming
Selección de actividad ponderada
Buscar..
Algoritmo de programación de trabajo ponderado
El algoritmo ponderado de programación de trabajos también se puede denotar como algoritmo ponderado de selección de actividades.
El problema es que, dados ciertos trabajos con su hora de inicio y finalización, y el beneficio que obtiene cuando termina el trabajo, ¿cuál es el beneficio máximo que puede obtener dado que no se pueden ejecutar dos trabajos en paralelo?
Este se parece a la Selección de Actividad usando el Algoritmo Greedy, pero hay un giro adicional. Es decir, en lugar de maximizar el número de trabajos finalizados, nos centramos en obtener el máximo beneficio. La cantidad de trabajos realizados no importa aquí.
Veamos un ejemplo:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Los trabajos se indican con un nombre, su hora de inicio y finalización y las ganancias. Después de algunas iteraciones, podemos averiguar si realizamos Job-A y Job-E , podemos obtener el máximo beneficio de 17. ¿Cómo descubrir esto utilizando un algoritmo?
Lo primero que hacemos es clasificar los trabajos por su tiempo de finalización en orden no decreciente. ¿Por qué hacemos esto? Es porque si seleccionamos un trabajo que demora menos tiempo en terminar, dejamos la mayor cantidad de tiempo para elegir otros trabajos. Tenemos:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Tendremos una matriz temporal adicional Acc_Prof de tamaño n (Aquí, n indica el número total de trabajos). Esto contendrá el beneficio acumulado máximo de realizar los trabajos. ¿No lo entiendes? Espera y mira. Inicializaremos los valores de la matriz con el beneficio de cada trabajo. Eso significa que Acc_Prof [i] al principio tendrá el beneficio de realizar el trabajo i-th .
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ahora denotemos la posición 2 con i , y la posición 1 se denotará con j . Nuestra estrategia será iterar j de 1 a i-1 y después de cada iteración, incrementaremos i en 1, hasta que i se convierta en n + 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Verificamos si la Tarea [i] y la Tarea [j] se superponen, es decir, si la hora de finalización de la Tarea [j] es mayor que la hora de inicio de la Tarea [i] , entonces estas dos tareas no se pueden hacer juntas. Sin embargo, si no se superponen, verificaremos si Acc_Prof [j] + Profit [i]> Acc_Prof [i] . Si este es el caso, actualizaremos Acc_Prof [i] = Acc_Prof [j] + Profit [i] . Es decir:
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
Aquí, Acc_Prof [j] + Profit [i] representa el beneficio acumulado de hacer estos dos trabajos juntos. Vamos a comprobarlo para nuestro ejemplo:
Aquí el trabajo [j] se superpone con el trabajo [i] . Así que estos no se pueden hacer juntos. Como nuestra j es igual a i-1 , incrementamos el valor de i a i + 1 que es 3 . Y hacemos 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ahora Job [j] y Job [i] no se superponen. La cantidad total de ganancias que podemos obtener al elegir estos dos trabajos es: Acc_Prof [j] + Profit [i] = 5 + 5 = 10, que es mayor que Acc_Prof [i] . Así que actualizamos Acc_Prof [i] = 10 . También incrementamos j en 1. Obtenemos,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Aquí, la tarea [j] se superpone con la tarea [i] y j también es igual a i-1 . Entonces incrementamos i por 1, y hacemos j = 1 . Obtenemos,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ahora, Job [j] y Job [i] no se superponen, obtenemos el beneficio acumulado 5 + 4 = 9 , que es mayor que Acc_Prof [i] . Actualizamos Acc_Prof [i] = 9 e incrementamos j en 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
De nuevo, Job [j] y Job [i] no se superponen. El beneficio acumulado es: 6 + 4 = 10 , que es mayor que Acc_Prof [i] . Nuevamente actualizamos Acc_Prof [i] = 10 . Incrementamos j en 1. Obtenemos:
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Si continuamos este proceso, después de recorrer toda la tabla usando i , nuestra tabla finalmente se verá así:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Se han saltado algunos pasos para acortar el documento.
¡Si iteramos a través de la matriz Acc_Prof , podemos encontrar la ganancia máxima de 17 ! El pseudocódigo:
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
La complejidad de llenar la matriz Acc_Prof es O (n 2 ). El recorrido transversal de la matriz toma O (n) . Entonces, la complejidad total de este algoritmo es O (n 2 ).
Ahora, si queremos averiguar qué trabajos se realizaron para obtener el máximo beneficio, debemos atravesar la matriz en orden inverso y si Acc_Prof coincide con maxProfit , empujaremos el nombre del trabajo en una pila y restaremos Ganancia de ese trabajo de maxProfit . Haremos esto hasta que nuestro maxProfit> 0 o alcancemos el punto de inicio de la matriz Acc_Prof . El pseudocódigo se verá así:
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
La complejidad de este procedimiento es: O (n) .
Una cosa para recordar, si hay varios horarios de trabajo que pueden darnos el máximo beneficio, solo podemos encontrar un programa de trabajo a través de este procedimiento.