Download Algoritmos y Complejidad

Algoritmos y Complejidad
Algoritmos y Complejidad
Algoritmos greedy
Algoritmos y Complejidad
Algoritmos greedy
Pablo R. Fillottrani
Depto. Ciencias e Ingeniería de la Computación
Universidad Nacional del Sur
Primer Cuatrimestre 2014
Generalidades
Problema de la mochila
Caminos más cortos
Árbol minimal de cubrimiento
Scheduling de procesos
Problema del viajante
Algoritmos y Complejidad
Generalidades
Algoritmos y Complejidad
Generalidades
Generalidades
I
los algoritmos greedy son algoritmos que toman decisiones de
corto alcance, basadas en información inmediatamente
disponible, sin importar consecuencias futuras.
I
se usan generalmente para resolver problemas de optimización.
I
en general son algoritmos eficientes y fáciles de implementar, si
es que funcionan (no siempre son correctos!!).
Ejemplo
Problema: Dado un conjunto de monedas, ¿cuál es la mínima
cantidad de monedas necesarias para pagar n centavos?.
Solución greedy: Dar en lo posible monedas de denominación grande.
Algoritmos y Complejidad
Generalidades
Características generales de todo algoritmo greedy
I
se dispone de un conjunto C de candidatos de los cuales se debe
seleccionar un subconjunto que optimice alguna propiedad.
I
a medida que avanza el algoritmo, se van seleccionando
candidatos y se los coloca en el conjunto S de candidatos
aceptados, o R de candidatos rechazados.
Algoritmos y Complejidad
Generalidades
Esquema general para un algortimo greedy
C ::= conjunto de candidatos; S ::= {}
WHILE (C != {} and ! esSolución(S))
x ::= selección(C)
C ::= C - {x}
IF esViable(S + {x})
S ::= S + {x}
ENDIF
ENDWHILE
IF esSolución(S)
RETURN S
ELSE
RETURN "No encontré soluciones"
ENDIF
Algoritmos y Complejidad
Generalidades
Características generales de todo algoritmo greedy
I
existe una función esSolución() que determina si un
conjunto de candidatos es una solución, no necesariamente
optimal, del problema.
I
existe una función esViable() que determina si un conjunto
de candidatos es posible de ser extendido para formar una
solución, no necesariamente optimal, del problema.
I
existe una función selección() que devuelve el candidato
más promisorio del conjunto de aquellos que todavía no han sido
considerados.
Algoritmos y Complejidad
Problema de la mochila
Problema de la mochila
Problema: se tienen n objetos (cada objeto i tiene un peso wi y un
valor vi ); y una mochila con capacidad máxima de W . Se pretende
encontrar la manera de cargar la mochila de forma que se maximice el
valor de lo transportado y se respete su capacidad máxima.
I
se quiere encontrar valores xi , 0 ≤ xi ≤ 1 de forma que
n
maximice
∑
i =1
n
xi vi
siempre que
∑ xi wi ≤ W
i =1
Algoritmos y Complejidad
Problema de la mochila
Algoritmos y Complejidad
Problema de la mochila
Algoritmo greedy
I
claramente, si ∑ni=1 wi ≤ W entonces xi = 1 es optimal.
I
los casos interesantes aparecen cuando ∑ni=1 wi > W .
I
se puede implementar un algoritmo greedy con diversas
estrategias de selección.
Algoritmos y Complejidad
Problema de la mochila
I
datos de entrada: arreglos w[1..n], y v[1..n] contienen
con los pesos y valores de los objetos.
I
datos de salida: arreglo x[1..n] con la porción de cada
elemento que se carga en la mochila.
I
x[i]=1 significa que el objeto i se lleva completo; x[i]=0
que nada se lleva del objeto i; y x[i]=r, 0 < r < 1 significa
que el elemento i se lleva fraccionado.
Algoritmos y Complejidad
Problema de la mochila
Algoritmo greedy
FOR i ::=1 TO n
x[i] ::= 0
ENDFOR
peso ::= 0
WHILE peso<W
i ::= seleccion() //no definido cómo
IF peso+w[i]<W
x[i] ::= 1; peso ::= peso+w[i]
ELSE
x[i] ::= (W-peso)/w[i]; peso ::= W
ENDIF
ENDWHILE
RETURN x
I
la función selección() no está especificada.
I
para definirla se pueden considerar tres estrategias diferentes:
1. seleccionar el elemento de mayor valor
2. seleccionar el elemento de menor peso
3. seleccionar el elemento que tenga mayor valor por unidad de peso
Algoritmos y Complejidad
Algoritmos y Complejidad
Problema de la mochila
Problema de la mochila
Ejemplo de aplicación
I
sea n = 5, W = 100 y objetos con los siguientes pesos y valores:
w
v
I
obj. 1
10
20
obj. 2
20
30
obj. 3
30
66
obj. 4
40
40
obj. 5
50
60
las soluciones con las tres estrategias de selección son:
Max vi
Min wi
Max vi /wi
obj. 1
0
01
01
obj. 2
0
01
01
obj. 3
01
01
01
obj. 4
0 0,5
01
0
obj. 5
01
0
0 0,8
I
el ejemplo anterior demuestra que las dos primeras estrategias
resultan en algoritmos que no son correctos.
I
¿es correcta la tercer estrategia?
Valor
146
156
164
Algoritmos y Complejidad
Problema de la mochila
Correctitud
Teorema
Algoritmos y Complejidad
Problema de la mochila
Análisis del tiempo de ejecución
I
si se ordenan los elementos antes del ciclo greedy, la selección
en cada iteración puede hacerse en tiempo constante y el
algoritmo es entonces de Θ(n log n), determinado por el
ordenamiento.
I
si se usa un heap ordenado por la estrategia de selección, el
tiempo de inicialización cae a Θ(n), pero cada selección obliga a
mantener la estructura (heapify) por lo que el algoritmo también
resulta de Θ(n log n).
I
¿Cuál de estas dos implementaciones es más conveniente?
El algoritmo greedy para el problema de la mochila con selección por
mayor vi /wi siempre encuentra una solución optimal.
Prueba.
Sea X = (x1 , x2 , . . . , xn ) la solución que encuentra el algoritmo, y
Y = (y1 , y2 , . . . , yn ) cualquier otra solución viable (o sea tal que
∑ni=1 yi wi ≤ W ). Se prueba que valor (X ) − valor (Y ) ≥ 0, luego X es
una solución optimal.
Algoritmos y Complejidad
Caminos más cortos
Caminos más cortos
I
sea G = hN , Ai un grafo dirigido, con pesos no negativos, en
donde existe un nodo distinguido llamado origen.
I
se define el problema de hallar los caminos más cortos desde el
origen hasta cada uno de los restantes nodos.
I
consideraremos el grafo representado con una matriz de
adyacencia G, con nodos 1..n, y al nodo origen etiquetado con 1.
G[i , j ] contiene el peso del arco (i , j ) si (i , j ) ∈ A, o G[i , j ] = ∞ si
el arco no existe.
I
atacaremos primero el problema de encontrar las distancias
mínimas, y después el de los caminos que la implementan.
Algoritmos y Complejidad
Caminos más cortos
Algoritmos y Complejidad
Caminos más cortos
Algoritmo de Dijsktra
I
el algoritmo de Dijsktra es un algoritmo greedy para resolver
CAMINOS MÁS CORTOS.
I
consiste en mantener en S al conjunto de nodos cuyas distancias
mínimas ya se conoce, y en C a aquellos que todavía falta
calcular.
I
en cada paso se selecciona el elemento de C más cercano al
origen.
I
datos de entrada: G[1..n, 1..n] el grafo; se supone que el
origen es el nodo 1.
I
datos de salida: d[1..n] un arreglo donde d[i] es la
distancia más corta posible entre 1 y i.
Algoritmos y Complejidad
Caminos más cortos
Análisis del tiempo de ejecución
array d[1..n]
FOR i ::= 1 TO n
d[i] ::= G[1,i]
ENDFOR
S ::= {1}; C ::= {2, ..., n}
FOR j ::= 1 TO n-2
v ::= el elemento de C que minimiza d[v]
S ::= S + {v}; C ::= C-{v}
FOR cada w en C
d[w] ::= min{d[w],d[v]+G[v,w])
ENDFOR
ENDFOR
RETURN d
n−2 n−j
T (n)
= an + b + ∑
j =1 k =1
n−2 n−j −1
+∑
∑
j =1 k =1
∈ Θ(n2 )
n−2
∑ c+ ∑ d+
e=
j =1
Algoritmos y Complejidad
Algoritmos y Complejidad
Caminos más cortos
Caminos más cortos
Ejemplo de aplicación
Para obtener los caminos más cortos:
Paso
v
C
0
1
2
3
–
5
4
3
{2, 3, 4, 5}
{2, 3, 4}
{2, 3}
{ 2}
d
I
[50, 30, 100, 10]
[50, 30, 20, 10]
[40, 30, 20, 10]
[35, 30, 20, 10]
es suficiente con mantener un arreglo auxiliar p[1...n],
inicializado en 1, que contiene el último nodo en el camino más
corto entre 1 y i
I
luego se reemplaza la sentencia interna del segundo ciclo FOR
por
Algoritmos y Complejidad
Caminos más cortos
IF d[w]>d[v]+G[v,w]
d[w] ::= d[v]+G[v,w]
p[w] ::= v
ENDIF
Algoritmos y Complejidad
Caminos más cortos
Alternativas de implementación para el mismo algoritmo
Ejercicio:
I
¿cómo se obtienen los caminos más cortos a partir de p?
I
¿cambia el orden del tiempo de ejecución?
I
se pueden evitar los excesivos accesos a g[i,j] cuando
G[i,j]=∞ si el grafo es ralo (a << n2 ) representando al grafo
con una lista de adyacencia.
I
para seleccionar el próximo candidato se puede usar un heap;
pero será necesario actualizarlo cada vez que se elimina el
elemento y cada vez que se modifica alguna distancia en d.
I
el tiempo total es de Θ((a + n) log n) = Θ(a log n). ¿porqué?
Algoritmos y Complejidad
Caminos más cortos
Correctitud
Algoritmos y Complejidad
Caminos más cortos
Teorema
El Algoritmo de Dijsktra es correcto.
Teorema
Prueba.
El Algoritmo de Dijsktra es correcto.
Se prueba por inducción sobre la cantidad de iteraciones i que para
todo w ∈ N:
I
para la demostración se necesitará usar
Definición
Sea S ⊂ N. Un camino desde el origen a cualquier otro nodo es
especial con respecto a S si todos los nodos intermedios pertenecen
a S.
I
es claro que un camino especial con respecto al conjunto N de
todos los nodos del grafo, es simplemente un camino del grafo.
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Subgrafos de cubrimiento
1. si w ∈ Si entonces d [w ]i almacena la menor longitud de un
camino desde el origen hasta w.
2. si w 6∈ Si entonces d [w ]i almacena la menor longitud de un
camino especial c.r.a. Si desde el origen hasta w.
Luego la menor longitud de un camino especial con respecto a N es la
menor longitud de cualquier camino en G, por lo que cuando el
algoritmo termina d [v ] contiene la menor longitud de cualquier camino
de 1 a v .
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Árboles minimales de cubrimiento
Lema
I
sea G = hN , Ai un grafo no dirigido, conexo y con pesos.
Definición
un subgrafo de cubrimiento es un subgrafo G0 = hN , A0 i, A0 ⊆ A, que
también es conexo.
Definición
un subgrafo de cubrimiento es minimal si la suma de los arcos de A0
es minimal entre todos los grafos de cubrimiento de G.
I
los subgrafos minimales de cubrimiento son interesantes de
calcular porque representan una forma óptimal de mantener
conectados todos los nodos de un grafo
Sea G un grafo no dirigido, conexo y con pesos, entonces todo
subgrafo minimal de cubrimiento de G es un árbol (no tiene ciclos).
Lema
Sea G un grafo no dirigido, conexo y con pesos, entonces todo árbol
minimal de cubrimiento de G tiene n − 1 arcos, siendo n la cantidad
de nodos.
Lema
Sea G un grafo no dirigido, conexo y con pesos, entonces siempre
posee al menos un árbol minimal de cubrimiento.
I
I
las demostraciones quedan como ejercicios
se define entonces ÁRBOL DE CUBRIMIENTO MINIMAL al
problema computacional de, dado un tal G, encontrarle un árbol
minimal de cubrimiento.
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Algoritmos y Complejidad
Árbol minimal de cubrimiento
I
un algoritmo greedy para solucionar este problema tendría como
conjunto de candidatos a A.
I
se puede demostrar que tanto el algoritmo de Kruskal como el de
Prim son correctos ( esto es muy inusual para algoritmos greedy!)
I
un conjunto es una solución si contiene n − 1 arcos (es un árbol y
cubre todos los nodos).
I
para ambas demostraciones de correctitud se necesitará:
I
el control de viable se puede realizar controlando por la no
existencia de ciclos (los candidatos deben siempre formar un
árbol).
I
de acuerdo a distintas funciones de selección se definen dos
algoritmos para este problema: Kruskal y Prim.
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Definición
sea T ⊆ A, T es promisorio si está incluido en una solución optimal, ie
si está incluido en un árbol minimal de cubrimiento.
Definición
sea B ⊆ N, y (u , v ) ∈ A. Se dice que (u , v ) toca B si (u ∈ B y v 6∈ B),
o (u 6∈ B y v ∈ B).
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Algoritmo de Kruskal
Algoritmo de Kruskal
I
también será necesario el siguiente lema:
Lema
I
sea G = hN , Ai un grafo no dirigido, conexo, con pesos; B ⊂ N y
T ⊆ A un conjunto promisorio de arcos tal que ninguno de sus
miembros toca B. Luego si (u , v ) es uno de los arcos minimales que
tocan B, entonces T ∪ {(u , v )} también es promisorio.
el Algoritmo de Kruskal es un algoritmo greedy que resuelve el
problema de encontrar un árbol minimal de cubrimiento.
I
se caracteriza por seleccionar en cada iteración el menor de los
arcos todavía no considerados.
I
si el arco seleccionado junto con la solución parcial es viable,
entonces se incluye en la solución parcial. En caso contrario, es
descartado.
I
se puede demostrar que es correcto, ie que siempre encuentra
un árbol minimal de cubrimiento para un grafo no dirigido, conexo
y con pesos.
Prueba.
Sea G0 el árbol minimal de cubrimiento que contiene a T . Si
(u , v ) ∈ G0 , entonces T ∪ {(u , v )} es promisorio. Si (u , v ) 6∈ G0 y
suponemos por el absurdo que T ∪ {(u , v )} no es promisorio,
entonces existe G00 arbol de cubrimiento tal que
peso(G00 ) < peso(G0 ).
Algoritmos y Complejidad
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Árbol minimal de cubrimiento
Algoritmo de Kruskal
Algoritmo de Kruskal
Implementación
Paso
1
2
3
4
5
6
7
8
Arco
–
(a,b)
(b,c)
(d,e)
(f,g)
(a,d)
(b,e)
(d,g)
Componentes Conexos
{a}{b}{c }{d }{e}{f }{g }
{a, b}{c }{d }{e}{f }{g }
{a, b, c }{d }{e}{f }{g }
{a, b, c }{d , e}{f }{g }
{a, b, c }{d , e}{f , g }
{a, b, c , d , e}{f , g }
rechazado
{a, b, c , d , e, f , g }
Algoritmos y Complejidad
ordenar los arcos al principio para que la selección sea eficiente.
I
usar conjuntos disjuntos para controlar si un nuevo arco conecta
componentes distintos.
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Árbol minimal de cubrimiento
Algoritmo de Kruskal
ordenar A en L
n ::= |N|; a ::= |A|; T ::={}
D.initiate(N)
REPEAT
(u,v) ::= primer arco en L
eliminar (u,v) de L
compu ::= D.find(u)
compv ::= D.find(v)
IF (compu != compv)
D.merge(u,v)
T ::= T + {(u,v)}
ENDIF
UNTIL (|T|=n-1)
RETURN T
I
Algoritmo de Kruskal
costo
Θ(a log a)
b
Θ(n)
veces
1
1
1
c
c
a
a
a
a
a
×
×
c
×
c
n−1
n−1
c
a
Análisis del tiempo de ejecución
I
el tiempo de ejecución resulta:
T (G)
= Θ(a log a) + Θ(a) + Θ(n) + O ((2a + n − 1) log∗ n)
= Θ(a log n) + O (a log∗ n)
∈ Θ(a log n)
I
considerando que:
I
I
I
si G es conexo n − 1 ≤ a ≤ n(n − 1)/2.
K llamadas a operaciones find () y merge() en una E.D. de
conjuntos disjuntos de n elementos lleva tiempo de O (K log∗ n)
log∗ n ∈ O (log n), pero log n 6∈ O (log∗ n).
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Algoritmo de Kruskal
Otra implementación:
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Algoritmo de Kruskal
Correctitud
(ejercicio)
I
en lugar de ordenar los arcos al principio, se usa un heap
invertido para obtener el arco minimal en cada iteración.
I
disminuye el tiempo de inicialización, pero aumenta el del cuerpo
del ciclo.
I
el orden exacto del tiempo de ejecución obtenido es el mismo,
pero las constantes ocultas por la notación asintótica serían
menores.
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Algoritmo de Prim
Teorema
El algoritmo de Kruskal es correcto.
Prueba.
Por inducción sobre i, se prueba que todo Ti es promisorio usando el
lema 12, considerando como B al componente conexo de alguno de
los extremos del (u , v ) elegido en cada iteración. Luego el Ti final es
una solución optimal porque no puede tener más arcos.
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Algoritmo de Prim
Esquema general de Prim
I
en Kruskal la función de selección elige arcos sin considerar la
conexión con los arcos precedentes.
I
el algoritmo de Prim se caracteriza por hacer la selección en
forma local, partiendo de un nodo seleccionado y construyendo
el árbol en forma ordenada.
I
dado que el arco es seleccionado de aquellos que parten del
árbol ya construído, la viabilidad está asegurada.
I
también se puede demostrar que el algoritmo de Prim es
correcto, es decir que devuelve un árbol minimal de cubrimiento
en todos los casos.
T ::= {}
B ::= {un nodo de N}
WHILE (B != N)
encontrar (u,v) tal que peso((u,v)) sea
mínimo con u en B y v en N-B
T ::= T+{(u,v)}
B ::= B+{v}
ENDWHILE
RETURN T
Algoritmos y Complejidad
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Árbol minimal de cubrimiento
Algoritmo de Prim
Algoritmo de Prim
Implementación
Paso
1
2
3
4
5
6
7
Arco
–
(a,b)
(b,c)
(a,d)
(d,e)
(d,g)
(g,f)
B
{a}
{a, b}
{a, b, c }
{a, b, c , d }
{a, b, c , d , e}
{a, b, c , d , e, g }
{a , b , c , d , e , f , g }
Algoritmos y Complejidad
suponer G representado por una matriz de adyacencia.
I
usar un arreglo dist[] para conocer cuál es la distancia a B de
cada nodo
I
usar un arreglo nodoMasCerca[] para conocer con cuál nodo de
B se tiene esa distancia.
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Árbol minimal de cubrimiento
Algoritmo de Prim
// Inicialización
B ::= {1}; T ::= {}
FOR i ::=2 TO n
dist[i] ::= G[1,i]
nodoMasCerca[i] ::= 1
ENDFOR
I
Algoritmo de Prim
costo
veces
b
b
b
b
1
n−1
n−1
n−1
// Ciclo greedy
REPEAT
k ::= nodo con dist[k]>=0 y
que minimice dist[k]
min ::= dist[k]
T ::= T+{(k,nodoMasCerca[k])}
B ::= B+{k}; dist[k] ::= -1
FOR j ::= 2 TO n
IF G[j,k]<dist[j]
dist[j] ::= G[j,k]
nodoMasCerca[j] ::= k
ENDIF
ENDFOR
UNTIL |B|=n
costo
veces
O (n)
n−1
Θ(1)
Θ(1)
Θ(1)
n−1
n−1
n−1
Θ(1)
Θ(1)
Θ(1)
(n − 1)(n − 1)
(n − 1)(n − 1)
(n − 1)(n − 1)
Θ(1)
n−1
Algoritmos y Complejidad
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Árbol minimal de cubrimiento
Algoritmo de Prim
Algoritmo de Prim
Comparación entre Kruskal y Prim
I
el tiempo de ejecución de Prim resulta T (n) ∈ Θ(n2 ).
I
resultando
Algoritmo de Kruskal
Θ(a log n)
I
Algoritmo de Prim
Θ(n2 )
como n − 1 ≤ a ≤ n(n − 1)/2 vale:
I si a ≈ n conviene utilizar Kruskal
I si a ≈ n2 conviene utilizar Prim
Algoritmos y Complejidad
Árbol minimal de cubrimiento
Otra implementación
(ejercicio)
I
se usa un heap invertido para obtener el arco minimal en cada
iteración.
I
el orden del tiempo de ejecución en este caso es Θ(a log n).
I
¿cómo cambia el tiempo de ejecución si se representa al grafo
con una lista de adyacencia?
Algoritmos y Complejidad
Scheduling de procesos
Algoritmo de Prim
Correctitud
Definición del problema
I
se tiene un servidor (que puede ser un procesador, un cajero en
un banco, un surtidor de nafta, etc.) que tiene n clientes que
servir.
I
el tiempo de servicio requerido por cada cliente es conocido
previamente: ti , 1 ≤ i ≤ n.
I
Problema: SCHEDULING se quiere encontrar una secuencia de
atención al cliente que minimice el tiempo total de espera de los
clientes:
Teorema
El algoritmo de Prim es correcto.
Prueba.
Por inducción sobre i, se prueba que todo Ti es promisorio usando el
lema 12, con el mismo B del algoritmo. Luego el Ti final es una
solución optimal porque no puede tener más arcos.
n
Tiempo de espera =
∑ (tiempo del cliente i en el sistema)
i =1
Algoritmos y Complejidad
Algoritmos y Complejidad
Scheduling de procesos
Ejemplo
Scheduling de procesos
Algoritmo greedy
I
I
tres clientes numerados 1, 2, 3 con tiempos t1 = 5, t2 = 10, t3 = 3
Scheduling
Tiempo de espera
123:
5+ (5+10) + (5+10+3) = 38
132:
5+ (5+3) + (5+3+10) = 31
213:
10+ (10+5) + (10+5+3) = 43
231:
10+ (10+3) + (10+3+5) = 41
312:
3+ (3+5) + (3+5+10) = 29 ← optimal
321:
3+ (3+10) + (3+10+5) = 34
Algoritmos y Complejidad
el ejemplo anterior sugiere un algoritmo greedy en donde la
selección se hace en base el menor tiempo de servicio restante
siempre devuelve un algoritmo optimal.
Teorema
El algoritmo greedy para SCHEDULING es correcto.
Prueba.
ejercicio Ayuda: se prueba por el absurdo, suponiendo que existe una
solución mejor a la resuelta por el algoritmo, y se llega a una
contradicción.
Algoritmos y Complejidad
Scheduling de procesos
Problema del viajante
Definición del problema
I
Implementación:
I
I
se ordenan los procesos por orden creciente de tiempo de
servicio, y se implementa el ciclo greedy.
como el cuerpo del ciclo greedy es de Θ(1), y el ciclo no se repite
más de n veces, el tiempo del algoritmo en general estará
dominado por el tiempo del ordenamiento: Θ(n log n).
(ejercicio)
I
existen numerosas variantes de este problema (con más de un
procesos, con límites a la espera de los procesos, con ganancia
por la ejecución del proceso antes del límite, etc.), la mayoría de
las cuales tienen algoritmos greedy correctos.
I
I
se tienen n ciudades
y las distancias entre
cada par de ellas,
representadas en
una matriz.
I
la ciudad de origen
es 1.
Problema: VIAJANTE se quiere partir de una de ellas y visitar
exactamente una vez cada ciudad, regresando al punto de
partida al final, y recorriendo la menor distancia posible.
Algoritmos y Complejidad
Algoritmos y Complejidad
Problema del viajante
Problema del viajante
Algoritmo greedy
Ejemplo
I
I
un algoritmo greedy obvio consiste en, empezando del punto de
partida, elegir en cada paso la ciudad no visitada más próxima.
I
su tiempo de ejecución sería de O (n2 )
I
pero no es un algoritmo correcto
Algoritmos y Complejidad
Problema del viajante
I
pero, ¿no será VIAJANTE como MOCHILA donde varias
estrategias de selección no funcionan, pero existe una estrategia
que sí genera un un algoritmo correcto?
I
se puede demostrar que ninguna estrategia de selección directa
genera un algoritmo greedy correcto en todos los casos.
I
es más, para cualquier estrategia se puede encontrar ejemplos
de grafos cuya solución greedy es arbitrariamente muy mala.
matriz de distancias
Ciudades
1
2
3
4
5
1
–
2
3
–
3
10
8
–
4
11
12
9
–
5
7
9
4
5
–
6
25
26
20
15
18
I
solución greedy: 1,2,3,5,4,6,1, con distancia 60.
I
solución optimal: 1,2,3,6,4,5,1, con distancia 58.