Fuerza bruta:
- Da una solución a un problema utilizando el método más directo. Sin embargo, por lo general no es una solución muy óptima o que sea flexible para cambios futuros, pero hace el trabajo.
- El proverbial ejemplo de programación de fuerza bruta es probar todas las soluciones óptimas para llegar a la respuesta final.
- La programación de fuerza bruta prueba cada combinación de enrutamiento posible; mientras que otros algoritmos matemáticos obtienen los resultados más rápidamente cuando el número de casos de prueba es grande.
- Las técnicas de fuerza bruta generalmente no se utilizan en el campo industrial porque no son óptimas en términos de espacio y tiempo y ralentizan el producto o software en general.
Programación dinámica:
- El enfoque de programación dinámica es similar a divide y vencerás al dividir el problema en subproblemas posibles cada vez más pequeños. En palabras simples, la programación dinámica es una optimización sobre la recursividad simple.
- Pero a diferencia de divide y vencerás, estos subproblemas no se resuelven de forma independiente.
- Más bien, los resultados de estos subproblemas más pequeños se recuerdan y se utilizan para la similitud o la superposición.
Diferentes formas de utilizar la Programación Dinámica:
- Top-Down: Comience a resolver el problema dado dividiéndolo. Si vemos que el problema ya se resolvió, simplemente devuelva la respuesta guardada. Si no se ha resuelto, resuélvelo y guarda la respuesta. Este enfoque también se conoce como Memoización.
- Bottom-Up: Analice el problema y vea el orden en que se resuelven los subproblemas y comience a resolver desde el subproblema trivial, hasta el problema dado. En este proceso se garantiza que los subproblemas se resuelven antes de resolver el problema. Este enfoque también se conoce como tabulación.
Diferencia entre fuerza bruta y programación dinámica: la diferencia entre estos dos enfoques se menciona claramente en la siguiente tabla.
| Parámetros de comparación | Fuerza bruta | Programación dinámica |
|---|---|---|
| Metodología | Encuentra todos los posibles resultados de un problema dado. | También encuentra todos los resultados posibles, pero evita volver a calcular almacenando las soluciones de los subproblemas. |
| Complejidad del tiempo | Podría ser cualquier cosa, a veces incluso en términos exponenciales. | Nos ayuda a optimizar el enfoque de fuerza bruta, a veces los términos exponenciales se mejoran a términos polinómicos (por ejemplo, programa factorial). |
| iteraciones | El número de iteraciones es más | El número de iteraciones es menor (en términos de n) |
| Eficiencia | es menos eficiente | es mas eficiente |
| Almacenamiento | Por lo general, no requiere espacio adicional para almacenar los resultados de los subproblemas. | Requiere espacio adicional para almacenar las soluciones a los subproblemas, que podría utilizarse más cuando sea necesario. |