Capítulo 16. Algoritmos Greedy (Parte I)

Características de los Algoritmos Greedy

 

La técnica de diseño de algoritmos denominada Greedy (algoritmos voraces) es aquella que va construyendo la solución de un problema a partir de decisiones parciales tomadas en base a la información disponible en cada momento.

 

No mira hacia adelante, es decir, no ve los efectos de las decisiones tomadas a futuro y nunca reconsidera una decisión ya tomada.

 

Esta técnica es utilizada en general para resolver problemas de optimización. Suelen ser muy eficientes pero su eficacia debe ser validada, o sea, debe tenerse mucho cuidado con su correctitud. Esto quiere decir que se debe demostrar que la solución encontrada es óptima.

 

Se basa en un conjunto de candidatos a formar parte de la solución. En cada paso se toma uno de los candidatos, el más apropiado y se evalúa si sirve o no. Si sirve, el candidato es agregado a la solución, caso contrario es descartado. Para ello, es necesario saber en todo momento, dado un candidato, si el mismo está pendiente de ser evaluado, si ya fue evaluado y agregado a la solución o si fue descartado.

 

Para cumplir con esto deben conocerse cuatro funciones:

• La función selección que es la que selecciona el mejor candidato dentro de los pendientes.
• La función factibilidad que evalúa si un candidato seleccionado es factible de formar parte de la solución.
• La función solución que evalúa si un conjunto solución propuesto conforma la solución al problema.
• La función objetivo que es la que se debe maximizar o minimizar (optimizar).

 

En el próximo capítulo presentaremos el pseudocódigo de la forma general de los algoritmos Greedy. Tener en cuenta que, aunque las cuatro funciones mencionadas deben estar presentes en el diseño, no siempre es trivial la identificación de las mismas dentro del algoritmo.

Fuentes:

 

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 15. MergeSort dividiendo cadena en tres partes

Cuando aplicamos MergeSort en capítulos previos, siempre fuimos dividiendo la cadena de entrada en dos partes. ¿Qué pasaría si dividiéramos la cadena en tres o más partes? ¿Mejoraría la complejidad temporal? En este capítulo intentaremos dar respuesta a estas cuestiones.

Enunciado

Dada una cadena S de números enteros, ordenarla en forma creciente. Utilizar el método de ordenamiento Merge-Sort, pero dividiendo la cadena en 3 subcadenas y analizar el costo.

Pseudocódigo

Análisis de Complejidad Temporal

Considerando que el método UnirCadenasOrdenadas tiene un costo lineal O(n), podemos ver que la cantidad de llamadas recursivas es 3 al igual que la cantidad en que se divide la cadena. El resto de asignaciones y comparaciones tienen un costo constante.

Por lo tanto, tenemos que a = 3, b = 3 y k = 1

Siendo a = b^k ya que 3 = 3¹ el orden del algoritmo es O(n^k*log(n)) lo que finalmente se traduce en un costo de O(n*log(n))

 

Así acabamos de mostrar que el hecho de dividir la cadena en una mayor cantidad de partes no mejora la complejidad temporal de MergeSort. Podemos proceder análogamente en el caso que deseemos dividir la cadena de entrada en 4 o más partes y veremos que el resultado no se ve alterado.

Capítulo 14. Métodos de Ordenamiento: QuickSort (Parte II)

En el capítulo previo estudiamos el funcionamiento del método de ordenamiento QuickSort. Aquí presentaremos el pseudocódigo del algoritmo así como también realizaremos el análisis de complejidad temporal del mismo.

Pseudocódigo

QUICKSORT
Entrada: S -> secuencia de enteros.
Salida:  S -> la misma secuencia ordenada.

     si longitud(S) > 1
          p <- pivot(S)
          S1 <- crearVector(p - 1)
          S2 <- crearVector(longitud(S) - p)
          S1 <- S[1... p - 1]
          S2 <- S[p + 1... longitud(S)]
          S1 <- QuickSort(S1)
          S2 <- QuickSort(S2)
          S  <- S1 + S[p] + S2
     fin si
     devolver S
fin QUICKSORT

El pseudocódigo para el método pivot es el siguiente

PIVOT
Entrada: S -> secuencia de enteros.
Salida:  p -> posición del elemento utilizado para pivotear.

     p <- S[1]
     k <- 2
     t <- longitud(S)
     mientras S[k] <= p y k < longitud(S)
          k <- k + 1
     fin mientras
     mientras S[t] > p
          t <- t - 1
     fin mientras
     mientras k < t
          aux <- S[k]
          S[k] <- S[t]
          S[t] <- aux
          mientras S[k] <= p
               k <- k + 1
          fin mientras
          mientras S[t] > p
               t <- t - 1
          fin mientras
     fin mientras
     aux <- S[1]
     S[1] <- S[t]
     S[t] <- aux
     devolver t
fin PIVOT

Análisis de Complejidad Temporal

Analizando el método pivot en primera instancia podemos ver que su costo es de O(n) ya que los "mientras" anidados tienen como restricción el "mientras" principal. A su vez, el método QuickSort posee dos llamadas recursivas.

Dependiendo la ubicación del pivot (ya habíamos visto que cuanto más cerca del elemento mediano mayor eficiencia tendría el método), si el mismo cae cerca del centro de la cadena, el análisis de costos es el siguiente:

 

 

Se tiene que a = 2, b = 2 y k = 1 lo que finalmente da lugar a un costo O(n*log(n)) al igual que el método MergeSort.

Por el contrario, si el pivot cae cerca de alguno de los extremos (el peor caso), tenemos

 

 

 

Aquí a = 1, b = 1 y k = 1 (estamos en el Caso 1 de los métodos recursivos) dando una complejidad de O(n²).

En el peor de los casos, este algoritmo es menos eficiente que MergeSort. Cabe mencionar que en situaciones de la vida cotidiana, donde los datos tienen una distribución aleatoria (cualquiera de los ordenamientos es igualmente probable), se puede demostrar (está fuera de los alcances de este curso) que si bien el orden es igual para ambos algoritmos en el caso promedio, el tiempo de ejecución es menor para QuickSort.

 

 

 

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 13. Métodos de ordenamiento: QuickSort (Parte I)

QuickSort

Pondremos nuestra atención en el funcionamiento de un nuevo método de ordenamiento que también utiliza la técnica de DyC, el QuickSort.

La idea principal del mismo consiste en elegir un elemento al azar, denominado pivot y, a partir de ese elemento, dividir la cadena en dos partes:

• A la izquierda del pivot todos los elementos menores
• A la derecha del pivot todos los elementos mayores.

Al hacer esto, el pivot queda ubicado en su posición definitiva dentro de la cadena, es decir, queda ordenado. Luego se aplica en forma recursiva el método a las dos partes restantes.

Existen distintas técnicas para la elección del pivot. Cabe destacar que una buena selección del elemento pivot significará una solución más eficiente. Cuanto más cercano al elemento mediano se encuentre el pivot, más parejas serán las dos partes de la cadena y mejor la solución. Por el contrario, cuanto más cercano a alguno de los extremos se encuentre el pivot, las partes serán más desparejas y la solución menos eficiente.

Al igual que con MergeSort veremos un ejemplo ilustrado que nos ayude a comprender la forma en que trabaja el método. Supondremos a continuación que nuestro algoritmo siempre selecciona como pivot el primer elemento de la cadena.

Señalamos a continuación el elemento pivot en negrita en las sucesivas llamadas recursivas.

Se puede observar que, a medida que el pivot es elegido, va quedando en la posición que le corresponde en la cadena ordenada. Verificar por ejemplo que el primer pivot, el número "15", queda sexto cuando es elegido y en la última cadena (la ordenada) también ocupa esa posición.

 

En el próximo capítulo presentaremos el pseudocódigo para el método de QuickSort así como también el análisis de complejidad temporal.

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán. 

Capítulo 12. Métodos de ordenamiento: MergeSort (Parte II)

En el capítulo anterior nos enfocamos en entender cómo funciona el método de ordenamiento denominado MergeSort. En esta oportunidad presentaremos el pseudocódigo y realizaremos el análisis de complejidad temporal para mostrar que esta técnica mejora las estudiadas previamente.

 

Pseudocódigo

 

 

Para mayor claridad se utiliza el método "Merge" que se encarga de combinar las subcadenas

 

 

 

Análisis de Complejidad Temporal

 

Podemos observar que en el algoritmo MergeSort se realizan 2 llamadas recursivas y la entrada va reduciéndose a la mitad en cada instancia. Por lo tanto nos encuadramos en el Caso 2 con un valor de a = 2.

 

Las operaciones no afectadas por la recursividad tienen una complejidad lineal, es decir, orden O(n) dando un valor de 1 para k. Como dijimos, al reducir la entrada por la mitad, el valor de b es 2.

 

Resumiendo, tenemos que a = b^k (ya que 2 = 2¹)  y entonces el costo del algoritmo es O(n*log n).

 

Esto representa una mejora a los algoritmos de inserción y selección que tenían una complejidad cuadrática. En el próximo capítulo veremos el método de ordenamiento QuickSort, también basado en la técnica de DyC.

 

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.