Page 82 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 82
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Algoritmo 3.2. Método greedy para el problema de la mochila
Mientras que las dos primeras estrategias no garantizan la solución óptima para el problema de la
mochila, el siguiente teorema muestra que la tercera estrategia siempre obtiene una solución óptima.
Teorema: Si P /W ≥ P /W ≥ P /W ≥... ≥ P /W , entonces el algoritmo de la mochila genera un óp-
1 1 2 2 3 3 n n
timo a la instancia dada por el problema.
árBol de expaNSIóN MíNIMa (MINIMuN SpaNNINg tree)
Definición: Sea G (V, E) (donde V es el conjunto de vértices y E el conjunto de aristas, arcos o seg-
mentos que unen a los nodos), por lo que una gráfica es la forma en que se unen los vértices me-
diante las aristas. En la figura 3.1 se muestran ejemplos de gráficas no direccionadas. Un árbol es
una gráfica que no tiene ciclos. Una subgráfica T (V, E‘) es un árbol de extensión de G si y solo si T
es un árbol. Por ende, las figuras 3.1b y 3.1c son árboles.
76
