Greedy Algorithms

Características generales:

-Set de candidatos: a tomar en cuenta.
-Set de candidatos considerados: fueron elegidos para la solución.
-Set de candidatos rechazados: fueron rechazados y ya no serán tomados en cuenta.

+Función solución: verifica que los candidatos den una solución al problema. 
+Función factibilidad: verifica si los candidatos son factibles para obtener una solución.
+Función de selección: selecciona de los candidatos aún no seleccionados, cuál es el más prometedor.
+Función objetiva: nos da la solución que hemos encontrado. Esta puede no estar explícitamente en el código.

 

MSTs:

Grafo conexo, pesado y no dirigido.
Debe tener n-1 arcos, n es la cantidad de nodos totales. Esto para que no hayan ciclos.

 

Kruskal:

Algoritmo para MST, que comienza vacío, y va agregando T resultado.

Agrega de forma creciente según el peso, y no le importa los nodos, solo no formar ciclos.

-> 8(a log n). n nodos y a arcos.

 

Prim:

Se inicia de una raíz arbitraria, cada paso agrega un nuevo nodo, hasta que todos los nodos se hayan incluído.

-> 8(n^2)

Es mejor usar Prim que Kruskal cuando a>n^2/log n, a es cantidad de arcos

 

Camino más corto(Dijkstra):

Se selecciona un nodo, y se quiere saber el camino más corto para llegar a todos los otros nodos.

C es nodos candidatos, D es solución (largos).

-> Normal: 8(n^2)

 

Problema de la mochila:

Se busca llenar una mochila con un peso máximo, con objetos con un peso y un valor, se busca el mayo valor respetando ese peso. Se pueden dividir objetos.

->O(n log n)

 

Planificación:

Minimizar tiempo en el sistema:

Un solo servicio, como un mae en un banco, procesador, etc. Tiene n clientes que atender, se sabe cuanto va a durar cada cliente. Se quiere minimizar el tiempo promedio de espera.

El caso óptimo es atender primero a los de menor tiempo primero.  Sólo es necesario ordenar esos tiempos. Los nuevos que lleguen se acomodan al final y se vuelve a poner en orden creciente.

-> solo es ordenar, O(n log n)

 

Planificación con tiempos de entrega:

Tenemos trabajos con valor y tiempo. Se elije una secuencia que se pueda hacer en el tiempo indicado y nos de mayor ganancia.