¿Resuelven la programación dinámica y los algoritmos codiciosos el mismo tipo de problemas?

Question

Me pregunto si la programación dinámica y los algoritmos codiciosos resuelven el mismo tipo de problemas, ya sea de forma precisa o aproximada. En concreto,

1. Hasta donde yo sé, el tipo de problemas que la programación dinámica puede resolver son los que tienen una "estructura óptima". ¿Puede el mismo tipo de problemas ser siempre resueltos por algoritmos codiciosos, ya sea de forma precisa o aproximada? (Creo que sí)
2. ¿Existen problemas óptimos que no tengan una "estructura óptima" y pueden ser resueltos por algoritmos codiciosos, ya sea de forma precisa o aproximadamente? En caso afirmativo, ¿qué caracteriza el tipo de problemas que pueden ser resueltos por algoritmos codiciosos, ya sea de forma precisa o aproximadamente?

Gracias y saludos.

Answer 1

("Aproximadamente" es difícil de definir, así que sólo voy a abordar el aspecto "con precisión" u "óptimo" de tus preguntas).

Hay una buena discusión sobre la diferencia entre los algoritmos codiciosos y la programación dinámica en _Introducción a los algoritmos_ de Cormen, Leiserson, Rivest y Stein (capítulo 16, páginas 381-383 de la segunda edición).

Con respecto a su primera pregunta, he aquí un resumen de lo que tienen que decir. Tanto la programación dinámica como los algoritmos codiciosos pueden utilizarse en problemas que presentan una "subestructura óptima" (que CLRS define diciendo que una solución óptima del problema contiene en su interior soluciones óptimas de subproblemas). Sin embargo, para que la solución codiciosa sea óptima, el problema debe presentar también lo que ellos llaman la "propiedad de elección codiciosa" Es decir, se puede llegar a una solución globalmente óptima tomando decisiones localmente óptimas (codiciosas). Por el contrario, la programación dinámica es buena para los problemas que presentan no sólo una subestructura óptima, sino también subproblemas superpuestos . (Esto significa que un subproblema concreto puede alcanzarse de múltiples maneras. El algoritmo de programación dinámica calcula el valor de cada subproblema una vez y luego puede reutilizarlos cada vez que el algoritmo los vuelva a visitar).

A continuación, dan el ejemplo de la mochila 0-1 frente al problema de la mochila fraccionaria aquí . Ambas exhiben la propiedad de subestructura óptima, pero sólo la segunda exhibe además la propiedad de elección codiciosa. Por tanto, el segundo puede resolverse de forma óptima con un algoritmo codicioso (o un algoritmo de programación dinámica, aunque el codicioso sería más rápido), pero el primero requiere programación dinámica o algún otro enfoque no codicioso. Véase también el ejemplo de Henry en la otra respuesta.

También puede ser útil leer lo siguiente, que es el núcleo de su discusión sobre la diferencia y que cito en su totalidad (el énfasis es mío):

En la programación dinámica, hacemos una elección en cada paso, pero la elección puede depender de las soluciones a los subproblemas . En un algoritmo codicioso, hacemos la elección que nos parezca mejor en ese momento y luego resolvemos los subproblemas que surgen después de la elección. La elección realizada por un algoritmo codicioso puede depender de las elecciones realizadas hasta el momento, pero no puede depender de ninguna elección futura ni de las soluciones de los subproblemas . Por lo tanto, a diferencia de la programación dinámica, que resuelve los subproblemas de abajo hacia arriba, una estrategia codiciosa suele progresar de arriba hacia abajo, haciendo una elección codiciosa tras otra, reduciendo iterativamente cada instancia del problema a una más pequeña.

Básicamente, pues, la programación dinámica resuelve primero los subproblemas y luego utiliza las soluciones de los subproblemas para construir las soluciones de los problemas más grandes. Los algoritmos codiciosos se encargan primero de todo el problema mayor y cada elección codiciosa reduce el problema mayor a un subproblema más pequeño. Por lo tanto, los dos tipos de algoritmos son una especie de inversión del otro.

---

Con respecto a su segunda pregunta, he aquí otra cita de CLRS (p. 380):

¿Cómo se puede saber si un algoritmo codicioso resolverá un determinado problema de optimización? No hay manera en general...

Answer 2

Diagramas de Dynkin afines (con la combinación lineal de raíces simples que tiene norma 0)

Answer 3

Para responder a su primera pregunta, hay problemas que pueden ser resueltos por la programación dinámica pero no satisfactoriamente por un algoritmo codicioso.

Por ejemplo, un Ejemplo de Wikipedia para encontrar el camino más corto.

donde las líneas onduladas se han calculado antes mediante programación dinámica. El camino global más corto es claramente la ruta superior, pero un algoritmo codicioso tomaría la ruta del medio ya que $2 < 5$ . Los valores pueden alterarse para que la solución codiciosa no se acerque ni de lejos al resultado de la programación dinámica.

Answer 4

Reformulando un poco, la ley de adición relativista dice que si $v_1$ y $v_2$ suma a $v$ que escribiremos como $v_1 \oplus v_2 = v$ entonces sus "ángulos de impulso" (o rapideces) se suman directamente. Es decir, $$\tanh \phi_i = v_i, \quad \tanh \phi = v, \quad \phi_1 + \phi_2 = \phi.$$ Su observación es que $1/v_1 \oplus v_2 = 1/v$ también, lo que equivale a demostrar que $$\text{arctanh}(a) - \text{arctanh}(1/a) = \text{constant}$$ para todos $a \in (-1, 1)$ . Y esto resulta ser cierto, así que tal vez tu resultado se reduce a una propiedad casual de arctanh.

He tratado de encontrar una explicación física. Teniendo $|v| > 1$ corresponde a tener un "ángulo de impulso" complejo $\phi$ . No sé qué significa eso, y es extra confuso porque los ángulos de impulso ya son generalizaciones "imaginarias" de los ángulos de rotación ordinarios (es decir, son lo que obtienes si rotas por un ángulo imaginario). Así que tal vez $|v| > 1$ lo envuelve de nuevo para que sea una rotación normal, pero no lo veo.