Algoritmos para juegos | Tema 3: Algoritmos voraces sobre grafos Por Alejandro Vargas Lugo Obra de creación propia bajo licencia Creative Commons BY-NC-SA 4.0 Internacional https://creativecommons.org/licenses/by-nc-sa/4.0/deed.es

Introducción

En episodios anteriores...

En el tema 1 vimos algunos de los algoritmos básicos sobre grafos. En el tema 2 estudiamos los algoritmos voraces, mostrando algunos de los más representativos del conjunto de los que puede resolverse de manera óptima de forma consistente. En este tercer tema, indagaremos en algoritmos varios que se aplican sobre grafos que pueden resolverse óptimamente siguiendo una estrategia voraz similar a la del tema anterior.

Mínimas distancias

El problema de hallar la menor distancia de un punto a otro es uno de los más estudiados en el campo de los algoritmos, y la forma de resolverlo varía mucho en función de las características del entorno. Por ejemplo, en una cuadrícula, la distancia entre casillas adyacentes es siempre de una unidad. Por lo tanto, para hallar la distancia entre dos casillas cualesquiera, solo hace falta contar el número mínimo de casillas que hay de una a otra.

En el contexto de grafos, esto sería equivalente a trabajar con un grafo sin pesos (o con todos los pesos iguales a un valor constante). A la hora de resolver un problema de mínimas distancias con esta característica se puede usar el recorrido en anchura, llevar la cuenta de la "profundidad" avanzada y detenerse una vez que se ha llegado al destino.

¿Pero qué sucede si el grafo tiene pesos? La gran mayoría de problemas de este tipo involucran grafos con pesos o distancias variables: redes de carreteras conectando ciudades, rutas de aerolíneas, redes de cableado eléctrico o de datos, logística de mercancía, etc. Y en todos estos casos, a la hora de calcular mínimas distancias, normalmente se hace uso de un célebre algoritmo:

Algoritmo de Dijkstra

Nombrado en honor a su inventor, el matemático y científico de la computación Edsger W. Dijkstra, este algoritmo permite obtener fácilmente la distancia mínima desde un vértice hasta cualquier otro de un grafo con pesos positivos. El proceso de ejecución es el siguiente:

1. Se asigna distancia 0 al vértice origen y distancia infinita (∞) al resto de vértices.

2. Se va manteniendo un conjunto de vértices cuyo camino mínimo ya se conoce de forma definitiva.

3. En cada iteración se selecciona el vértice sin procesar con la menor distancia acumulada desde el vértice origen.

4. Para cada arista que sale de ese mismo vértice, se comprueba si al pasar por él se reduce la distancia conocida hasta el vértice adyacente. Si es así, se actualiza dicha distancia y se registra el vértice actual como su predecesor.

5. El vértice seleccionado se marca como procesado y no vuelve a considerarse.

6. El proceso continúa hasta procesar todos los vértices alcanzables o hasta llegar al vértice destino, en caso de que solo nos interese un camino en particular.

El resultado, si calculamos todas las distancias, es una lista de distancias a cada nodo. La implementación más habitual, y la estudiada en la asignatura, hace uso de una cola de prioridad (heapq en Python) para seleccionar de forma eficiente el siguiente vértice con la menor distancia acumulada.

Veamos el código:

def dijkstra(start, g):

    distances = [float('inf')] * len(g)
    distances[start] = 0

    pq = [(0, start)]

    while pq:
        current_distance, current_node = heapq.heappop(pq)

        if current_distance > distances[current_node]:
            continue

        for neighbor, weight in g[current_node]:
            new_distance = current_distance + weight

            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance
                heapq.heappush(pq, (new_distance, neighbor))

    return distances

Applet interactivo: ¿Aún tienes dudas? ¿Quieres probar con tus propios grafos? ¡Prueba el applet interactivo del algoritmo de Dijkstra!

https://algoritmos.neocities.org/applets/dijkstra

Árboles de recubrimiento mínimo

En ocasiones, lo que nos puede interesar es obtener el conjunto de aristas de menor peso/distancia que conecte a todos los vértices del grafo. A este conjunto se le denomina árbol de recubrimiento (o expansión) mínima, o MST (del inglés Minimum Spanning Tree).

Todo MST tiene siempre |V|-1 aristas, donde |V| es el número de vértices del grafo. Un grafo puede tener varios MST posibles: esta situación se puede dar cuando hay dos o más aristas de igual peso. Sin embargo, si todas las aristas tienen peso distinto, necesariamente habrá un único MST posible. Estudiaremos dos métodos para obtener el árbol de recubrimiento mínimo: el algoritmo de Prim y el algoritmo de Kruskal.

Algoritmo de Prim

El algoritmo de Prim, nombrado así por el científico de la computación Robert C. Prim, encuentra un MST de un grafo a partir de un vértice determinado. De forma similar al algoritmo de Dijkstra, la implementación más habitual, y la estudiada en la asignatura, hace uso de una cola de prioridad. Su funcionamiento es el siguiente:

1. Se parte del vértice proporcionado y se añade al conjunto de nodos visitados.

2. Se evalúan todas las aristas conectadas a dicho vértice que estén conectadas a otro vértice que aún no haya sido visitado y se añaden a la cola prorizando siempre aquellas de peso inferior.

3. Se extrae una arista de la cola y se añade al árbol solución.

4. El nuevo vértice que conecta se añade al conjunto de nodos visitados.

5. Se actualiza la cola de aristas candidatas agregando las nuevas aristas que parten del vértice recién incorporado.

6. Este proceso se repite hasta que todos los vértices forman parte del árbol.

El código resultante en Python es el siguiente:

xxxxxxxxxx
def prim_pq(g, start):

    pq = [(0, None, start)]
    visited = set()
    total_dist = 0
    mst = []

    while pq:
        dist, prev_node, node = heapq.heappop(pq)

        if node not in visited:
            visited.add(node)
            total_dist += dist

            if prev_node is not None:
                mst.append((prev_node, node, dist))

            for neighbor, distance in g[node]:
                if neighbor not in visited:
                    heapq.heappush(pq, (distance, node, neighbor))

    return total_dist, mst

Applet interactivo: ¿Aún tienes dudas? ¿Quieres probar con tus propios grafos? ¡Prueba el applet interactivo del algoritmo de Prim!

https://algoritmos.neocities.org/applets/prim

Algoritmo de Kruskal

El algoritmo de Kruskal también permite encontrar un árbol de recubrimiento mínimo (MST), pero a diferencia de Prim, este árbol se construye seleccionando las aristas por orden de peso, sin partir de un vértice en concreto. Su funcionamiento es el siguiente:

1. Se ordenan todas las aristas del grafo de menor a mayor peso.

2. Inicialmente, cada vértice forma un componente independiente.

3. Se recorren las aristas en el orden establecido en el primer paso.

4. Por cada arista evaluada, se comprueba si sus dos vértices pertenecen a componentes diferentes. Si es así, la arista se añade al árbol y ambos componentes se fusionan. Por contra, si pertenecen al mismo componente, la arista se descarta ya que no es necesaria.

5. El proceso continúa hasta que el árbol contiene |V|-1 aristas.