¿Por qué es este un algoritmo codicioso?

Question

tengo esta pregunta en mi libro de texto:.

"Supongamos que tenemos un conjunto de actividades para programar entre un gran número de salas de conferencias, donde se llevarán a cabo cualquier actividad en cualquier sala de conferencias Deseamos programar . todas las actividades utilizando el menor número de salas de conferencia como sea posible Dar un algoritmo codicioso eficiente para determinar qué actividad debe utilizar lo que la sala de conferencias "

y se le da la respuesta aquí:. http://mitpress.mit.edu/algorithms/solutions/chap16-solutions.pdf

(la solución abetos)

Y mi respuesta es, ¿por qué el algoritmo es un algoritmo codicioso?

Creo que es porque toma la decisión (codiciosa) de tomar siempre una actividad y ponerla en una sala de conferencias, donde ya hay una o más actividades (si es posible), en lugar de poner la actividad en una nueva sala de conferencias vacía. Pero no estoy seguro. :)

Answer 1

Codicioso significa que no reconsideras tus elecciones. eso hace que sea muy difícil encontrar una solución óptima y describe el algoritmo allí.

Answer 2

Es porque usted hace más con la sala de conferencias 1 incluso antes de considerar el resto del problema. En este sentido, la sala de conferencias 1 es "codiciosa".

Answer 3

La definición de un algoritmo codicioso es que toma la aparente mejor opción en cada paso, en lugar de considerar varios pasos adelante. Por lo tanto, se encuentra un mínimo local del espacio de búsqueda (pendiente descendente tal vez vale la pena un poco de google). Un programa de ajedrez es un buen ejemplo de esto, un algoritmo codicioso siempre haría el movimiento directo más poderoso (tomar una pieza, maximizar el desarrollo de la pieza) pero no consideraría varios movimientos en el futuro.

Lamentablemente, parece que no puedo abrir el enlace que ha incluido en este momento. Pero puedo dudar una buena conjetura de que el algoritmo es codicioso porque una vez que ha encajado un evento en una sala, no reconsiderará esa decisión (retroceder en Google probablemente valga la pena en este momento).

Answer 4

No sé si existe una única definición oficial de "codicioso", pero para mí una solución codiciosa es aquella que reduce un problema a la selección de una serie de soluciones locales óptimas con la esperanza de que cuando Juntos, están cerca de la solución óptima general. (A veces esta esperanza es más que esperanza).