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

Vista previa del material en texto

CAMINO MíNIMO
Tecnología Digital V: Diseño de Algoritmos
Universidad Torcuato Di Tella
El problema de camino mínimo
Problema
Dados ...
1. Un grafo dirigido pesado � = (#, �), con una función de distancia
3 : �→ ℝ+ asociada con los arcos, y
2. nodos B, C ∈ # de origen y destino,
... determinar el camino pesado más corto en � entre los nodos B y C.
1
Camino mínimo en grafos
Aplicación I
Determinar el camino más corto entre dos ciudades en un mapa vial.
2
Camino mínimo en grafos
Aplicación II
Determinar el camino más corto entre dos puntos de una ciudad (a pie, en
auto, o en bicicleta).
3
Camino mínimo en grafos
www.openstreetmap.org
4
Camino mínimo en grafos
# Arcos con peso negativo: Si el grafo � no contiene ciclos de peso
negativo o contiene alguno pero no es alcanzable desde B, entonces el
problema sigue estando bien definido, aunque algunos caminos puedan
tener longitud negativa.
# Sin embargo, si � tiene algún ciclo con peso negativo alcanzable desde B,
el concepto de camino de peso mínimo deja de estar bien definido.
# Propiedad de subestructura óptima de un camino mínimo: Sea %8 9 un
camino mínimo entre 8 y 9, y sea : ∈ %8 9 . Entonces, el subcamino de %8 9
entre 8 y : es un camino mínimo entre 8 y :.
5
Camino mínimo en grafos
# Arcos con peso negativo: Si el grafo � no contiene ciclos de peso
negativo o contiene alguno pero no es alcanzable desde B, entonces el
problema sigue estando bien definido, aunque algunos caminos puedan
tener longitud negativa.
# Sin embargo, si � tiene algún ciclo con peso negativo alcanzable desde B,
el concepto de camino de peso mínimo deja de estar bien definido.
# Propiedad de subestructura óptima de un camino mínimo: Sea %8 9 un
camino mínimo entre 8 y 9, y sea : ∈ %8 9 . Entonces, el subcamino de %8 9
entre 8 y : es un camino mínimo entre 8 y :.
5
Camino mínimo en grafos
# Arcos con peso negativo: Si el grafo � no contiene ciclos de peso
negativo o contiene alguno pero no es alcanzable desde B, entonces el
problema sigue estando bien definido, aunque algunos caminos puedan
tener longitud negativa.
# Sin embargo, si � tiene algún ciclo con peso negativo alcanzable desde B,
el concepto de camino de peso mínimo deja de estar bien definido.
# Propiedad de subestructura óptima de un camino mínimo: Sea %8 9 un
camino mínimo entre 8 y 9, y sea : ∈ %8 9 . Entonces, el subcamino de %8 9
entre 8 y : es un camino mínimo entre 8 y :.
5
Algoritmo de Dijkstra (1959)
Edsger Dijkstra (1930–2002)
www.cs.utexas.edu/users/EWD
6
Algoritmo de Dijkstra (1959)
# Asumimos que las longitudes de las aristas son positivas. El grafo puede
ser orientado o no orientado.
Algoritmo de Dijkstra
1. Asignar distancias tentativas 3B = 0 y 38 = ∞ para 8 ≠ B.
2. Mientras el destino no esté visitado:
◦ Seleccionar como nodo actual 8 el nodo no visitado con menor distancia
tentativa, y marcarlo como visitado.
◦ Para cada 9 ∈ #+(8) no visitado, calcular 3′
9
= 38 + 38 9 . Si 3′9 < 39 entonces
fijar 39 := 3′9 .
3. Retornar 3C .
7
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}( = {1, 6, 2}( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 10
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}
( = {1, 6}( = {1, 6, 2}( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}
( = {1, 6}( = {1, 6, 2}( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}
( = {1, 6}
( = {1, 6, 2}( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}
( = {1, 6}
( = {1, 6, 2}( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}
( = {1, 6}
( = {1, 6, 2}( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}
( = {1, 6, 2}
( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}
( = {1, 6, 2}
( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}
( = {1, 6, 2}
( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}( = {1, 6, 2}
( = {1, 6, 2, 5}
( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}( = {1, 6, 2}
( = {1, 6, 2, 5}
( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}( = {1, 6, 2}
( = {1, 6, 2, 5}
( = {1, 6, 2, 5, 3}( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}( = {1, 6, 2}( = {1, 6, 2, 5}
( = {1, 6, 2, 5, 3}
( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}( = {1, 6, 2}( = {1, 6, 2, 5}
( = {1, 6, 2, 5, 3}
( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}( = {1, 6, 2}( = {1, 6, 2, 5}
( = {1, 6, 2, 5, 3}
( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra - Ejemplo
1
2 3
4
56
4
3
1
4
3
3
8
1 1
0
∞ ∞
∞
∞∞
0
4 8
∞
∞3
0
4 8
∞
63
0
4 7
∞
53
0
4 7
9
53
0
4 7
8
53
( = {1}( = {1, 6}( = {1, 6, 2}( = {1, 6, 2, 5}( = {1, 6, 2, 5, 3}
( = {1, 6, 2, 5, 3, 4}
8
Algoritmo de Dijkstra
Lema
Llamamos (: a los nodos visitados luego de la iteración :. Al finalizar la
iteración : el algoritmo de Dijkstra determina el camino mínimo entre el
nodo B y cada uno de los nodos de (: .
Teorema
Dado un grafo orientado � con pesos positivos en las aristas, el algoritmo
de Dijkstra determina el camino mínimo entre el nodo B y el resto de los
nodos de �.
9
Algoritmo de Dijkstra
Lema
Llamamos (: a los nodos visitados luego de la iteración :. Al finalizar la
iteración : el algoritmo de Dijkstra determina el camino mínimo entre el
nodo B y cada uno de los nodos de (: .
Teorema
Dado un grafo orientado � con pesos positivos en las aristas, el algoritmo
de Dijkstra determina el camino mínimo entre el nodo B y el resto de los
nodos de �.
9
Algoritmo de Dijkstra con pesos negativos
1
23
4
56
4
3
7
3
1
4
3
2-2 1
0
∞ ∞
∞
∞∞
0
4 7
∞
∞3
0
4 7
∞
63
0
4 7
∞
62
10
Algoritmo de Dijkstra con pesos negativos
1
2 3
4
56
4
3
7
3
1
4
3
2-2 10
∞ ∞
∞
∞∞
0
4 7
∞
∞3
0
4 7
∞
63
0
4 7
∞
62
10
Algoritmo de Dijkstra con pesos negativos
1
2 3
4
56
4
3
7
3
1
4
3
2-2 1
0
∞ ∞
∞
∞∞
0
4 7
∞
∞3
0
4 7
∞
63
0
4 7
∞
62
10
Algoritmo de Dijkstra con pesos negativos
1
2 3
4
56
4
3
7
3
1
4
3
2-2 1
0
∞ ∞
∞
∞∞
0
4 7
∞
∞3
0
4 7
∞
63
0
4 7
∞
62
10
Algoritmo de Dijkstra con pesos negativos
1
2 3
4
56
4
3
7
3
1
4
3
2-2 1
0
∞ ∞
∞
∞∞
0
4 7
∞
∞3
0
4 7
∞
63
0
4 7
∞
62
10
Algoritmo de Dijkstra con pesos negativos
1
2 3
4
56
4
3
7
3
1
4
3
2-2 1
0
∞ ∞
∞
∞∞
0
4 7
∞
∞3
0
4 7
∞
63
0
4 7
∞
62
10
Algoritmo de Dijkstra con pesos negativos
1
2 3
4
56
4
3
7
3
1
4
3
2-2 1
0
∞ ∞
∞
∞∞
0
4 7
∞
∞3
0
4 7
∞
63
0
4 7
∞
62
10
Algoritmo de Dijkstra con pesos negativos
1
2 3
4
56
4
3
7
3
1
4
3
2-2 1
0
∞ ∞
∞
∞∞
0
4 7
∞
∞3
0
4 7
∞
63
0
4 7
∞
62
10
Algoritmo de Dijkstra, complejidad computacional
Algoritmo de Dijkstra
1. Asignar distancias tentativas 3B = 0 y 38 = ∞ para 8 ≠ B.
2. Mientras el destino no esté visitado:
◦ Seleccionar como nodo actual 8 el nodo no visitado con menor distancia
tentativa, y marcarlo como visitado.
◦ Para cada 9 ∈ #+(8) no visitado, calcular 3′
9
= 38 + 38 9 . Si 3′9 < 39 entonces
fijar 39 := 3′9 .
3. Retornar 3C .
Complejidad computacional:
# $(=2) con una implementación sencilla.
# $(< log =) guardando las distancias tentativas en un heap.
11
Algoritmo de Dijkstra, complejidad computacional
Algoritmo de Dijkstra
1. Asignar distancias tentativas 3B = 0 y 38 = ∞ para 8 ≠ B.
2. Mientras el destino no esté visitado:
◦ Seleccionar como nodo actual 8 el nodo no visitado con menor distancia
tentativa, y marcarlo como visitado.
◦ Para cada 9 ∈ #+(8) no visitado, calcular 3′
9
= 38 + 38 9 . Si 3′9 < 39 entonces
fijar 39 := 3′9 .
3. Retornar 3C .
Complejidad computacional:
# $(=2) con una implementación sencilla.
# $(< log =) guardando las distancias tentativas en un heap.
11
Algoritmo de Dijkstra, complejidad computacional
Algoritmo de Dijkstra
1. Asignar distancias tentativas 3B = 0 y 38 = ∞ para 8 ≠ B.
2. Mientras el destino no esté visitado:
◦ Seleccionar como nodo actual 8 el nodo no visitado con menor distancia
tentativa, y marcarlo como visitado.
◦ Para cada 9 ∈ #+(8) no visitado, calcular 3′
9
= 38 + 38 9 . Si 3′9 < 39 entonces
fijar 39 := 3′9 .
3. Retornar 3C .
Complejidad computacional:
# $(=2) con una implementación sencilla.
# $(< log =) guardando las distancias tentativas en un heap.
11
Algoritmo de Dijkstra, complejidad computacional
Algoritmo de Dijkstra
1. Asignar distancias tentativas 3B = 0 y 38 = ∞ para 8 ≠ B.
2. Mientras el destino no esté visitado:
◦ Seleccionar como nodo actual 8 el nodo no visitado con menor distancia
tentativa, y marcarlo como visitado.
◦ Para cada 9 ∈ #+(8) no visitado, calcular 3′
9
= 38 + 38 9 . Si 3′9 < 39 entonces
fijar 39 := 3′9 .
3. Retornar 3C .
Complejidad computacional:
# $(=2) con una implementación sencilla.
# $(< log =) guardando las distancias tentativas en un heap.
11
Reducciones desde otros problemas
Exact packing
Dados un conjunto � = {1, . . . , =} de objetos, el peso ?8 ∈ ℤ+ de cada objeto
8 ∈ � y una capacidad máxima " ∈ ℤ+, determinar si existe un
subconjunto de � con peso igual a ".
# Ejemplo:
1. � = {1, . . . , 4},
2. ?1 = 1, ?2 = 2, ?3 = 1, ?4 = 1,
3. " = 3.
# Cómo convertimos este problema en un problema de recorrido en un
grafo?
12
Reducciones desde otros problemas
Exact packing
Dados un conjunto � = {1, . . . , =} de objetos, el peso ?8 ∈ ℤ+ de cada objeto
8 ∈ � y una capacidad máxima " ∈ ℤ+, determinar si existe un
subconjunto de � con peso igual a ".
# Ejemplo:
1. � = {1, . . . , 4},
2. ?1 = 1, ?2 = 2, ?3 = 1, ?4 = 1,
3. " = 3.
# Cómo convertimos este problema en un problema de recorrido en un
grafo?
12
Reducciones desde otros problemas
Exact packing
Dados un conjunto � = {1, . . . , =} de objetos, el peso ?8 ∈ ℤ+ de cada objeto
8 ∈ � y una capacidad máxima " ∈ ℤ+, determinar si existe un
subconjunto de � con peso igual a ".
# Ejemplo:
1. � = {1, . . . , 4},
2. ?1 = 1, ?2 = 2, ?3 = 1, ?4 = 1,
3. " = 3.
# Cómo convertimos este problema en un problema de recorrido en un
grafo?
12
Reducciones desde otros problemas
13
Reducciones desde otros problemas
14
Reducciones desde otros problemas
Si además cada objeto tiene un costo de compra y queremos minimizar el
costo total ...
15
Reducciones desde otros problemas
Course scheduling
Dado el programa de charlas de una conferencia, determinar la mayor
cantidad de charlas a la que podemos asistir.
1. Todas las charlas se realizan en un mismo día.
2. Cada charla tiene un horario de inicio y final.
3. Una vez que entramos a una charla, no se puede salir hasta que termine.
# Cómo convertimos este problema en un problema de camino mínimo?
16
Reducciones desde otros problemas
Course scheduling
Dado el programa de charlas de una conferencia, determinar la mayor
cantidad de charlas a la que podemos asistir.
1. Todas las charlas se realizan en un mismo día.
2. Cada charla tiene un horario de inicio y final.
3. Una vez que entramos a una charla, no se puede salir hasta que termine.
# Cómo convertimos este problema en un problema de camino mínimo?
16
Reducciones desde otros problemas
Ejemplo. [9-11], [10-13], [9-15], [11-13], [13-15]
17
Reducciones desde otros problemas
Ejemplo. [9-11], [10-13], [9-15], [11-13], [13-15]
18
Camino mínimo con arcos negativos
Camino mínimo con arcos negativos!
1. Algoritmo de Bellman-Ford (1956). Complejidad $(=<) en el peor caso,
pero puede manejar arcos con longitudes negativas.
2. Algoritmo de Floyd-Warshall (1962). Complejidad $(=3). Calcula el
camino mínimo entre cada par de nodos, y también permite arcos con
longitudes negativas.
19
Camino mínimo con arcos negativos
Camino mínimo con arcos negativos!
1. Algoritmo de Bellman-Ford (1956). Complejidad $(=<) en el peor caso,
pero puede manejar arcos con longitudes negativas.
2. Algoritmo de Floyd-Warshall (1962). Complejidad $(=3). Calcula el
camino mínimo entre cada par de nodos, y también permite arcos con
longitudes negativas.
19
Camino mínimo con arcos negativos
Camino mínimo con arcos negativos!
1. Algoritmo de Bellman-Ford (1956). Complejidad $(=<) en el peor caso,
pero puede manejar arcos con longitudes negativas.
2. Algoritmo de Floyd-Warshall (1962). Complejidad $(=3). Calcula el
camino mínimo entre cada par de nodos, y también permite arcos con
longitudes negativas.
19
Algoritmo A*
Nodos visitados
Cuando termina, el Algoritmo de Dijkstra calcula el camino mínimo entre el
nodo origen y todos los nodos visitados.
A. Lundblom y R. Uggelberg, Comparative analysis of weighted pathfinding in realistic environments. Degree Project in Computer Science.
KTH Skolan för Datavetenskap och Kommunikation, Suecia (2017).
20
Algoritmo A*
Algoritmo A* = Dijkstra + estimación de distancia al destino
# Tenemos como parte de los datos una estimación ℓ : # → ℝ de la
distancia entre cada nodo y el nodo destino.
# Suponemos que esta estimación cumple la desigualdad triangular
ℓ8 ≤ ℓ 9 + 38 9 para todo arco 8 9 ∈ �.
# En cada paso del Algoritmo de Dijkstra, en lugar de usar la distancia 38 9
de cada arco 8 9 ∈ �, usamos 3̂8 9 := 38 9 + ℓ 9 − ℓ8 como su “distancia”.
# Si ℓ8 es una cota inferior de la distancia del nodo 8 al nodo destino, para
todo 8 ∈ # , entonces el Algoritmo A* es un algoritmo. Si no, es una
heurística.
21
Algoritmo A*
Algoritmo A* = Dijkstra + estimación de distancia al destino
# Tenemos como parte de los datos una estimación ℓ : # → ℝ de la
distancia entre cada nodo y el nodo destino.
# Suponemos que esta estimación cumple la desigualdad triangularℓ8 ≤ ℓ 9 + 38 9 para todo arco 8 9 ∈ �.
# En cada paso del Algoritmo de Dijkstra, en lugar de usar la distancia 38 9
de cada arco 8 9 ∈ �, usamos 3̂8 9 := 38 9 + ℓ 9 − ℓ8 como su “distancia”.
# Si ℓ8 es una cota inferior de la distancia del nodo 8 al nodo destino, para
todo 8 ∈ # , entonces el Algoritmo A* es un algoritmo. Si no, es una
heurística.
21
Algoritmo A*
Algoritmo A* = Dijkstra + estimación de distancia al destino
# Tenemos como parte de los datos una estimación ℓ : # → ℝ de la
distancia entre cada nodo y el nodo destino.
# Suponemos que esta estimación cumple la desigualdad triangular
ℓ8 ≤ ℓ 9 + 38 9 para todo arco 8 9 ∈ �.
# En cada paso del Algoritmo de Dijkstra, en lugar de usar la distancia 38 9
de cada arco 8 9 ∈ �, usamos 3̂8 9 := 38 9 + ℓ 9 − ℓ8 como su “distancia”.
# Si ℓ8 es una cota inferior de la distancia del nodo 8 al nodo destino, para
todo 8 ∈ # , entonces el Algoritmo A* es un algoritmo. Si no, es una
heurística.
21
Algoritmo A*
Algoritmo A* = Dijkstra + estimación de distancia al destino
# Tenemos como parte de los datos una estimación ℓ : # → ℝ de la
distancia entre cada nodo y el nodo destino.
# Suponemos que esta estimación cumple la desigualdad triangular
ℓ8 ≤ ℓ 9 + 38 9 para todo arco 8 9 ∈ �.
# En cada paso del Algoritmo de Dijkstra, en lugar de usar la distancia 38 9
de cada arco 8 9 ∈ �, usamos 3̂8 9 := 38 9 + ℓ 9 − ℓ8 como su “distancia”.
# Si ℓ8 es una cota inferior de la distancia del nodo 8 al nodo destino, para
todo 8 ∈ # , entonces el Algoritmo A* es un algoritmo. Si no, es una
heurística.
21
Algoritmo A*
Nodos visitados
# Cuando se utiliza una cota inferior para la función de estimación ℓ , el
Algoritmo A* visita una cantidad de nodos mucho menor.
# No obstante, el peor caso sigue siendo el mismo!
A. Lundblom y R. Uggelberg, Comparative analysis of weighted pathfinding in realistic environments. Degree Project in Computer Science.
KTH Skolan för Datavetenskap och Kommunikation, Suecia (2017).
22
Algoritmo A*
Nodos visitados
Otro ejemplo, ahora con grafos grilla que representan movimientos de un
barco a vela en una regata. El objetivo es llegar en el menor tiempo posible
de una boya a la siguiente.
F. Martínez y G. Sainz-Trápaga, Modelos y algoritmos de optimización combinatoria para planificación de rutas en regatas de barcos de vela.
Tesis de Licenciatura, Universidad de Buenos Aires, Argentina (2010).
23