SLIDES - Tecnología Digital V Diseño de Algoritmos (14)

Vista previa del material en texto

ALGORITMOS APROXIMADOS
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
Árbol generador mínimo
Árbol generador
Dado un grafo 𝐺, un árbol generador de 𝐺 es un subgrafo de 𝐺 que es un
árbol y tiene el mismo conjunto de vértices que 𝐺.
Longitud de un árbol generador
Sea 𝑇 = (𝑉, 𝐸) un árbol y 𝑙 : 𝐸 → 𝑅 una función que asigna longitudes (o
pesos) a las aristas de 𝑇. Se define la longitud de 𝑇 como 𝑙(𝑇) = ∑𝑒∈𝑇 𝑙(𝑒).
Árbol generador mínimo
Dado un grafo 𝐺 = (𝑉, 𝐸) un árbol generador mínimo 𝑇 de 𝐺 es un árbol
generador de 𝐺 de mínima longitud, es decir
𝑙(𝑇) ≤ 𝑙(𝑇′) para todo 𝑇′ árbol generador de 𝐺.
1
Árbol generador mínimo
Árbol generador
Dado un grafo 𝐺, un árbol generador de 𝐺 es un subgrafo de 𝐺 que es un
árbol y tiene el mismo conjunto de vértices que 𝐺.
Longitud de un árbol generador
Sea 𝑇 = (𝑉, 𝐸) un árbol y 𝑙 : 𝐸 → 𝑅 una función que asigna longitudes (o
pesos) a las aristas de 𝑇. Se define la longitud de 𝑇 como 𝑙(𝑇) = ∑𝑒∈𝑇 𝑙(𝑒).
Árbol generador mínimo
Dado un grafo 𝐺 = (𝑉, 𝐸) un árbol generador mínimo 𝑇 de 𝐺 es un árbol
generador de 𝐺 de mínima longitud, es decir
𝑙(𝑇) ≤ 𝑙(𝑇′) para todo 𝑇′ árbol generador de 𝐺.
1
Árbol generador mínimo
Árbol generador
Dado un grafo 𝐺, un árbol generador de 𝐺 es un subgrafo de 𝐺 que es un
árbol y tiene el mismo conjunto de vértices que 𝐺.
Longitud de un árbol generador
Sea 𝑇 = (𝑉, 𝐸) un árbol y 𝑙 : 𝐸 → 𝑅 una función que asigna longitudes (o
pesos) a las aristas de 𝑇. Se define la longitud de 𝑇 como 𝑙(𝑇) = ∑𝑒∈𝑇 𝑙(𝑒).
Árbol generador mínimo
Dado un grafo 𝐺 = (𝑉, 𝐸) un árbol generador mínimo 𝑇 de 𝐺 es un árbol
generador de 𝐺 de mínima longitud, es decir
𝑙(𝑇) ≤ 𝑙(𝑇′) para todo 𝑇′ árbol generador de 𝐺.
1
Ejemplo
jA
jB jC jD
jE
jFjGjH
jI��
�
�
�
4
8 6
@
@
@
@
@
8
1
3
12
5
�
�
�
�
�
6
3
�
�
�
�
�
10
@
@
@
@
@
9
13
A
A
A
A
A
A
A
A
A
AA
4
2
Ejemplo
jA
jB jC jD
jE
jFjGjH
jI��
�
�
�
4
8 6
@
@
@
@
@
8
1
3
12
5
�
�
�
�
�
6
3
�
�
�
�
�
10
@
@
@
@
@
9
13
A
A
A
A
A
A
A
A
A
AA
4
3
Ejemplo
jA
jB jC jD
jE
jFjGjH
jI��
�
�
�
4
8 6
1
3
3
@
@
@
@
@
9
A
A
A
A
A
A
A
A
A
AA
4
4
Algoritmo de Prim
Vojtech Jarnik Robert Prim Edsger Dijkstra
(1897–1970) (1921) (1930–2002)
5
Algoritmo de Prim
𝑉𝑇 := {𝑢} (𝑢 cualquier vértice de 𝐺)
𝐸𝑇 := ∅
𝑖 := 1
mientras 𝑖 ≤ 𝑛 − 1 hacer
elegir 𝑒 = (𝑢, 𝑣) ∈ 𝐸 tal que 𝑙(𝑒) sea mínima
entre las aristas que tienen un extremo
𝑢 ∈ 𝑉𝑇 y el otro 𝑣 ∈ 𝑉 \𝑉𝑇
𝐸𝑇 := 𝐸𝑇 ∪ {𝑒}
𝑉𝑇 := 𝑉𝑇 ∪ {𝑣}
𝑖 := 𝑖 + 1
retornar 𝑇 = (𝑉𝑇 , 𝐸𝑇 )
6
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
A
B C
I
FGH
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B C
I
FGH
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B
C
I
FGH
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B C
I
FGH
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B C
I
FGH
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B C
I
F
GH
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B C
I
FG
H
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B C
I
FGH
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B C
I
FGH
D
E
7
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134A
B C
I
FGH
D
E
7
Algoritmo de Kruskal
Joseph Kruskal
(1928–2010)
8
Algoritmo de Kruskal
𝐸𝑇 := ∅
𝑖 := 1
mientras 𝑖 ≤ 𝑛 − 1 hacer
elegir 𝑒 ∈ 𝐸 tal que 𝑙(𝑒) sea mínima entre las
aristas que no forman circuito con las
aristas que ya están en 𝐸𝑇
𝐸𝑇 := 𝐸𝑇 ∪ {𝑒}
𝑖 := 𝑖 + 1
retornar 𝑇 = (𝑉, 𝐸𝑇 )
9
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B D
E
10
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B D
E
10
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B D
E
10
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B D
E
10
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B D
E
10
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B
D
E
10
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B D
E
10
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B D
E
10
Ejemplo
A
B C D
E
FGH
I
4
8 6
8
1
3
12
56
3
10
9
134
GH
C
I
F
A
B D
E
10
Problema del viajante de comercio (TSP)
Problema del viajante de comercio
Dado un grafo completo 𝐺 = (𝑉, 𝑋) con longitudes asignadas a las aristas,
𝑙 : 𝑋 → ℝ+, encontrar un circuito hamiltoniano en 𝐺 de longitud mínima.
# El TSP es NP-hard. Su versión de decisión es un problema NP-completo.
# No se conocen algoritmos 𝜖-aproximados polinomiales para el TSP
general (sí se conocen cuando las distancias son euclídeas).
# Es el problema de optimización combinatoria NP-hard más estudiado.
11
Problema del viajante de comercio (TSP)
Problema del viajante de comercio
Dado un grafo completo 𝐺 = (𝑉, 𝑋) con longitudes asignadas a las aristas,
𝑙 : 𝑋 → ℝ+, encontrar un circuito hamiltoniano en 𝐺 de longitud mínima.
# El TSP es NP-hard. Su versión de decisión es un problema NP-completo.
# No se conocen algoritmos 𝜖-aproximados polinomiales para el TSP
general (sí se conocen cuando las distancias son euclídeas).
# Es el problema de optimización combinatoria NP-hard más estudiado.
11
Heurística del vecino más cercano
elegir un nodo 𝑣
𝑜𝑟𝑑𝑒𝑛(𝑣) := 0
𝑆 := {𝑣}
𝑖 := 0
mientras 𝑆 ≠ 𝑉 hacer
𝑖 := 𝑖 + 1
elegir la arista (𝑣, 𝑤) más barata con 𝑤 ∉ 𝑆
𝑜𝑟𝑑𝑒𝑛(𝑤) := 𝑖
𝑆 := 𝑆 ∪ {𝑤}
𝑣 := 𝑤
fin mientras
retornar 𝑜𝑟𝑑𝑒𝑛
# Cuál es la complejidad computacional de este algoritmo?
# Qué se puede decir sobre la calidad de las soluciones que encuentra?
12
Heurística del vecino más cercano
elegir un nodo 𝑣
𝑜𝑟𝑑𝑒𝑛(𝑣) := 0
𝑆 := {𝑣}
𝑖 := 0
mientras 𝑆 ≠ 𝑉 hacer
𝑖 := 𝑖 + 1
elegir la arista (𝑣, 𝑤) más barata con 𝑤 ∉ 𝑆
𝑜𝑟𝑑𝑒𝑛(𝑤) := 𝑖
𝑆 := 𝑆 ∪ {𝑤}
𝑣 := 𝑤
fin mientras
retornar 𝑜𝑟𝑑𝑒𝑛
# Cuál es la complejidad computacional de este algoritmo?
# Qué se puede decir sobre la calidad de las soluciones que encuentra?
12
Heurísticas de inserción
𝐶 := un circuito de longitud 3
𝑆 := {nodos de 𝐶}
mientras 𝑆 ≠ 𝑉 hacer
ELEGIR un nodo 𝑣 ∉ 𝑆
𝑆 := 𝑆 ∪ {𝑣}
INSERTAR 𝑣 en 𝐶
fin mientras
retornar 𝐶
# Cómo ELEGIR?
# Cómo INSERTAR?
# Cuál es la complejidad computacional de este algoritmo?
# Qué se puede decir sobre la calidad de las soluciones que encuentra?
13
Heurísticas de inserción
𝐶 := un circuito de longitud 3
𝑆 := {nodos de 𝐶}
mientras 𝑆 ≠ 𝑉 hacer
ELEGIR un nodo 𝑣 ∉ 𝑆
𝑆 := 𝑆 ∪ {𝑣}
INSERTAR 𝑣 en 𝐶
fin mientras
retornar 𝐶
# Cómo ELEGIR?
# Cómo INSERTAR?
# Cuál es la complejidad computacional de este algoritmo?
# Qué se puede decir sobre la calidad de las soluciones que encuentra?
13
Heurísticas de inserción
𝐶 := un circuito de longitud 3
𝑆 := {nodos de 𝐶}
mientras 𝑆 ≠ 𝑉 hacer
ELEGIR un nodo 𝑣 ∉ 𝑆
𝑆 := 𝑆 ∪ {𝑣}
INSERTAR 𝑣 en 𝐶
fin mientras
retornar 𝐶
# Cómo ELEGIR?
# Cómo INSERTAR?
# Cuál es la complejidad computacional de este algoritmo?
# Qué se puede decir sobre la calidad de las soluciones que encuentra?
13
Paréntesis: Grafos eulerianos
A B
C
DE
Definición
Un grafo es euleriano si tiene un circuito que pasa exactamente una vez por
cada arista.
Teorema (Euler, 1736 – Hierholzer, 1873)
Un grafo es euleriano si y sólo si todos sus vértices tienen grado par.
Algoritmo de Hierholzer. Dado un grafo euleriano, se puede construir un
circuito eulerianoen 𝑂(𝑚).
14
Paréntesis: Grafos eulerianos
A B
C
DE
Definición
Un grafo es euleriano si tiene un circuito que pasa exactamente una vez por
cada arista.
Teorema (Euler, 1736 – Hierholzer, 1873)
Un grafo es euleriano si y sólo si todos sus vértices tienen grado par.
Algoritmo de Hierholzer. Dado un grafo euleriano, se puede construir un
circuito euleriano en 𝑂(𝑚).
14
Paréntesis: Grafos eulerianos
A B
C
DE
Definición
Un grafo es euleriano si tiene un circuito que pasa exactamente una vez por
cada arista.
Teorema (Euler, 1736 – Hierholzer, 1873)
Un grafo es euleriano si y sólo si todos sus vértices tienen grado par.
Algoritmo de Hierholzer. Dado un grafo euleriano, se puede construir un
circuito euleriano en 𝑂(𝑚).
14
TSP – Heurística del árbol generador
1. Encontrar un árbol generador mínimo 𝑇 de 𝐺.
2. Duplicar las aristas de 𝑇.
3. Armar un circuito euleriano 𝐸 con las aristas de 𝑇 y sus duplicados.
4. Recorrer 𝐸 y armar con “cortocircuitos” un circuito hamiltoniano de 𝐺.
Teorema
Sea 𝐶𝐻 el circuito generado por la heurística del árbol generador y sea 𝐶∗
un circuito óptimo. Si las distancias cumplen la desigualdad triangular,
entonces
𝑙(𝐶𝐻 )
𝑙(𝐶∗) ≤ 2.
15
TSP – Heurística del árbol generador
1. Encontrar un árbol generador mínimo 𝑇 de 𝐺.
2. Duplicar las aristas de 𝑇.
3. Armar un circuito euleriano 𝐸 con las aristas de 𝑇 y sus duplicados.
4. Recorrer 𝐸 y armar con “cortocircuitos” un circuito hamiltoniano de 𝐺.
Teorema
Sea 𝐶𝐻 el circuito generado por la heurística del árbol generador y sea 𝐶∗
un circuito óptimo. Si las distancias cumplen la desigualdad triangular,
entonces
𝑙(𝐶𝐻 )
𝑙(𝐶∗) ≤ 2.
15
TSP – Heurística de Christofides (1976)
Nicos Christofides
(1942–2019)
16
TSP – Heurística de Christofides (1976)
1. Encontrar un árbol generador mínimo 𝑇 de 𝐺.
2. Encontrar un matching perfecto de peso mínimo 𝑀 en el grafo inducido
por los vértices de grado impar en 𝑇.
3. Armar un circuito euleriano 𝐸 con las aristas de 𝑇′ = 𝑇 + 𝑀.
4. Recorrer 𝐸 y armar con “cortocircuitos” un circuito hamiltoniano de 𝐺.
Teorema
Sea 𝐶𝐻 el circuito generado por la heurística de Christofides y sea 𝐶∗ un
circuito óptimo. Si las distancias cumplen la desigualdad triangular,
entonces
𝑙(𝐶𝐻 )/𝑙(𝐶∗) ≤ 3/2
.
17
TSP – Heurística de Christofides (1976)
1. Encontrar un árbol generador mínimo 𝑇 de 𝐺.
2. Encontrar un matching perfecto de peso mínimo 𝑀 en el grafo inducido
por los vértices de grado impar en 𝑇.
3. Armar un circuito euleriano 𝐸 con las aristas de 𝑇′ = 𝑇 + 𝑀.
4. Recorrer 𝐸 y armar con “cortocircuitos” un circuito hamiltoniano de 𝐺.
Teorema
Sea 𝐶𝐻 el circuito generado por la heurística de Christofides y sea 𝐶∗ un
circuito óptimo. Si las distancias cumplen la desigualdad triangular,
entonces
𝑙(𝐶𝐻 )/𝑙(𝐶∗) ≤ 3/2
.
17
TSP – Heurística de Christofides (1976)
# La Heurística de Christofides es el mejor algoritmo aproximado
conocido para el TSP métrico
... hasta 2020.
# En julio de 2020 Anna Karlin, Nathan Klein y Shayan Gharan
presentaron un algoritmo (3/2 − 10−36)-aproximado para el TSP métrico.
18
TSP – Heurística de Christofides (1976)
# La Heurística de Christofides es el mejor algoritmo aproximado
conocido para el TSP métrico ... hasta 2020.
# En julio de 2020 Anna Karlin, Nathan Klein y Shayan Gharan
presentaron un algoritmo (3/2 − 10−36)-aproximado para el TSP métrico.
18
TSP – Heurística de Christofides (1976)
# La Heurística de Christofides es el mejor algoritmo aproximado
conocido para el TSP métrico ... hasta 2020.
# En julio de 2020 Anna Karlin, Nathan Klein y Shayan Gharan
presentaron un algoritmo (3/2 − 10−36)-aproximado para el TSP métrico.
18