Búsqueda del camino más corto entre islas usando BFS en Python

Clase 33 de 52 • Curso de Algoritmos Avanzados: Grafos y Árboles

Resumen

¿Cómo implementar una solución al problema de las islas utilizando Python?

En este fascinante recorrido por las soluciones algorítmicas, exploramos cómo abordar el problema de encontrar la cantidad mínima de pasos necesarios para conectar dos islas en un mapa utilizando Python. La clave radica en comprender el uso de algoritmos DFS (Depth-First Search) y BFS (Breadth-First Search), técnicas fundamentales en la programación y el análisis de grafos.

¿Qué cambios son necesarios en la función inicial?

Para desarrollar la solución elegimos Python, pero antes de implementar el enfoque queremos asegurarnos de tener un punto de partida claro y adaptado a nuestro objetivo. Inicialmente, comenzamos con un código que resolvía el problema de contar la cantidad de islas. Vamos a modificarlo para enfocarnos en hallar la mínima cantidad de pasos que conecten las islas.

Renombrar la función: Cambiamos el nombre de la función a shortest_reach y se define para recibir solamente un mapa.
Eliminar variables innecesarias: Eliminamos la variable que contaba la cantidad de islas y otras que ya no aportan al nuevo objetivo.
Definir el retorno: Debemos retornar un entero que indique la mínima cantidad de pasos necesarios. Si no es posible conectar las islas, retornamos -1.

¿Cómo detectar cuándo se encuentra la segunda isla?

Para optimizar el proceso de búsqueda:

Crear una bandera boolean: Esta bandera, llamada encontré_isla, nos ayudará a detectar cuando alcanzamos la segunda isla. Esto nos permite dejar de buscar una vez que cumplimos el objetivo.
```
encontré_isla = False
```
Iterar por el mapa: Utilizamos ciclos que recorren el mapa, y aplicamos DFS cuando encontramos tierra. Sin embargo, antes de aplicar DFS, si ya encontramos la segunda isla, podemos salir del ciclo.

¿Cómo utilizar BFS para conectar las islas?

El uso de BFS es crucial en este problema, dado que este algoritmo examina las capas o niveles que rodean una isla hasta encontrar la siguiente:

Inicializar variables: Definimos cantidad_material para cuantificar el recurso necesario para crear el puente y lo iniciamos en cero.
Implementar la cola: En BFS utilizamos una cola (FIFO) para gestionar los puntos a explorar:
```
cola = [(inicio_x, inicio_y)]
```
Verificar condiciones: A medida que expandimos la búsqueda, si encontramos la otra isla, retornamos la cantidad de pasos necesarios. En lo contrario, seguimos explorando nuevos niveles.

¿Cómo implementar el código de manera efectiva?

Vamos a ver partes esenciales del código y cómo se ejecutan estos conceptos:

# Marcamos las posibles direcciones para moverse
direcciones = [(0, 1), (0, -1), (1, 0), (-1, 0)]

# Implementamos la lógica de iteración y búsqueda
while cola:
    for _ in range(len(cola)):
        actual_x, actual_y = cola.pop(0)
        if mapa[actual_x][actual_y] == 1:
            return cantidad_material
        for dx, dy in direcciones:
            nueva_x, nueva_y = actual_x + dx, actual_y + dy
            # Lógica para verificar si nueva posición es válida...

¿Qué pasa si no encontramos una solución?

Nuestro enfoque asegura que, si ninguno de los caminos posibles nos lleva a conectar las dos islas, el proceso retornará un valor de -1, indicando la imposibilidad de conexión con los datos dados.

Este enfoque te ofrece la oportunidad de profundizar en métodos de búsqueda y grafos. La programación competitiva involucra resolver problemas como estos con eficiencia, y esperamos que esta guía te haya sido útil para encarar desafíos similares. ¡Sigue aprendiendo y desarrollando tu habilidad en algoritmos y estructuras de datos!

Mario Alberto Hernández Pintor

student•

// Asumamos que solo hay dos islas en el mapa

const mapa1 = [
	[1,1,0,0,0],
	[1,0,0,1,0],
	[1,0,0,1,1],
	[1,0,0,1,1]
]

var DIMS = (mapa=>{
    return [mapa.length, mapa[0].length];
})(mapa1);

const visitados = [];
    for (var j = 0;j<DIMS[0];j++){
    	visitados.push([]);
    	for (var i = 0; i< DIMS[1];i++){
    		visitados[j].push(false);
    }};

function identificarIsla(inicio,mapa) {
    var bordes_isla = [];
    var pila = [inicio]
  
    while (pila.length > 0){
        
    	var celda_actual = pila.pop();

    	var flag = false
    	const direcciones = [
    	  [0,1],[0,-1],[1,0],[-1,0]
    	];
        for (const [r,c] of direcciones){
    	    const nr = celda_actual[0]+r;
    	    const nc = celda_actual[1]+c;
  
    	    if (nr >= 0 && nr< DIMS[0] && nc >=0 && nc < DIMS[1]){
    		   if (!visitados[nr][nc] && mapa[nr][nc]){
                 pila.push([nr,nc]);
               }
               if (!mapa[nr][nc]){
             	  flag = true;
               }
            }
    	 };

    	 if (flag){
    	 	bordes_isla.push([celda_actual[0],celda_actual[1],0])
    	 }
     
    	visitados[celda_actual[0]][celda_actual[1]] = true;
    }

    return bordes_isla;
}

function ObtenerBordes(mapa){
	var bordesIslas = []
	for(var i = 0; i < DIMS[0]; i++){
		for(var j = 0 ; j < DIMS[1]; j++){
			if (mapa[i][j] && !visitados[i][j]){
				bordesIslas.push(identificarIsla([i,j],mapa))
			}
		}
	}
	return bordesIslas;
}

function ExpansionPuente(mapa){
	var bordesIslas = ObtenerBordes(mapa)
	console.log("Bordes: ",bordesIslas)
	console.log("Visitados:",visitados)
	var cola = bordesIslas[0]

	while (cola.length > 0 ){
		var [row_actual, col_actual,nivel_actual] = cola.shift()
		visitados[row_actual][col_actual] = true;
		siguiente_nivel = nivel_actual + 1 

    	const direcciones = [
    	  [0,1],[0,-1],[1,0],[-1,0]
    	];
        for (const [r,c] of direcciones){
    	    const nr = row_actual+r;
    	    const nc = col_actual+c;
  
    	    if (nr >= 0 && nr< DIMS[0] && nc >=0 && nc < DIMS[1]){
    	    	for (const borde of bordesIslas[1]){
                   	  if (nr == borde[0] && nc == borde[1]){
                   	  	console.log(nivel_actual)
                   	  	return nivel_actual;
                   	  }}
    		    if (!visitados[nr][nc] && !mapa[nr][nc]){
                     cola.push([nr,nc,siguiente_nivel]); 
                   }
            }
    	 };
	}
}
console.log(mapa1)
ExpansionPuente(mapa1)
console.log("Visitados:",visitados)

Mario Alberto Hernández Pintor

student•

Edwin Uldarico Hernandez Osorio

student•

No me quedo claro como el algoritmo busco la ruta mas corta, en algún punto va a encontrar tierra y retornar cantidad de material, pero como se sabe si no hay otro borde que sea aun mas cercano

Imagine que el resultado seria como una lista de todas las distancias y se escogería la menor

Alexis Otaño

student•

Esto es por que BFS, justo lo que hace es que se aproxima un paso a la vez, en cuanto toca tierra ya sabe que es el minimo.

William Velázquez

student•

En la parte de BFS en teoría cola = [] por lo tanto el while nunca se ejecutará, no?

Ivo Zayas

student•

si, no se que onda según yo está mal esa solución

Ivo Zayas

student•

en el dfs cuando igualas la tierra que encontraste a dos, también guardas esa posición en el queue así ya empezas el bfs con el primer nivel!! ;)

Tomas A

student•

from typing import List
class Bridge:
    def shortestBridge(self, map: List[List[int]]) -> int:
        def dfs(i, j):
            if 0 <= i < len(map) and 0 <= j < len(map[0]) and map[i][j] == 1:
                map[i][j] = 2
                q.append((i, j))
                [dfs(x, y) for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]]
        q = []
        i, j = next((i, j) for i in range(len(map)) for j in range(len(map)) if map[i][j])
        dfs(i, j)
        bridge = 0
        while q:
            for _ in range(len(q)):
                i, j = q.pop(0)
                for a, b in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if 0 <= i + a < len(map) and 0 <= j + b < len(map):
                        if map[i + a][j + b] == 1: 
                          return bridge
                        if map[i + a][j + b] == 0:
                            map[i + a][j + b] = 2
                            q.append((i + a, j + b))
            bridge += 1
map = [[1,1,1,1,1],
       [1,0,0,0,1],
       [1,0,1,0,1],
       [1,0,0,0,1],
       [1,1,1,1,1]]
Bridge().shortestBridge(map)
map = [[1,1,0,0,1],
       [1,1,0,0,1],
       [1,0,0,0,1],
       [1,0,0,0,1],
       [1,0,0,1,1]]
Bridge().shortestBridge(map)

Tomas A

student•

from typing import List
from itertools import pairwise
from collections import deque
class Bridge:
    def shortestBridge(self, map: List[List[int]]) -> int:
        def dfs(i, j):
            q.append((i, j))
            map[i][j] = 2
            for a, b in pairwise((-1, 0, 1, 0, -1)):
                x, y = i + a, j + b
                if 0 <= x < len(map) and 0 <= y < len(map) and map[x][y] == 1:
                    dfs(x, y)

        q = deque()
        i, j = next((i, j) for i in range(len(map)) for j in range(len(map)) if map[i][j])
        dfs(i, j)
        bridge = 0
        while 1:
            for _ in range(len(q)):
                i, j = q.popleft()
                for a, b in pairwise((-1, 0, 1, 0, -1)):
                    x, y = i + a, j + b
                    if 0 <= x < len(map) and 0 <= y < len(map):
                        if map[x][y] == 1: return bridge
                        if map[x][y] == 0:
                            map[x][y] = 2
                            q.append((x, y))
            bridge += 1
map = [
  [1,1,1,1,1],
  [1,0,0,0,1],
  [1,0,1,0,1],
  [1,0,0,0,1],
  [1,1,1,1,1],
]
response = Bridge().shortestBridge(map)
print(response)

map = [
  [1,1,0,0,1],
  [1,1,0,0,1],
  [1,0,0,0,1],
  [1,0,0,0,1],
  [1,0,0,1,1],
]
response = Bridge().shortestBridge(map)
print(response)

Cristian Toro

student•

Desarrollé una solución que, aunque es algo distinta de la presentada en clase, refleja un enfoque creativo y completamente propio, sin ayuda externa. No estoy completamente seguro de si este enfoque aumenta la complejidad temporal, pero he comprobado que resuelve el problema de manera efectiva.

Decidí modular el problema dividiéndolo en dos partes:

En la primera parte, el código localiza los límites de la primera isla encontrada.
En la segunda parte, evalúa los espacios de agua para calcular la distancia mínima posible entre las dos islas.

A continuación, presento mi código para que puedas revisarlo y ver si es necesario ajustar algo

def shrtestBetweenIsland(matriz):
    if not matriz:
        return -1
    
    cola = [(0, 0)]
    steps = [(+1 , 0) , (-1 , 0) , (0 , +1) , (0 , -1)]
    extremos = []
    lugares = set()
    limx = len(matriz)
    limy = len(matriz[0])
    distancia = 0


    while cola:
        for _ in range(len(cola)):
            posicionActual = cola.pop(0)
            lugares.add(posicionActual)

            for xd , yd in steps:
                nextPosicion = (posicionActual[0] + xd , posicionActual[1] + yd)

                if nextPosicion in lugares:
                    continue

                if not (0 <= nextPosicion[0] < limx) or not (0 <= nextPosicion[1] < limy):
                    continue

                if matriz[nextPosicion[0]][nextPosicion[1]] == 1:
                    cola.append(nextPosicion)

                if matriz[nextPosicion[0]][nextPosicion[1]] == 0:
                    extremos.append(posicionActual)

    while extremos:
        for _ in range(len(extremos)):
            posicionActual = extremos.pop(0)
            lugares.add(posicionActual)

            for xd , yd in steps:
                nextPosicion = (posicionActual[0] + xd , posicionActual[1] + yd)

                if nextPosicion in lugares:
                    continue

                if not (0 <= nextPosicion[0] < limx) or not (0 <= nextPosicion[1] < limy):
                    continue

                if matriz[nextPosicion[0]][nextPosicion[1]] == 1:
                    return distancia
                
                extremos.append(nextPosicion)

        distancia += 1

Cristian Toro

student•

En la segunda parte del código, no evalúa todas las distancia. solo se queda con las distancia mas corta

Tomas A

student•

from typing import List
class Bridge:
    def shortestBridge(self, map: List[List[str]]) -> int:
        def dfs(i, j):
            if 0 <= i < len(map) and 0 <= j < len(map[0]) and map[i][j] == 1:
                map[i][j] = 2
                queue.append((i, j))
                [dfs(x, y) for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]]

        queue = []
        islandFound = False

        # DFS to mark the first island
        for i in range(len(map)):
            for j in range(len(map[0])):
                if islandFound:
                    break
                if map[i][j] == 1:
                    dfs(i, j)
                    islandFound = True
                    break

        # BFS to find the shortest bridge
        bridgeSize = 0

        while queue:
            currentQueue = []
            while queue:
                currentCell = queue.pop(0)
                for x, y in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    newX = x + currentCell[0]
                    newY = y + currentCell[1]

                    if (newX < 0 or newX >= len(map)
                        or newY < 0 or newY >= len(map[newX])
                        or map[newX][newY] == 2):
                        continue
                    if map[newX][newY] == 1:
                        return bridgeSize
                    currentQueue.append([newX, newY])
                    map[newX][newY] = 2
            queue = currentQueue
            bridgeSize += 1

        return -1

map = [
  [1,1,1,1,1],
  [1,0,0,0,1],
  [1,0,1,0,1],
  [1,0,0,0,1],
  [1,1,1,1,1],
]
response = Bridge().shortestBridge(map)
print(response)

map = [
  [1,1,0,0,1],
  [1,1,0,0,1],
  [1,0,0,0,1],
  [1,0,0,0,1],
  [1,0,0,1,1],
]
response = Bridge().shortestBridge(map)
print(response)