Algoritmos
Algoritmos greedy
Análisis y Diseño de Algoritmos
Análisis y Diseño de Algoritmos
greedy sobre grafos
sobre grafos
Algoritmos
Algoritmos greedy
greedy sobre grafos
sobre grafos
Árboles generadores
Algoritmo de Kruskal
Kruskal
Algoritmo de PrimPrim
Árboles generadores minimales
minimales
Algoritmo de
Algoritmo de
Caminos mínimos
Caminos mínimos
Algoritmo de
Algoritmo de
Heurísticas greedy
greedy
El problema del coloreo de un grafo
El problema del coloreo de un grafo
El problema del viajante de comercio
El problema del viajante de comercio
Algoritmo de Dijkstra
Algoritmo de Dijkstra
Dijkstra
Dijkstra
Heurísticas
11
Árboles generadores minimales
Árboles generadores
minimales
Problema
Problema
Dado un grafo conexo G = (V, A) no dirigido y
Dado un grafo conexo G = (V, A) no dirigido y
ponderado con pesos positivos, calcular un subgrafo
ponderado con pesos positivos, calcular un
subgrafo
conexo T
conexo T ⊆⊆ GG que conecte todos los vértices del grafo
que conecte todos los vértices del grafo
G y que
G y que la suma de
G y que
G y que la suma de
seleccionadas sea mínima.
seleccionadas sea mínima.
la suma de los pesos de las
la suma de los pesos de las
los pesos de las aristas
los pesos de las aristas
aristas
aristas
subgrafo es necesariamente un árbol: árbol
es necesariamente un árbol: árbol
Solución
Solución
Este
Este subgrafo
generador
generador minimal
(en inglés, “
(en inglés, “minimum
minimal o árbol de recubrimiento mínimo
o árbol de recubrimiento mínimo
minimum spanning
spanning treetree” [MST]).
” [MST]).
Árboles generadores minimales
Árboles generadores
minimales
4
6
16
8
5
10
24
23
21
18
11
14
9
7
G = (V, A)
4
6
5
8
11
9
7
T ⊂ G
Σa∈T ca = 50
22
33
Árboles generadores minimales
Árboles generadores
minimales
p.ej.
p.ej.
Aplicaciones
Aplicaciones
Diseño de redes: redes telefónicas, eléctricas,
Diseño de redes: redes telefónicas, eléctricas,
hidraúlicas, de ordenadores, de carreteras…
hidraúlicas
, de ordenadores, de carreteras…
Construcción de redes de mínimo coste
Construcción de redes de mínimo coste
Refuerzo de líneas críticas
Refuerzo de líneas críticas
Refuerzo de líneas críticas
Refuerzo de líneas críticas
Identificación de cuellos de botella
Identificación de cuellos de botella
Enrutamiento (evitar ciclos)
Enrutamiento (evitar ciclos)
……
Soluciones aproximadas para problemas NP.
Soluciones aproximadas para problemas NP.
Algoritmos de agrupamiento (análisis de clusters
Algoritmos de agrupamiento (análisis de
clusters))
……
44
Árboles generadores minimales
Árboles generadores
minimales
Algoritmos
Algoritmos greedy
greedy para resolver el problema:
para resolver el problema:
Kruskal: :
Algoritmo de
Algoritmo de Kruskal
Comenzando
Comenzando con T=
coste
coste y y añadir
de un
de un ciclociclo..
de un
de un ciclociclo..
añadir laslas aristas
con T=∅∅, , considerar
aristas a T salvo
considerar laslas aristas
a T salvo queque hacerlo
aristas en en orden
hacerlo suponga
creciente de de
suponga la la creación
creación
orden creciente
Algoritmo
Algoritmo de de borrado
Comenzando
Comenzando con
coste y y eliminar
de de coste
eliminar laslas aristas
con T=A,
inverso::
borrado inverso
T=A, considerar
considerar laslas aristas
aristas de T salvo
aristas en en orden
de T salvo queque esoeso desconectase
orden decreciente
decreciente
desconectase T.T.
de Prim::
Algoritmo de Prim
Algoritmo
con un nodonodo raízraíz arbitrario
Comenzando con un
Comenzando
desde
desde s s hacia
hacia afuera
afuera. En
cada pasopaso, se
el el nodonodo queque tenga
queque lo lo conecte
. En cada
tenga unauna arista
otros nodos
, se añade
añade al al árbol
arista de de menormenor coste
coste
nodos de T.
de T.
arbitrario s, s, hacer
conecte a a otros
hacer crecer
crecer el el árbol
árbol TT
árbol T T
55
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
Elementos del algoritmo de Kruskal
Elementos del algoritmo de
Kruskal
Conjunto de candidatos: Aristas del grafo.
Conjunto de candidatos: Aristas del grafo.
Función de selección: La arista de menor coste.
Función de selección: La arista de menor coste.
Función de factibilidad:
Función de factibilidad:
Función de factibilidad:
Función de factibilidad:
El conjunto de aristas no contiene ningún ciclo.
El conjunto de aristas no contiene ningún ciclo.
Criterio que define lo que es una solución:
Criterio que define lo que es una solución:
El conjunto de aristas seleccionado conecta todos los
El conjunto de aristas seleccionado conecta todos los
vértices (árbol con n
vértices (árbol con n--1 aristas).
1 aristas).
Función objetivo: Suma de los costes de las aristas.
Función objetivo: Suma de los costes de las aristas.
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
función
función Kruskal
{{
Kruskal( Grafo
( Grafo G(V,A)
G(V,A) ))
set<aristas> C(A);
set<aristas> C(A);
set<aristas> S; // Solución inicial vacía
// Solución inicial vacía
set<aristas> S;
Ordenar(C);
Ordenar(C);
while
while (!(!C.empty
while
while (!(!C.empty
C.empty() &&
C.empty() &&
() && S.size
() && S.size
S.size()!=
S.size()!=
()!=V.size
()!=V.size
V.size()()--1) {
V.size()()--1) {
1) {
1) {
C.first();
(); // Arista de menor coste
// Arista de menor coste
HayCiclo((S,xS,x))
)) // ¿Solución factible?
// ¿Solución factible?
x = C.first
x =
C.erase
C.erase(x);
(x);
ifif (!(!HayCiclo
S.insert(x);
S.insert
(x);
}}
ifif ((S.size
S.size()==
()==V.size
V.size()()--1)1)
return
return S; S;
else
else
return “No hay solución”;
return
“No hay solución”;
}}
66
77
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
a
v
a
a
u
Añadir la arista crearía un ciclo.
Añadir la arista crearía un ciclo.
La arista forma parte del
La arista forma parte del
árbol generador minimal
árbol generador
minimal..
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
88
99
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
1010
1111
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
5
4
6
8
7
9
12
3
3
4
7
5
5
6
10
11
1212
1313
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
6
5
4
3
5
4
7
6
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
Optimalidad
Optimalidad del algoritmo de
del algoritmo de Kruskal
Kruskal
Teorema:
El algoritmo de Kruskal halla un árbol generador minimal.
El algoritmo de Kruskal halla un árbol generador minimal.
Demostración:
Por inducción sobre el número de aristas que se han
incluido en el árbol generador minimal.
1414
1515
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
Optimalidad
Optimalidad del algoritmo de
Demostración
Demostración
del algoritmo de Kruskal
Kruskal
Caso base: Sea k1 la arista de menor peso en A.
Entonces, existe un AGM tal que k1 ∈ T.
Entonces, existe un AGM tal que k1 ∈ T.
Suponemos que es cierto para n-1: La (n-1)-ésima arista
incluida por el algoritmo de Kruskal pertenece al AGM.
Demostramos que es cierto para n: La n-ésima arista
incluida por el algoritmo de Kruskal pertenece al AGM.
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
del algoritmo de Kruskal
Kruskal
Optimalidad
Optimalidad del algoritmo de
Demostración
Demostración
Caso base
Por reducción al absurdo:
Por reducción al absurdo:
Sea k1 la arista de menor peso en A.
Supongamos un AGM T’ que no incluye a k1.
Consideremos T'∪k1 con peso(T'∪k1) = peso(T') + peso(k1).
En T'∪k1 aparece un ciclo (¿por qué?), pero si eliminamos
cualquier arista del ciclo (x), distinta de k1, obtenemos un árbol
T*=T'+k1-x con peso(T*) = peso(T') + peso(k1) – peso(x).
Por tanto, como peso(k1) < peso(x),
deducimos que peso(T*) < peso(T'). Contradicción.
1616
1717
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
del algoritmo de Kruskal
Kruskal
Optimalidad
Optimalidad del algoritmo de
Demostración
Demostración
Inducción
Por reducción al absurdo:
Por reducción al absurdo:
Supongamos un AGM T' que incluye a {k1,..., kn-1} pero no
incluye a kn.
Consideremos T'∪kn con peso(T'∪kn) = peso(T') + peso(kn).
Aparece un ciclo, que incluirá al menos una arista x que NO
pertenece al conjunto de aristas seleccionadas {k1, ..., kn-1}
Eliminando dicha arista del ciclo, obtenemos un árbol T*=T'+kn-x
con peso(T*) = peso(T') + peso(kn) – peso(x).
Pero peso(kn) < peso(x), por lo que peso(T*) < peso(T').
Contradicción.
1818
Árboles generadores minimales
Árboles generadores
minimales
Algoritmo de Kruskal
Algoritmo de
Kruskal
función
función Kruskal
{{
Kruskal( Grafo G(V,A) )
( Grafo G(V,A) )
set<aristas> C(A);
set<aristas> C(A);
set<aristas> S;
set<a
Crear cuenta
Comentarios de: Análisis y Diseño de Algoritmos - Algoritmos Greedy sobre grafos (0)
No hay comentarios