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.
