quiz#4

QUIZ #4:

Un grafo conexo de n nodos, tiene como minimo n-1 arcos. Si tiene mas, es porque tiene cilclos

Un conjunto factible es prometedor si puede producir una solución optima

Kruskal: log n

Prim: a log n

Djisktra: n^2

Knapsack: log n

minimizar tiempo: n log n

schedule: n log n

GREEDY ALGORITHMS:

-3 conjuntos: candidatos, aceptados, rechazados.
-4 funciones: una verifica que un conjunto sea solucion, otra que un conjunto sea factible, otra de los candidatos cual es el mas prometedor, y otra que nos indica la solucion(esta puede no ser explicita).
-Se selecciona el mejor, sin preocuparse por el futuro, nunca se arrepiente, si alguien está está, si se rechazó ni modo