Get best of the week

El libro "Algoritmo perfecto. Algoritmos codiciosos y programación dinámica »

imagenHola habrozhiteli! En el nuevo libro, Tim Rafgarden habla sobre algoritmos codiciosos (el problema de planificación, árboles de expansión mínima, agrupación, códigos Huffman) y programación dinámica (el problema de la mochila, la alineación de secuencias, los caminos más cortos, los árboles de búsqueda óptimos). Esta publicación presenta un extracto "Desarrollando un algoritmo codicioso". Los algoritmos

codiciosos parecen ser muy adecuados para la tarea de programar el trabajo, minimizando la suma ponderada de los tiempos de finalización. El resultado tiene una estructura iterativa, donde el trabajo se procesa uno a la vez. ¿Por qué no usar un algoritmo codicioso que decide iterativamente qué trabajo será el próximo?

El primer paso de nuestro plan es resolver dos casos especiales del problema general. Nuestras soluciones a estos casos mostrarán cómo se vería un algoritmo codicioso en el caso general. Luego reducimos el dominio a un algoritmo candidato y demostramos que es este candidato el que resuelve el problema correctamente. El proceso por el cual llegamos a este algoritmo es más importante para recordar que el algoritmo mismo; Este proceso es repetible y puede usarlo en sus propias aplicaciones.

13.3.1. Dos casos especiales


Supongamos que para la tarea de minimizar la suma ponderada de las fechas de finalización, de hecho, hay un algoritmo codicioso correcto. ¿Cómo se vería si asumimos que todas las obras tienen la misma longitud (pero posiblemente pesos diferentes) o, por el contrario, tienen el mismo peso (pero posiblemente longitudes diferentes)?
13.2

(1) , ?
(2) , ?
) ;
) ;
) ;
) ;
( . 13.3.3.)

13.3.2.


En general, el trabajo puede tener diferentes pesos y diferentes longitudes. Siempre que nuestras dos reglas generales, preferir un trabajo más corto y trabajar con pesos más altos, tengan la suerte de que coincidan un par de trabajos, sabemos cuál planear primero (más corto con pesos más altos). Pero, ¿qué pasa si estas dos reglas dan consejos contradictorios? ¿Qué debemos hacer con un trabajo corto con bajo peso y un trabajo largo con alto peso?

¿Cuál será el algoritmo codicioso más simple que funcionará como debería? Cada trabajo tiene dos parámetros, y el algoritmo debe considerar ambos. La mejor opción sería desarrollar una fórmula que compilara la longitud y el peso de cada trabajo en una sola marca (contribución), de modo que la planificación del trabajo de la marca más alta a la más baja garantice minimizar la cantidad de fechas de finalización ponderadas. Si existe tal fórmula, entonces de nuestros dos casos particulares se deduce que debería tener dos propiedades: (i) dejando fija la longitud, debería aumentar según el peso del trabajo; (ii) dejando el peso fijo, debería disminuir a partir de la duración del trabajo (recuerde que cuanto mayor sea la marca, mejor). Dedique un minuto a una lluvia de ideas sobre varias fórmulas que tengan ambas propiedades.

imagen

Quizás la función más simple, que aumenta de peso y disminuye de longitud, es la diferencia entre ellos:
propuesta No. 1 para la marca del trabajo. imagen

La marca indicada podría ser negativa, pero esto no plantea ningún obstáculo para organizar secuencialmente el trabajo de la marca más alta a la más baja. . Sin embargo, hay muchas otras opciones. Por ejemplo, la relación de dos parámetros es otro candidato: la

Propuesta No. 2 para marcar el trabajo. imagen

Estas dos funciones para calcular la marca conducen a dos algoritmos codiciosos diferentes.
GREEDYDIFF DIFERENCIA DE GREED

Planifique el trabajo en orden descendente imagen
(rompiendo arbitrariamente la coincidencia de valores).
GREEDYRATIO

imagen
( ).

Por lo tanto, nuestro primer estudio de caso ilustra el primer tema del paradigma codicioso (sección 13.1.2): proponer para la tarea varios algoritmos codiciosos competidores generalmente no es difícil. Pero, ¿cuál de los dos algoritmos, si alguno, es correcto? Una forma rápida de excluir uno de ellos es encontrar una instancia en la que dos algoritmos muestren diferentes horarios con diferentes valores de la función objetivo. Para cualquier algoritmo cuyos resultados sean peores en este ejemplo, podemos concluir que no siempre es óptimo. En dos casos especiales con trabajos del mismo peso o la misma longitud, ambos algoritmos actúan correctamente. El ejemplo más simple posible de la exclusión de uno de ellos puede ser una instancia de una tarea en la que dos obras tienen pesos y longitudes diferentes,Como resultado, ambos algoritmos planean trabajar en órdenes opuestos. Es decir, estamos buscando dos obras, cuyo orden de diferencia es el opuesto de su orden en relación. Ejemplo:

imagen

El primer trabajo tiene una relación grande más grande imagenpero una diferencia más grande (–2 vs. –1). Por lo tanto, el algoritmo GreedyDiffplanifica el segundo trabajo primero, mientras que el algoritmo GreedyRatioplanifica lo contrario.
EJERCICIO 13.3

¿Cuál es la suma de las fechas de finalización ponderadas en los cronogramas deducidos por los algoritmos GreedyDiffy , respectivamente GreedyRatio?

a) 22 y 23
b) 23 y 22
c) 17 y 17
d) 17 y 11
(Para una solución y explicación, ver sección 13.3.3.)

Avanzamos excluyendo el algoritmo GreedyDiffde mayor consideración. Sin embargo, el resultado del ejercicio 13.3 no conduce directamente al hecho de que el algoritmo GreedyRatiosiempre será óptimo. Hasta donde sabemos, hay otros casos en los que este algoritmo produce una programación no óptima. Siempre debe ser escéptico de un algoritmo que no esté acompañado de una prueba de su corrección, incluso si este algoritmo hace lo correcto en varios casos de prueba y es extremadamente escéptico de los algoritmos codiciosos.

En nuestro caso, el algoritmo GreedyRatio, de hecho, está garantizado para minimizar la cantidad de fechas de finalización ponderadas.

Teorema 13.1 (la corrección del algoritmo GreedyRatio) . Para cada conjunto de pesos de trabajo positivosimageny la duración positiva del trabajo, el imagenalgoritmo GreedyRatiomuestra un cronograma con la menor suma posible de fechas de finalización ponderadas.

Esta declaración lógica no es obvia, y no debes confiar en él sin recibir evidencia. De acuerdo con el tercer tema del paradigma codicioso (sección 13.1.2), esta prueba abarca toda la siguiente sección.
, . .

. — , ( ). — , , , . «» ( ) , .

El tema restante del paradigma codicioso es la simplicidad del análisis de tiempo de ejecución (sección 13.1.2). Aquí, por supuesto, lo es. El algoritmo GreedyRatio solo clasifica los trabajos por relación, lo que toma tiempo O (n log n), donde n es el número de trabajos en la entrada (ver nota 1 en la página 24).

13.3.3. Soluciones de ejercicio 13.2–13.3


La solución para el ejercicio 13.2 La

respuesta correcta: (a) . Primero, suponga que todos los n trabajos tienen la misma duración, digamos 1. Luego, cada cronograma tiene exactamente el mismo conjunto de plazos - {1, 2, 3, ..., n} - y la única pregunta es qué tipo de trabajo obtiene fecha de finalización y cuál es la fecha límite. Nuestra semántica para los pesos de trabajo ciertamente implica que el trabajo con mayor peso debe recibir tiempos de finalización más cortos, y esto es cierto. Por ejemplo, no querría planificar un trabajo con un peso de 10 tercios (con una fecha límite de 3) y trabajar con un peso de 20 quintos (con un plazo de 5); sería mejor cambiar las posiciones de estos dos trabajos, lo que reduciría la suma de los plazos ponderados en 20 (como puede ver por usted mismo).

El segundo caso, en el que todas las obras tienen el mismo peso, es ligeramente más delgado. Aquí desea dar preferencia al trabajo más corto. Por ejemplo, considere dos trabajos de unidad de peso con longitudes de 1 y 2. Si primero planea un trabajo más corto, los plazos de finalización serán 1 y 3 con un total de 4. En el orden inverso, los plazos serán 2 y 3 con el peor resultado 5. En general, el planificado el trabajo primero contribuye al tiempo de finalización de todo el trabajo, ya que todo el trabajo debe esperar a la finalización del primero. En igualdad de condiciones, la planificación del trabajo más corto primero minimiza este impacto negativo. El segundo trabajo contribuye a todas las fechas de finalización, excepto el primer trabajo, por lo que el segundo trabajo más corto debe programarse para el siguiente, etc.

Ejercicio 13.3 Solución

La respuesta correcta es b). El algoritmo GreedyDiffplanea un segundo trabajo primero. La fecha límite para completar este trabajo es imagenmientras que la fecha límite para completar otro trabajo es la imagensuma de las fechas límite ponderadas para completar entonces

imagen

El algoritmo GreedyRatioplanifica primero el primer trabajo, lo que da como resultado plazos imagen
y la suma de los plazos ponderados igual a

imagen

Dado que el algoritmo GreedyDiffno puede calcular el programa óptimo para este ejemplo , no siempre es correcto.

»Se puede encontrar más información sobre el libro en el sitio web del editor
» Contenido
» Extracto de

Khabrozhiteley 25% de descuento en el cupón - Algoritmos

Al pagar la versión en papel del libro, se envía un libro electrónico por correo electrónico.

More articles:


All Articles