la nada



Universidad de Guadalajara



[]
dinámica y búsqueda exhaustiva.


ALGORITMO DIVIDE Y VENCERAS
EJEMPLO;
funcion divide_y_venceras_1(problema)
{
descomponer el problema en nsubproblemas más pequeños;
para i=1 hasta n hacer
resolver el subproblema k;
combinar las n soluciones;

funcion divide_y_venceras(problema)
{
si el problema es trivialentonces resolver el problema;
si no es trivial
{
descomponer el problema en n subproblemas más pequeños;
para i=1 hasta n hacer
divide_y_venceras(subproblema_k);combinar las n soluciones;
}
}

Programación dinámica
En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización desubproblemas superpuestos y subestructuras óptimas, como se describe a continuación.
El matemático Richard Bellman inventó la programación dinámica en 1953 que se utiliza para optimizar problemascomplejos que pueden ser discretizados y secuencializados
Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en suconjunto. Por ejemplo, el camino más corto entre dos vértices de un grafo se puede encontrar calculando primero el camino más corto al objetivo desde todos los vértices adyacentes al de partida, y despuésusando estas soluciones para elegir el mejor camino de todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:
1. Dividir el problema ensubproblemas más pequeños.
2. Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
3. Usar estas soluciones óptimas para construir una solución óptima al problemaoriginal.
Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.
BUSQUEDA EXHAUSTIVA:
De lo que...