¿En qué se diferencia la programación dinámica de la fuerza bruta?

19

Estaba leyendo sobre programación dinámica cuando me encontré con la siguiente cita

Un algoritmo de programación dinámica examinará todas las formas posibles de resolver el problema y elegirá la mejor solución. Por lo tanto, podemos pensar aproximadamente en la programación dinámica como un método inteligente de fuerza bruta que nos permite analizar todas las soluciones posibles para elegir la mejor . Si el alcance del problema es tal que analizar todas las soluciones posibles es posible y lo suficientemente rápido, la programación dinámica garantiza encontrar la solución óptima

El siguiente ejemplo fue dado

Por ejemplo, supongamos que tiene que ir del punto A al punto B lo más rápido posible, en una ciudad determinada, durante la hora pico. Un algoritmo de programación dinámico analizará todo el informe de tráfico, analizará todas las combinaciones posibles de caminos que pueda tomar, y solo entonces le indicará cuál es el camino más rápido. Por supuesto, es posible que tenga que esperar un tiempo hasta que termine el algoritmo, y solo entonces puede comenzar a conducir. El camino que tomará será el más rápido (suponiendo que nada haya cambiado en el entorno externo)

Brute Force está probando todas las soluciones posibles antes de decidir la mejor solución.

En qué se diferencia la programación dinámica de Brute Force si también pasa por todas las soluciones posibles antes de elegir la mejor , la única diferencia que veo es que la programación dinámica tiene en cuenta los factores adicionales (condiciones de tráfico en este caso).

¿Estoy en lo cierto al decir que la programación dinámica es un subconjunto del método de fuerza bruta?

Computernerd
fuente
1
Las condiciones del tráfico son un arenque rojo. Podrías considerarlos en cualquier algoritmo.
Yuval Filmus
Su primera cita no define la programación dinámica.
reinierpost
@reinierpost Bueno, trata de llegar allí intelligent, brute force, pero luego se olvida de describir la parte "inteligente"
Izkata
@Izkata Según ese razonamiento, cada algoritmo es "fuerza bruta inteligente" (que de todos modos es un oxímoron).
Raphael

Respuestas:

17

Un algoritmo de programación dinámica examinará todas las formas posibles de resolver el problema y elegirá la mejor solución.

Esta afirmación es simplemente errónea.

Recurrencias de programación dinámica no (a menudo) consideran todas las formas posibles de dividir el problema ejemplo dado en casos más pequeños de acuerdo con algún esquema. Sin embargo, no combinará todas las soluciones a todos los problemas parciales entre sí y elegirá la mejor; solo combina soluciones parciales óptimas (y elige la mejor de ellas).

El hecho de que esto produzca una solución óptima para el problema original no es trivial y, de hecho, solo es válido para algunos problemas. Es decir, aquellos que cumplen con el principio de optimización de Bellman (una de las "definiciones" más sospechosas y mal entendidas que se citan regularmente). Vea aquí para algunos pensamientos más sobre eso.

Como ejemplo concreto, considere el algoritmo de Bellman-Ford en un gráfico completo con pesos unitarios: solo considera caminos de longitud uno y dos (es decir, Θ ( n 2 ) muchos) porque aquellos que usan un borde son todos óptimos . ¡Pero hay infinitas soluciones si no limita el número máximo de bordes permitidos, y aún así ( n - 1 ) ! muchos si permite que cada nodo se use solo una vez. Claramente, Bellman-Ford, un algoritmo de programación dinámico, no realiza una búsqueda de fuerza bruta.KnorteΘ(norte2)(norte-1)!

Rafael
fuente
"Esta afirmación es simplemente incorrecta" - Solucionarlo .
nmclean
44
@nmclean Mi experiencia con la edición de artículos relacionados con algoritmos en Wikipedia ha sido menos que agradable, así que no. Prefiero invertir mi tiempo aquí.
Raphael
Probé suerte y edité el artículo. Espero que ahora esté un poco menos mal.
C4stor
9

La programación dinámica es inteligente ya que reutiliza la computación, mientras que la fuerza bruta no. Suponga que para resolver, f (6), necesita resolver 2 subproblemas que ambos llaman f (3). El método de fuerza bruta calculará f (3) dos veces, lo que desperdiciará el esfuerzo, mientras que la programación dinámica lo llamará una vez, guardará el resultado en caso de que los cálculos futuros necesiten usarlo. En muchos problemas, la dinámica mejora la complejidad exponencial de la fuerza bruta a la complejidad polinómica.

Tushar
fuente
9
Esa es la memorización , que es solo uno de los muchos trucos que emplea DP.
Ben Voigt
44
La fuerza bruta con la memorización sigue siendo ineficiente; solo la estructura / poda adicional proporcionada por las recurrencias DP hace que la memorización valga la pena.
Raphael
3
No sé nada sobre programación dinámica, pero estoy bastante seguro de que hay más que solo agregar cachés a un algoritmo de fuerza bruta. Creo que la programación dinámica evita probar todas las combinaciones posibles subdividiendo el espacio del problema, encontrando una solución óptima para cada subdivisión pequeña y luego combinándolas para crear una mejor solución general. (Puede hacer esto de forma recursiva, sumergiendo las subdivisiones). Esto solo funciona si puede expresar el problema de una manera que permita la combinación de soluciones como esta y aún así obtener un óptimo general.
Jonathan Hartley
1
Esta respuesta es realmente bastante precisa. Recomiendo leer un libro de texto como Cormen et al: "Introducción a los algoritmos" para obtener más información sobre la programación dinámica, este libro tiene un capítulo bastante decente. En pocas palabras, la programación dinámica eficiente utiliza dos propiedades del problema (de optimización) que desea resolver: las soluciones óptimas se pueden construir a partir de las soluciones óptimas de subproblemas más pequeños, y el número total de subproblemas más pequeños es en realidad bastante pequeño. Luego, puede construir todas las soluciones de subproblemas de abajo hacia arriba, acelerando el cálculo a costa de la memoria.
MRA
O, para decirlo en términos aún más simples: si sabe cómo calcular un coeficiente binomial utilizando el triángulo de Pascal, entonces sabe todo lo que necesita saber sobre programación dinámica.
MRA
3

La distinción que el artículo de Wikipedia podría estar tratando de hacer es entre tres tipos de algoritmos:

  1. Algoritmos que repasan todas las soluciones posibles, eligiendo la óptima.

  2. Algoritmos que abarcan un subconjunto de todas las soluciones posibles, elegidas para que la solución óptima pertenezca al subconjunto.

  3. Algoritmos que abarcan un subconjunto de todas las soluciones posibles, sin la garantía de que la solución óptima pertenece al subconjunto.

Los primeros dos tipos de algoritmos producen la solución óptima, mientras que el tercer tipo apunta a producir una solución "buena" en lugar de una solución óptima. En mi opinión, la distinción entre los dos primeros tipos no es tan clara.

Permítanme comenzar dando ejemplos simples para los tres tipos de algoritmos, en el contexto de la ruta más corta (el ejemplo que da).

  1. Prueba todos los caminos posibles. Esto se conoce como fuerza bruta .

  2. Pruebe todos los caminos posibles, haciendo un seguimiento de la solución mínima hasta ahora. Siempre que la ruta actual que está construyendo sea más costosa que la solución mínima hasta el momento, abandónela y elija otra (imaginamos que la distancia se calcula segmento por segmento). Esto se llama poda .

  3. Mire el mapa, considere algunos caminos y elija el mejor entre ellos. Este es un algoritmo para un humano en lugar de una computadora.

Estos ejemplos son bastante toscos, y quizás no pintan una imagen muy precisa. La poda es crucial en muchas situaciones, por ejemplo, en el ajedrez informático. Si tiene curiosidad, busque el algoritmo A * , que en realidad se utiliza para la ruta más corta.

La programación dinámica es una técnica para acelerar significativamente el algoritmo de fuerza bruta. Sin embargo, es algo engañoso pensarlo de esta manera. Es una técnica algorítmica para resolver problemas de optimización. Puede implementar la poda en el contexto de la programación dinámica.

ttt+1t

Yuval Filmus
fuente
Y luego está eliminando a un candidato de la consideración sin procesarlo por completo. Por ejemplo, al encontrar el conjunto de números no negativos con la suma mínima, en realidad no tiene que sumar cada conjunto por completo, solo vaya hasta que la suma exceda el mejor actual. Esta es una idea similar a la poda pero ortogonal. La combinación de las dos ideas produce "ramificación y unión", donde se resuelve un problema de complejidad reducida y se utiliza para justificar la poda.
Ben Voigt
0

La programación dinámica es mucho más rápida que la fuerza bruta. La fuerza bruta puede llevar un tiempo exponencial, mientras que la programación dinámica suele ser mucho más rápida.

La analogía con la fuerza bruta es muy laxa. La programación dinámica no es una bala mágica de plata que le permite tomar el algoritmo de fuerza bruta que desee y hacerlo eficiente.

DW
fuente
55
Esa es una consecuencia, no una explicación.
Raphael
-2

Esto es sencillo. La programación dinámica es una "estrategia de búsqueda" que utiliza factores adicionales para limitar una búsqueda. Si no hay solución en el espacio de búsqueda, la programación dinámica hará (típicamente) una búsqueda a través de cada elemento del espacio de búsqueda. Pero eso no significa que sea una búsqueda de fuerza bruta.

no hombre
fuente
"Si no hay una solución en el espacio de búsqueda, la programación dinámica (típicamente) realizará una búsqueda a través de cada elemento del espacio de búsqueda". - mal, mira mi respuesta.
Raphael
-2

La afirmación de que la programación dinámica es la fuerza bruta inteligente es correcta, pero un poco difícil de entender con esa fraseología. El objetivo de la programación dinámica generalmente es tomar un problema y dividirlo en partes más pequeñas de una manera inteligente. Una vez que haya hecho eso, usará la fuerza bruta para resolver cada pieza pequeña, y luego usará la fuerza bruta nuevamente para combinar las piezas en una solución final. Entonces, aunque definitivamente podría decir que la programación dinámica es un tipo de solución de fuerza bruta, el truco radica en cómo usa esa fuerza bruta.

Tal
fuente
1
"usarás la fuerza bruta para resolver cada pieza pequeña" - mal. Por lo general, utilizará el mismo enfoque de forma recursiva.
FrankW