03 Algoritmos Voraces PDF
03 Algoritmos Voraces PDF
03 Algoritmos Voraces PDF
Esquema de diseño
Consideraciones sobre su aplicación
Ejemplos de algoritmos voraces
Algoritmos voraces sobre grafos
OpenCourseWare 2015
Campus Virtual UPV/EHU
1/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño
Consideraciones sobre su aplicación
Ejemplos de algoritmos voraces
Algoritmos voraces sobre grafos
3/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño
Consideraciones sobre su aplicación
Ejemplos de algoritmos voraces
Algoritmos voraces sobre grafos
5/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño
Consideraciones sobre su aplicación
Ejemplos de algoritmos voraces
Algoritmos voraces sobre grafos
◦ La estrategia voraz trata de ganar todas las batallas sin darse cuenta de
que, como bien saben los estrategas militares y los jugadores de ajedrez,
para ganar la guerra muchas veces es necesario perder alguna batalla.
◦ Desgraciadamente, y como en la vida misma, pocos hechos hay para los
que podamos afirmar sin miedo a equivocarnos que lo que parece bueno
hoy será bueno también en el futuro. Y aquı́ radican las limitaciones de
este tipo de algoritmos.
6/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño
Consideraciones sobre su aplicación
Ejemplos de algoritmos voraces
Algoritmos voraces sobre grafos
7/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño
Consideraciones sobre su aplicación
Ejemplos de algoritmos voraces
Algoritmos voraces sobre grafos
8/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
◦ Solución
Un conjunto de monedas cuyo valor total es igual al importe a devolver.
◦ Completable
La suma de los valores de las monedas escogidas en un momento dado,
que no supera el importe a devolver.
◦ Función de selección
Elegir la moneda de mayor valor del sistema monetario tal que sumada al
completable no supere el importe a devolver.
◦ Función objetivo
Número total de monedas utilizadas en la solución (debe minimizarse).
10/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
11/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
15 = 11 + 1 + 1 + 1 + 1
14/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
teniéndose que:
s0 + s1 + ... + sn > r0 + r1 + ... + ri + (si+1 + Ai ) + ... + sn (5)
16/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
17/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
con la restricción:
n
X
pi xi ≤ M
i=1
18/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
Algoritmo propuesto
def Mochila ( peso , beneficio , M ) :
n = len ( peso )
solucion = [0.0 for i in range ( n ) ]
peso_actual = 0.0
while peso_actual < M :
i = m e j o r _obj eto_ resta nte ( peso , beneficio )
if peso [ i ] + peso_actual <= M :
solucion [ i ] = 1
peso_actual = peso_actual + peso [ i ]
else :
solucion [ i ] = ( M - peso_actual ) / peso [ i ]
peso_actual = M
return solucion
19/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
20/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
21/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
n
X n
X
(pi xi − pi yi ) = pi (xi − yi ) ≥ 0 (6)
i=1 i=1
22/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
◦ Ası́ pues, para todo i se tiene que: bpii (xi − yi ) ≥ pbjj (xi − yi ).
◦ Por último, teniendo en cuenta este último resultado y la desigualdad (6),
la diferencia de beneficios (7) queda:
n n
X bi bj X
f (x) − f (y ) = pi (xi − yi ) ≥ pi (xi − yi ) ≥ 0
i=1
pi pj i=1
24/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Esquema de diseño Cambio de monedas
Consideraciones sobre su aplicación El problema de la mochila (continuo)
Ejemplos de algoritmos voraces El problema de la mochila (discreto)
Algoritmos voraces sobre grafos
bi 11 6 6
: , ,
pi 5 3 3
25/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Grafos: Introducción
Grafos: Definiciones
◦ Un grafo simple G es un par (V , E ) tal que:
◦ V es un conjunto finito no vacı́o de nodos o vértices. Se llama orden de G
al número de vértices de G y se denotará n.
◦ E es un subconjunto del producto cartesiano V × V (pares de vértices),
cuyos elementos se denominan arcos (grafos dirigidos) o aristas (grafos no
dirigidos), que conectan los vértices de V .
◦ En un grafo dirigido, cada arco viene dado por un par ordenado < u, v >
donde u ∈ V es el vértice inicial del arco y v ∈ V es el vértice final.
◦ En un grafo no dirigido, no se distinguen los vértices inicial y final. Dados
dos vértices u, v ∈ V , la arista (u, v ) conecta dichos vértices en ambos
sentidos.
◦ En un grafo no existen autociclos ni multi-arcos.
◦ El máximo número de aristas de un grafo no dirigido es n(n − 1)/2. El
máximo número de arcos de un grafo dirigido es n(n − 1). En ambos
casos, se dice que el grafo es completo.
27/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Grafos: Definiciones
28/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Grafos: Definiciones
◦ Un camino entre los los vértices u y v de un grafo no dirigido G = (V , E )
es una secuencia de nodos u, w1 , . . . , wk , v tal que las aristas
(u, w1 ), . . . , (wk , v ) ∈ E . En el caso de grafos dirigidos, un camino se
define de la misma manera, pero usando arcos en lugar de aristas.
◦ Se denomina camino simple a un camino en el cual todos sus los vértices
son distintos salvo, quizás, el primero y el último.
◦ Se denomina ciclo a un camino simple en el cual los vértices primero y
último son iguales.
◦ La longitud de un camino es el número de arcos/aristas que lo componen.
◦ En un grafo no dirigido, dos vértices u y v están conectados si existe al
menos un camino entre ambos. Un grafo no dirigido es conexo si existe al
menos un camino entre todo par de vértices.
◦ En un grafo dirigido, un vértice u es accesible desde otro vértice v si
existe al menos un camino que parte de v y termina en u. Un grafo
dirigido es fuertemente conexo si todo vértice u es accesible desde
cualquier otro vértice v .
29/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Representación de grafos
30/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
3 10 1 2 3 4 5 6 7
4 1 0 9 3 ∞ ∞ 5 ∞
6
2 7
2 9 0 2 5 1 ∞ ∞
3 5
3 3 2 0 10 ∞ ∞ 6
2 5 7 4 ∞ 5 10 0 ∞ 8 7
9 1
8
5 ∞ 1 ∞ ∞ 0 4 ∞
4 3
1 6 5 ∞ ∞ 8 4 0 3
5
6
7 ∞ ∞ 6 7 ∞ 3 0
31/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Matrices en Python
El siguiente código:
produce la salida:
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
[[2, 3, 4], [3, 4, 5], [4, 5, 6]]
32/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
3 10
4 1 (2,9) (3,3) (6,5)
6
2 (1,9) (3,2) (4,5) (5,1)
2 7
3 5 3 (1,3) (2,2) (4,10) (7,6)
4 (2,5) (3,10) (6,8) (7,7)
2 5 7
9 1 5 (2,1) (6,4)
8
34/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Diccionarios en Python
Considerese el siguiente código:
def histograma ( s ) :
d ={}
for c in s :
if c not in d :
d [ c ]=1
else :
d [ c ]+=1
return d
35/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
for i in G :
for j , c in G [ i ]:
for i in G : print (i ,j , c )
print ( G [ i ]) 1 2 50
[(2, 50), (3, 30), (4, 100), (5, 10)] 1 3 30
[(2, 5)] 1 4 100
[(2, 20), (3, 50)] 1 5 10
[(4, 10)] 3 2 5
4 2 20
4 3 50
5 4 10
36/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
for arista in c :
if 2 in arista :
print ( arista , c [ arista ])
(1, 2) 50
(2, 3) 5
(2, 4) 20
37/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
3 10
4
Un árbol de recubrimiento de coste 6
2
mı́nimo sobre un grafo G es, como su 3 5
7
5
6
38/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
40/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
◦ Esquema general
◦ Los candidatos son las aristas de G .
◦ Un conjunto de aristas es factible si no contiene ningún ciclo.
◦ Un conjunto de aristas factible es solución si contiene todos los vértices de G .
◦ La función de selección varı́a con el algoritmo.
◦ La función objetivo que hay que minimizar es la suma del coste de las aristas
de la solución.
◦ Diremos que un conjunto de aristas factible es prometedor si añadiéndole
más aristas es posible obtener un árbol de recubrimiento de coste mı́nimo.
◦ Diremos que una arista sale de un conjunto de vértices si uno y sólo uno de
sus extremos está en dicho conjunto de vértices.
◦ Tendremos en cuenta también ciertas propiedades de los árboles:
◦ Un árbol con n nodos tiene exactamente n − 1 aristas.
◦ Si se añade una nueva arista entre dos de los vértices de un árbol, el
grafo resultante contiene un ciclo (y por tanto ya no es un árbol).
41/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
42/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Algoritmo de Kruskal
43/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Algoritmo de Kruskal
def Kruskal (n , c ) :
T = [] # inicialización del árbol de recubrimiento
B = [[ i ] for i in range ( n ) ] # inicialmente : n componentes conectadas ,
# cada una con un vértice
while len ( T ) < n -1:
e = argmin ( c ) # se extrae la arista de coste mı́nimo :
c . pop ( e )
i = componente (B , e [0]) # componente donde está el vértice e [0]
j = componente (B , e [1]) # componente donde está el vértice e [1]
if i != j :
B [ i ]. extend ( B [ j ]) # se fusionan las componentes
B . pop ( j )
T . append ( e ) # la arista e entra en la solución
return T
44/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Algoritmo de Kruskal
El algoritmo de Kruskal devuelve un árbol de recubrimiento de coste mı́nimo.
La demostración se hace por inducción sobre el número de aristas en T .
Si T es prometedor, sigue siendo prometedor tras añadir una nueva arista.
Cuando al algoritmo termina, T es la solución al problema.
◦ Base: el conjunto vacı́o es prometedor porque G es conexo y por tanto tiene que
existir solución.
◦ Hipótesis: T es prometedor antes de añadir una nueva arista e = (u, v ).
◦ Prueba: Las aristas de T dividen a los nodos de G en dos o más componentes
conexas. Por definición, el vértice u de la arista añadida se encuentra en una de
esas componentes y el vértice v en otra. Sea B el conjunto de vértices de la
componente que contiene a u:
◦ El conjunto B es un subconjunto estricto de los vértices de G
y no contiene a v .
◦ T es un conjunto prometedor tal que ninguna arista de T sale de B.
◦ La arista e tiene coste mı́nimo entre las aristas que salen de B.
Esto hace que se cumplan las condiciones del lema demostrado anteriormente, y
por tanto el conjunto T ∪ {e} es prometedor.
45/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Algoritmo de Prim
46/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Algoritmo de Prim
def Prim (n , c ) :
T = [] # inicialización del árbol de recubrimiento
B = [0] # B se inicializa con un vértice cualquiera
while len ( B ) < n :
e = argmin (B ,n , c ) # e : arista de menor coste t . q . e [0]∈B y e [1] ∈B
/
B . append ( e [1]) # el vértice e [1] entra en B
T . append ( e ) # la arista e entra en la solución
return T
47/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Algoritmo de Prim
48/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
49/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Ejemplo de aplicación 1
1
0 1
2
n = 4
5 6
c = { (0 ,1) : 1 , (0 ,2) : 5 , (0 ,3) : 2 ,
(1 ,2) : 4 , (1 ,3) : 6 , (2 ,3) : 3 } 4
2 3
3
51/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
6
1 2
n = 6 8 9
12 4
100 30
2 3
10 20 5
4 5
50
Paso w S D P
54/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
55/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
Demostración
(continúa...)
56/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces
Introducción
Grafos: Definición e implementación
Esquema de diseño
Árboles de recubrimiento de coste mı́nimo
Consideraciones sobre su aplicación
El problema del viajante: ciclos hamiltonianos
Ejemplos de algoritmos voraces
Caminos de coste mı́nimo: algoritmo de Dijkstra
Algoritmos voraces sobre grafos
58/58
OpenCourseWare Campus Virtual UPV/EHU LJRF & AVF Técnicas de diseño de algoritmos – Algoritmos voraces