Estrategias_Diseno_Algoritmos_Escrito

SHAREL:
Divide y Vencerás
Programación dinámica
Algoritmos Ávidos

KENNETH:
BackTracking
Branch and Bound


2.1 BackTracking

 El objetivo del recorrido es encontrar soluciones para algúnproblema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que puede encontrar una solución completa. Elrecorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede, o bien detenerse (si lo único que se necesita es una solución del problema) obien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puedecompletar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve aun nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución. 
2.1.1 Ventajas

Si existen una o las soluciones el backtracking las calcula.
Es relativamente sencillo deimplementar en los problemas a resolver.
Se adapta a características en específico del problema.

2.1.2 Desventajas

Si la solución es infinita, y si esta existe, no se encontrará nunca.
Consume muchamemoria para tener que almacenar ciclos de búsqueda.



2.1.3 Eficiencia del algoritmo
De los 4 factores que determinan el tiempo de ejecución de un algoritmo backtracking, sólo el cuarto varía de uncaso a otro: el número de nodos generados. En el mejor caso, backtracking podría generar sólo O(n) nodos, aunque podría llegar a tener que explorar el árbol completo del espacio de estados del problema.En el peor caso, si el número de nodos es O(2n) o O(n), el tiempo de ejecución del algoritmo backtracking será generalmente de orden O(p(n)2n) u O(q(n)n) respectivamente, con p y q polinomios en n....