Gráficos en Python - Teoría e Implementación - Algoritmo de Dijkstra vs Algoritmo A*

Los gráficos son una estructura de datos extremadamente versátil. ¡Más de lo que la mayoría de la gente cree! Los gráficos se pueden usar para modelar prácticamente cualquier cosa, dada su naturaleza de modo...

Cada algoritmo de búsqueda consta de:

  1. El estado actual del problema
  2. Posibles acciones que se pueden realizar para cambiar ese estado
  3. La capacidad de reconocer el estado final - nuestro objetivo

Cuando se trata de Inteligencia Artificial, hay dos tipos de algoritmos de búsqueda:

  • Algoritmos de búsqueda no informados
  • Algoritmos de búsqueda informados

En esta lección, repasaremos algunas de las diferencias entre dos de los algoritmos más populares, uno de cada categoría:

  1. Algoritmo de Dijkstra: algoritmo de búsqueda no informado
  2. Algoritmo A* (A Star): algoritmo de búsqueda informada

Algoritmos de búsqueda no informados {#algoritmos de búsqueda no informados}

Como ya mencionamos, un algoritmo de búsqueda tiene que ser capaz de:

  • Identificar el estado actual del problema.
  • Utilice un conjunto de acciones para modificar el estado actual
  • Identificar el estado final

Desinformado en este contexto significa que el algoritmo no tiene ninguna información adicional que lo ayude a determinar a dónde debe ir. Piense en ello como una persona miope que intenta navegar por las calles de una ciudad con la que no está familiarizado. Toda la información que tienen es lo que está justo frente a ellos, y nada más.

Ejemplos comunes son el algoritmo de búsqueda primero en profundidad, así como el algoritmo de búsqueda primero en amplitud. Sin embargo, en esta lección, solo nos centraremos en el algoritmo de Dijkstra.

Algoritmo de Dijkstra

El algoritmo de Dijkstra es un algoritmo que encuentra el camino más corto entre los nodos A y B en un gráfico dirigido con pesos de borde no negativos. En pocas palabras, hace esto al encontrar las rutas más cortas desde un nodo ‘A’ a todos los demás nodos, que, por supuesto, incluirán ‘B’.

Para indicar la longitud de la ruta más corta actual desde cualquier nodo dado al nodo A, necesitamos establecer "costos" para todos los nodos en el gráfico. Todos los costos se establecerán en “infinito” al principio, para asegurarnos de que cualquier otro costo con el que podamos compararlo sea menor que el inicial. La única excepción es el costo del nodo inicial: este nodo tendrá un costo de 0.

Repasemos este algoritmo paso a paso:

  1. Primero, crearemos un conjunto de nodos visitados (“visitados”), para realizar un seguimiento de todos los nodos a los que se les ha asignado su ruta más corta correcta al nodo “A”. Necesitamos esta lista para no retroceder a los nodos a los que ya se les ha asignado su ruta más corta.

  2. Hasta llegar al nodo final B, hacemos lo siguiente:

    1. We pick a node K with the shortest current cost and visit it (add it to the visited nodes set)
    2. We update the costs of all of K's adjacent nodes that are not visited yet: we do this by comparing their current cost with the sum of K's cost and the edge between K and the adjacent node in question.
  3. Cuando lleguemos al nodo final B, el algoritmo estará listo y se garantiza que el costo asignado al nodo final sea el camino más corto desde el nodo inicial hasta él.

Hay una manera interesante de explicar la idea detrás de este algoritmo:

Una gran analogía proviene del libro "Inteligencia artificial" de Predrag Janičić:

Digamos que cada nodo de un gráfico está representado por una esfera. Dos esferas están conectadas por un hilo si y solo si hay un borde entre ellas en un gráfico. Las longitudes de estos hilos son directamente proporcionales al peso de los bordes correspondientes. Todas estas esferas están colocadas exactamente en el mismo lugar en el suelo.

Recogemos la esfera que corresponde al nodo de partida ya medida que sube, arrastra consigo a las demás esferas. Las esferas dejan el suelo una por una, y la distancia más corta entre ellas y la esfera inicial es una distancia en línea recta entre ellas.

En términos del algoritmo de Dijkstra, esto es lo que realmente hacemos: tenemos dos grupos de esferas: las que están en el suelo y las que ya se han levantado. En cada iteración, levantamos una de las esferas del suelo y calculamos su distancia desde la primera esfera.

[Predrag Janičić, Mladen Nikolić - Inteligencia artificial]{.small}

La complejidad de este algoritmo es O(|E|+|V|log|V|), donde |E| representa el número de aristas, mientras que |V| representa el número de nodos.

Algoritmos de búsqueda informados {#algoritmos de búsqueda informados}

Los algoritmos de búsqueda informados no solo utilizan la información sobre posibles acciones para modificar el estado actual del problema, sino también información adicional que dirigiría la búsqueda hacia la meta. Esta información adicional es algún tipo de puntaje, un indicador de la calidad de un estado determinado. Este indicador no es necesariamente exacto, generalmente es solo una aproximación.

Esta aproximación suele denominarse heurística, derivada de la palabra griega "heurisko", que significa "buscar" o "descubrir".

Una función que calcula la puntuación (calidad) de un determinado estado se denomina función de evaluación. Si esta función es h, entonces h(n) representa la puntuación del estado n.

Cada vez que un algoritmo de búsqueda informada ingresa a un estado, calcula el valor f(n) para cada uno de sus estados vecinos, y luego ingresa al nodo con el valor más óptimo de f(n).

Uno de los algoritmos de búsqueda informada más populares es definitivamente el A* algoritmo. ¡Vamos a repasarlo ahora mismo!

Algoritmo A* (A Star)

El algoritmo A* se basa en la heurística para navegar por la búsqueda, pero a diferencia de muchos algoritmos similares con esta base (por ejemplo, el mejor algoritmo de búsqueda), es completo y (bajo ciertas condiciones) óptimo:

  • Un algoritmo completo es un algoritmo que garantiza una respuesta correcta para cualquier entrada correcta, si esa respuesta existe
  • Un algoritmo óptimo es un algoritmo que devuelve una respuesta en el menor tiempo posible.

La optimización de este algoritmo depende en gran medida de la calidad de su función de evaluación.

Para el algoritmo A*, la función de evaluación tiene una forma específica:

$$
f(n) = g(n) + h(n)
$$

Donde g(n) representa la ruta de costo más corta desde el nodo de inicio hasta el nodo n, y h(n) representa la aproximación heurística del valor del nodo n.

Dependiendo del problema, se pueden utilizar diferentes aproximaciones heurísticas para lograr la optimización. Elegir una heurística de calidad es uno de los pasos más importantes a la hora de implementar este algoritmo.

¡Ahora, vayamos al algoritmo A* en sí mismo! Para empezar, lo repasamos paso a paso:

  1. Para evitar bucles infinitos, garantizar la integridad y asegurarnos de que podemos arreglar las rutas ya encontradas, necesitamos dos listas:

    • Closed state list: a list in which we keep the visited states whose neighbors are all also visited
    • Open state list: a list in which we keep the visited states whose neighbors are not necessarily all visited

    At the beginning, the open state list only contains the start state (with the calculated value f(start_state)), while the closed state list is empty.

  2. Elegimos el estado n con el mejor valor de f(n). Si el estado n es también nuestro estado final, hemos terminado. Si no, pasamos por encima de sus vecinos directos.

  3. Para cada vecino m del estado n, verificamos si está en una de las dos listas. Si no, lo ponemos en la lista de estados abiertos. Marcamos n como el padre de m. Luego, calculamos g(m) y f(m). Sin embargo, si el vecino está en una de las dos listas, verificamos si la ruta desde el estado de inicio hasta el estado m sobre el estado n es más corta que la ruta existente actual a m. Si esto es cierto, marcamos n como padre de m y actualizamos g(m) y f(m). Si el estado m estaba antes en la lista cerrada, lo colocamos en la lista abierta.

  4. Finalmente, colocamos el nodo actual en la lista de estado cerrado.

  5. Siempre que haya elementos en la lista de estados abiertos, repetimos los pasos 2, 3 y 4.

  6. Si no llegamos al estado final, pero nuestra lista de estados abiertos está vacía, la ruta al estado final no existe

Rompecabezas de Loyd

Ahora que hemos repasado los dos algoritmos, podemos mostrar mejor sus diferencias usando un ejemplo, en este caso, el rompecabezas de Loyd, también conocido como el rompecabezas 15.

El rompecabezas de Loyd es un rompecabezas deslizante con 15 fichas cuadradas numeradas del 1 al 15 en un marco de 4 fichas de alto y 4 fichas de ancho, dejando una posición de ficha desocupada. Los mosaicos en la misma fila o columna de la posición abierta se pueden mover deslizándolos horizontal o verticalmente, respectivamente. El objetivo del rompecabezas es colocar las fichas en orden numérico.

El rompecabezas de Loyd consiste en un tablero de 4x4 y piezas etiquetadas con números del 1 al 15 que encajan en dicho tablero. Las piezas están dispuestas inicialmente al azar en el tablero. El objetivo del rompecabezas es colocar las piezas en orden ascendente solo deslizándolas:

En este ejemplo, vamos a usar el rompecabezas de Loyd de menor tamaño (2x3) para poder repasar cada paso más fácilmente.

Este va a ser el estado inicial de nuestro tablero:

1
2
3
[[2, 3, 5],
[1, 4, 0], 
[7, 8, 6]]

Queremos que nuestro estado final sea el siguiente:

1
2
3
[[0, 1, 2],
[3, 4, 5],
[6, 7, 8]]

El número 0 en nuestro tablero representa la ficha vacía.
El estado del tablero cambia cada vez que cambiamos el orden de los números en él. Por ejemplo, los únicos estados posibles después del primero son:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
[[2, 3, 5],
[1, 0, 4], 
[7, 8, 6]],


[[2, 3, 0],
[1, 4, 5], 
[7, 8, 6]] 


[[2, 3, 5],
[1, 4, 6], 
[7, 8, 0]]

Dado que hay miles de estados posibles para esta placa, es bastante difícil mostrar una explicación paso a paso sobre cómo funcionan estos dos algoritmos. Es por esto que vamos a intentar explicarlo solo de manera intuitiva y mediante su implementación.

Implementación

Antes de comenzar a implementar estos algoritmos, debemos importar un par de módulos de Python:

1
2
3
from collections import defaultdict
import copy
from queue import PriorityQueue

Ahora, hablemos de la representación de nuestra junta. En este código, vamos a representarlo de dos maneras: la primera forma serializada - en una matriz unidimensional, y la segunda forma deserializada - en una matriz (es decir, una matriz bidimensional, simplemente como los ejemplos anteriores).

En aras de la claridad, así es como se verá el estado final en la representación deserializada:

1
2
3
[[0, 1, 2],
[3, 4, 5],
[6, 7, 8]]

Y así es como se verá nuestro estado final serializado:

1
 [0:1:2:3:4:5:6:7:8]

La razón por la que necesitamos la representación serializada es porque es un poco más fácil de manipular, lo que da como resultado un código mucho más limpio.

Ahora, necesitamos escribir funciones que nos permitan convertir fácilmente de una representación a otra:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def serialize (state):
    result = []
    for row in state:
        for col in row:
            result.append(str(col))
    return ':'.join(result)

def deserialize (serialized):
    splitted = serialized.split(':')
    splitted = [int(x) for x in splitted]
    return [splitted[:3], splitted[3:6], splitted[6:]]

Otra función adicional que necesitamos para implementar estos algoritmos de manera más eficiente es una función que nos permita obtener posibles próximos estados: los vecinos del estado actual.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def get_neighbours(state):
    deserialized = deserialize(state)
    neighbours = []
    blank_i = -1
    blank_j = -1

    for i in range(0, 3):
        for j in range(0, 3):
            if deserialized[i][j] == 0:
                blank_i, blank_j = i, j
                break

    i = blank_i
    j = blank_j

    if i > 0:
        new_matrix = copy.deepcopy(deserialized)
        new_matrix[i][j] = new_matrix[i - 1][j]
        new_matrix[i - 1][j] = 0
        neighbours.append(serialize(new_matrix))
    if i < 2:
        new_matrix = copy.deepcopy(deserialized)
        new_matrix[i][j] = new_matrix[i + 1][j]
        new_matrix[i + 1][j] = 0
        neighbours.append(serialize(new_matrix))
    if j > 0:
        new_matrix = copy.deepcopy(deserialized)
        new_matrix[i][j] = new_matrix[i][j - 1]
        new_matrix[i][j - 1] = 0
        neighbours.append(serialize(new_matrix))
    if j < 2:
        new_matrix = copy.deepcopy(deserialized)
        new_matrix[i][j] = new_matrix[i][j + 1]
        new_matrix[i][j + 1] = 0
        neighbours.append(serialize(new_matrix))

    return zip(neighbours, [1 for x in neighbours])

Como ya mencionamos antes, los estados vecinos son los estados a los que podemos llegar cambiando los lugares del 0 (el mosaico vacío) con uno de los mosaicos a su alrededor (izquierda, derecha, arriba o abajo).

En esta función, trabajamos con una representación deserializada, pero devolvemos una representación serializada porque es la que necesitamos en nuestras funciones principales (para A* y el algoritmo de Dijkstra).

Primero, revisamos nuestra matriz y encontramos las coordenadas del mosaico vacío. Luego, usamos deepcopy para hacer una nueva matriz, y luego cambiamos todos los mosaicos posibles.

Por supuesto, es importante verificar la validez de cada mosaico antes de configurarlos.

Dijkstra

Ahora que hemos repasado las funciones adicionales, ¡entremos en los algoritmos reales!

El código del algoritmo de Dijkstra para este problema se ve así:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def dijkstra(start_node, target_node):
    start_node = serialize(start_node)
    target_node = serialize(target_node)

    visited = set()
    D = defaultdict(lambda: float('inf'))
    D[start_node] = 0

    pq = PriorityQueue()
    pq.put((0, start_node))

    parent = dict()
    parent[start_node] = None
    path_found = False
    iteratrion = 0
    while not pq.empty():
        (dist, current_node) = pq.get()
        if current_node == target_node:
            path_found = True
            break
        visited.add(current_node)

        for (neighbour, distance_from_current_node) in get_neighbours(current_node):
            if neighbour not in visited:
                old_cost = D[neighbour]
                new_cost = D[current_node] + distance_from_current_node
                if new_cost < old_cost:
                    pq.put((new_cost, neighbour))
                    D[neighbour] = new_cost
                    parent[neighbour] = current_node
        iteratrion += 1

    path = []
    if path_found:
        path.append(target_node)
        while True:
            parent_node = parent[target_node]
            if parent_node is None:
                break
            path.append(parent_node)
            target_node = parent_node
        path.reverse()
    return (path, iteratrion)

Como ya mencionamos, usaremos datos serializados. Además de eso, necesitaremos un conjunto de estados visitados, así como un diccionario que asigne un estado a su distancia desde el estado inicial. El valor predeterminado de un estado en este diccionario será inf.

Ponemos el estado de inicio en el diccionario y lo asignamos a 0, ya que su distancia de sí mismo es 0.

Otra cosa que necesitamos es una * cola de prioridad * que ordenará las distancias de los estados no visitados. Ponemos la distancia del estado de inicio y el propio estado en la cola de prioridad.

También necesitamos un diccionario (padres) que asigne un estado a su padre para reconstruir fácilmente una ruta desde el estado inicial hasta el estado final una vez que lo encontremos.

Siempre que tengamos estados en la cola de prioridad, tomamos el primer estado y verificamos si es o no el estado final. Si es así, rompemos el bucle, ya que hemos encontrado el camino. Si no, colocamos el estado en el conjunto visitado y calculamos los nuevos costos de todos sus vecinos no visitados.

El nuevo costo de un vecino es igual a la suma del costo del estado actual y la distancia entre el estado actual y el vecino en cuestión. Si el nuevo costo es menor que el costo anterior, ponemos al vecino con el nuevo costo en una cola de prioridad y actualizamos el diccionario de costos, así como el diccionario de los padres.

Una vez que encontramos la ruta correcta, la reconstruimos fácilmente con el diccionario 'parents'.

En esta función, contamos el número de iteraciones para poder comparar su número con el número de iteraciones en el algoritmo A*. Por eso los devolvimos junto con el camino.

Llamemos ahora al algoritmo de Dijkstra desde nuestra función principal, usando el ejemplo de un tablero que mencionamos antes:

1
2
3
4
5
6
7
if __name__ == '__main__':
    start_state = [[2,3,5], [1,4,0], [7,8,6]]
    target_state = [[0,1,2],[3,4,5],[6,7,8]]

    print('Dijkstra benchmark')
    (path, iteration) = dijkstra(start_state, target_state)
    print(path, iteration)

Esto va a producir el siguiente resultado:

1
2
3
Dijkstra benchmark
['2:3:5:1:4:0:7:8:6', '2:3:5:1:4:6:7:8:0', '2:3:5:1:4:6:7:0:8', '2:3:5:1:0:6:7:4:8', '2:0:5:1:3:6:7:4:8', '0:2:5:1:3:6:7:4:8', '1:2:5:0:3:6:7:4:8', '1:2:5:3:0:6:7:4:8', '1:2:5:3:6:0:7:4:8', '1:2:0:3:6:5:7:4:8', '1:0:2:3:6:5:7:4:8', '0:1:2:3:6:5:7:4:8', '3:1:2:0:6:5:7:4:8', '3:1:2:6:0:5:7:4:8', '3:1:2:6:4:5:7:0:8', '3:1:2:6:4:5:0:7:8', '3:1:2:0:4:5:6:7:8', '0:1:2:3:4:5:6:7:8'] 
12649

Como podemos ver, necesitamos 12649 iteraciones antes de encontrar el camino más corto desde el primer estado hasta el estado final del rompecabezas de Loyd.

A*

Ahora, repasemos el algoritmo A* más eficiente. Este algoritmo depende en gran medida de su heurística, por lo que debemos tener mucho cuidado al elegir uno. Esta función nos va a ayudar a navegar en la búsqueda hacia una solución más óptima.

Para cada estado, vamos a calcular una calidad. Esa calidad jugará un papel importante cuando se trata de clasificar los estados en una cola de prioridad.

De hecho, podemos pensar en el algoritmo de Dijkstra como un caso especial del algoritmo A*, donde la heurística es 0 para cada estado.

Ahora, pensemos en cómo podríamos escribir una función de evaluación para este problema en particular.

Vamos a utilizar la suma de las Distancias de Manhattan entre la ubicación actual de cada mosaico y la ubicación donde ese mismo mosaico debería terminar al final. Esta es una de las heurísticas más sencillas e intuitivas, por lo que a menudo se utiliza como punto de partida.

La Distancia Manhattan se calcula como la suma de las diferencias absolutas entre dos vectores.

$$
d((1,5,3),(4,7,2))=|(1-4)|+|(5-7)|+|(3-2)|=3 +2+1=6
$$

Lleva el nombre de Manhattan, donde los edificios están dispuestos en bloques cuadrados y las calles rectas se cruzan en ángulo recto, por lo que solo se puede mover en 4 direcciones: izquierda, derecha, arriba y abajo. Esto se asemeja a la forma en que podemos movernos en un rompecabezas de Floyd, por lo que esta heurística en particular es ideal para nuestro problema.

Así es como se verá nuestra función de evaluación:

1
2
3
4
5
6
7
def h(state):
    deserialized = deserialize(state)
    H = 0
    for i in range(0, 3):
        for j in range(0, 3):
            H += abs(deserialized[i][j] % 3 - j) + abs(deserialized[i][j] / 3 - i)
    return H

Ahora, otra función adicional que podríamos necesitar es una función que devuelva un estado en un conjunto abierto con la conjetura heurística más baja.

La entrada de esta función es el conjunto abierto, así como el diccionario que asigna el estado a su suposición heurística.

1
2
3
4
5
6
7
8
9
def in_open_set_with_lowest_heuristic_guess(open_set, heuristic_guess):
    result, min_guess = None, float('inf')
    for v in open_set:
        if v in heuristic_guess:
            guess = heuristic_guess[v]
            if guess < min_guess:
                result = v
                min_guess = guess
    return result

Ahora que lo eliminamos, vayamos a la implementación real del algoritmo A*:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
def astar_lloyd(start_node, target_node, h):
    start_node = serialize(start_node)
    target_node = serialize(target_node)

    open_set = set([start_node])

    parents = {}
    parents[start_node] = None

    cheapest_paths = defaultdict(lambda: float('inf'))
    cheapest_paths[start_node] = 0

    heuristic_guess = defaultdict(lambda: float('inf'))
    heuristic_guess[start_node] = h(start_node)

    path_found = False
    iteration = 0
    while len(open_set) > 0:
        # O(1)
        current_node = in_open_set_with_lowest_heuristic_guess(open_set, heuristic_guess)
        if current_node == target_node:
            path_found = True
            break

        open_set.remove(current_node)
        for (neighbour_node, weight) in get_neighbours(current_node):
            new_cheapest_path = cheapest_paths[current_node] + weight
            if new_cheapest_path < cheapest_paths[neighbour_node]:
                parents[neighbour_node] = current_node
                cheapest_paths[neighbour_node] = new_cheapest_path
                heuristic_guess[neighbour_node] = new_cheapest_path + h(neighbour_node)
                if neighbour_node not in open_set:
                    open_set.add(neighbour_node)
        iteration += 1

    path = []
    if path_found:
        while target_node is not None:
            path.append(target_node)
            target_node = parents[target_node]
        path.reverse()
    return (path, iteration)

Al igual que en el último algoritmo, usamos una representación serializada del tablero.

Vamos a necesitar dos conjuntos: un conjunto abierto, en el que mantenemos los estados visitados cuyos vecinos no son necesariamente todos visitados, así como el conjunto cerrado, en el que mantenemos los estados visitados cuyos vecinos también son todos visitado.

Ponemos el estado inicial en el conjunto abierto, el conjunto cerrado queda vacío.

Al igual que en la implementación del algoritmo de Dijkstra, mantenemos un diccionario 'padres' que nos ayuda a reconstruir la ruta, así como un diccionario para las rutas más baratas.

Además de eso, necesitaremos el diccionario de conjeturas heurísticas mencionado anteriormente.

Siempre que haya estados en el conjunto abierto, elegimos un estado con la conjetura heurística más baja como el siguiente estado actual. Si por casualidad nos hemos topado con el estado objetivo, rompemos el bucle y reconstruimos la ruta. De lo contrario, eliminamos el estado actual del conjunto abierto. Pasamos por los vecinos del estado actual y calculamos sus nuevas rutas más baratas.

La ruta más barata de un vecino es igual a la suma de la ruta más barata del estado actual y la distancia entre el estado actual y el vecino.

Si esta nueva ruta más barata es más pequeña que la ruta más barata que tenía el vecino antes, actualizamos los diccionarios principal, de conjetura heurística y de ruta más barata.

Si el estado vecino no está en el conjunto abierto, lo ponemos ahí.

Una vez que encontramos la ruta correcta, la reconstruimos fácilmente con el diccionario 'parents'.

En esta función, también contamos el número de iteraciones para que podamos comparar su número con el número de iteraciones en el algoritmo de Dijkstra. Por eso los devolvimos junto con el camino.

Llamemos ahora al algoritmo de Dijkstra desde nuestra función principal, usando el ejemplo de un tablero que mencionamos antes:

1
2
3
4
5
6
if __name__ == '__main__':
    start_node = [[2,3,5], [1,4,0], [7,8,6]]
    target_node = [[0,1,2],[3,4,5],[6,7,8]]
    print('Astar benchmark')
    (path, iteration) = astar_lloyd(start_node, target_node, h)
    print(path, iteration)

Esto va a producir una salida:

1
2
3
Astar benchmark
['2:3:5:1:4:0:7:8:6', '2:3:5:1:4:6:7:8:0', '2:3:5:1:4:6:7:0:8', '2:3:5:1:0:6:7:4:8', '2:0:5:1:3:6:7:4:8', '0:2:5:1:3:6:7:4:8', '1:2:5:0:3:6:7:4:8', '1:2:5:3:0:6:7:4:8', '1:2:5:3:6:0:7:4:8', '1:2:0:3:6:5:7:4:8', '1:0:2:3:6:5:7:4:8', '0:1:2:3:6:5:7:4:8', '3:1:2:0:6:5:7:4:8', '3:1:2:6:0:5:7:4:8', '3:1:2:6:4:5:7:0:8', '3:1:2:6:4:5:0:7:8', '3:1:2:0:4:5:6:7:8', '0:1:2:3:4:5:6:7:8'] 
217

Como podemos ver, ¡solo necesitábamos ‘217’ iteraciones antes de encontrar el mismo camino más corto desde el primer estado hasta el estado final del rompecabezas de Loyd!

Conclusión

Aunque el algoritmo de Dijkstra y el algoritmo A* encuentran los mismos caminos más cortos, ¡el algoritmo A* lo hace casi 60 veces más rápido! Mientras que el algoritmo de Dijkstra produjo la salida después de 12649 iteraciones, solo tomó 217 para el algoritmo A*.

Sin embargo, debe tenerse en cuenta que la eficiencia del algoritmo A* depende en gran medida de su función de evaluación, y con la función incorrecta, los resultados podrían ser incluso peores que los de Dijkstra.

Para resumir todo, dado que tenemos una buena estimación heurística de nuestro problema, definitivamente es más eficiente usar el algoritmo A* en comparación con el algoritmo de Dijkstra, aunque este no siempre será el caso, ya que puede depender en gran medida del problema en cuestión.

Referencias

  1. Predrag Janičić, Mladen Nikolić - Inteligencia artificial urses/VI_B5.pdf)
Licensed under CC BY-NC-SA 4.0