Resolución del Problema Shortest Bridge con DFS y BFS

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

Resumen

¿Cómo resolver de manera eficiente el problema de Shortest Bridge?

El problema de Shortest Bridge nos invita a optimizar la construcción de un puente entre dos islas en un mapa representado por ceros y unos. Los ceros representan agua y los unos, tierra. Aunque el objetivo parece simple, la solución implica una combinación ingeniosa de los algoritmos DFS y BFS para determinar el camino más corto posible. A lo largo de este proceso, utilizamos técnicas fundamentales que ya hemos trabajado en ejercicios anteriores. ¡Así que recuerda repasar la búsqueda en profundidad antes de continuar!

¿Cómo identificar la primera isla?

Para detectar la primera isla, empleamos DFS (Depth-First Search). Este algoritmo permite profundizar desde el primer cuadro donde encontramos un "1", lo que identifica el inicio de la isla. Este es un punto de referencia crítico para nuestro problema, ya que desde aquí comenzamos a marcar los bordes de esta isla. Estos límites son esenciales, pues luego servirán como punto de partida para explorar posibles rutas al construir el puente hacia la segunda isla.

Utilizamos DFS para identificar y registrar los bordes de la primera isla.
Desde el primer "1", el DFS se expande hasta que identifica todos los límites de la isla.
Los bordes se almacenan en una estructura tipo stack (pila) propia de DFS.

¿Cómo encontrar el punto más cercano de las dos islas?

Una vez identificados los bordes de la primera isla, es crucial decidir dónde están las dos islas más cerca. La construcción del puente será óptima en el punto donde la distancia entre ambas islas sea mínima.

Para abordar este problema, utilizamos BFS (Breadth-First Search). Avanzamos nivel por nivel desde los bordes de la primera isla hasta encontrar suelo, es decir, cuando nos topamos con un "1" de la segunda isla:

Iniciar BFS desde las coordenadas de los bordes (en una estructura de cola).
Avanzar por todos los casillas adyacentes: arriba, abajo, izquierda y derecha.
Utilizar un hash set para guardar y verificar las coordenadas ya visitadas, evitando redundancias.
Detener el proceso tan pronto como alcancemos tierra nuevamente, es decir, la segunda isla.

¿Cómo calcular la cantidad de materiales de construcción del puente?

El número de niveles de BFS que recorremos en el agua nos da la cantidad de material necesario. Sin embargo, tomemos en cuenta que cuando alcanzamos tierra (un "1"), no necesitamos incluir ese nivel en el conteo. El conteo de niveles avanzados menos uno nos proporciona la distancia correcta:

Llevar un conteo de los niveles de BFS.
Decrementar el conteo en uno al final para obtener la distancia real del puente necesario.

Esta mezcla de DFS y BFS nos brinda una solución eficiente y optimizada para el problema.

¿Qué otras consideraciones se deben tener en cuenta?

Podríamos preguntarnos si es posible invertir las estrategias, utilizando primero BFS y luego DFS. Te animo a reflexionar sobre esto y compartir tus ideas en los comentarios. Estas discusiones enriquecen nuestra comprensión y nos permiten aprender alternativas valiosas para un problema en particular. También te propongo un reto: intenta determinar la complejidad temporal y espacial de esta solución.

Recuerda, el aprendizaje es un proceso continuo, y cada enfoque nos brinda una oportunidad única para desarrollar nuestra habilidad para resolver problemas. ¡Así que sigue explorando, comentando, y nos vemos en la próxima clase para explorar más sobre la implementación de este algoritmo!

Yojan Antonio Pardo Zabala

student•

esta es mi solución en java, primero obtengo las coordenadas de la primera isla con DFS y luego desde cada punto de la primera isla hago BFS para encontrar la distancia entre las islas

package dev.yojanpardo.grafosarboles.shortestbridge;

import dev.yojanpardo.grafosarboles.recursion.Point;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class ShortestBridgeBetweenIslands {

    private static final Point[] DIRECTIONS = new Point[] {
            new Point(1,0),
            new Point(0,1),
            new Point(-1,0),
            new Point(0,-1)
    };

    public static void main(String[] args) {
        final int[][] islandsMap = buildIslandsMap();
        final Queue<Point> firstIslandCoordinates = findFirstIslandEdges(islandsMap);

        System.out.printf("the minimum required materials for build a bridge are: [%d]\n", calculateMinimumMaterialsForBridge(islandsMap, firstIslandCoordinates));

    }

    private static int calculateMinimumMaterialsForBridge(int[][] islandsMap, Queue<Point> firstIslandCoordinates) {
        int minRequiredMaterials = -1;
        final Set<Point> visitedPoints = new HashSet<>();
        while(!firstIslandCoordinates.isEmpty()){

            int size = firstIslandCoordinates.size();

            for(int i = 0; i < size; i++) {
                Point islandCoordinate = firstIslandCoordinates.poll();
                if(islandCoordinate != null && islandsMap[islandCoordinate.getX()][islandCoordinate.getY()] == 1){
                    return minRequiredMaterials;
                }
                if(!visitedPoints.contains(islandCoordinate)){
                    visitedPoints.add(islandCoordinate);
                    firstIslandCoordinates.addAll(getPossibleRoutesFromPoint(islandCoordinate, islandsMap));
                }
            }

            minRequiredMaterials++;

        }

        return -1;
    }

    private static Queue<Point> getPossibleRoutesFromPoint(Point islandCoordinate, int[][] islandsMap) {
        final Queue<Point> possibleRoutes = new LinkedList<>();

        for(Point direction : DIRECTIONS){
            Point point = new Point(islandCoordinate.getX() + direction.getX(), islandCoordinate.getY() + direction.getY());
            if(point.getX() >= 0 && point.getY() >= 0 && point.getX() < islandsMap.length && point.getY() < islandsMap[point.getX()].length ){
                possibleRoutes.add(point);
            }
        }

        return possibleRoutes;
    }

    private static Queue<Point> findFirstIslandEdges(int[][] islandsMap) {
        final Queue<Point> edgePoints = new LinkedList<>();

        for (int x = 0; x < islandsMap.length; x++){
            for(int y = 0; y < islandsMap[x].length; y++){
                if(islandsMap[x][y] == 1) {
                    dfs(islandsMap, x, y, edgePoints);
                    return edgePoints;
                }
            }
        }

        return edgePoints;
    }

    private static void dfs(int[][] islandsMap, int x, int y, final Queue<Point> edgePoints) {

        if(x < 0 || y < 0 || x >= islandsMap.length || y >= islandsMap[x].length || islandsMap[x][y] == 0){
            return;
        }

        islandsMap[x][y] = 0;
        edgePoints.add(new Point(x,y));

        for (Point direction : DIRECTIONS){
            dfs(islandsMap, x + direction.getX(), y + direction.getY(), edgePoints);
        }
    }


    /**
     * builds the map with two islands
     * @return the array with the islands
     */
    private static int[][] buildIslandsMap() {
        return new int[][] {
                {0,1,0,0,0,0,0},
                {1,1,1,0,0,0,0},
                {0,0,0,0,0,0,0},
                {0,0,0,0,0,1,1},
                {0,0,0,0,0,1,1},
        };
    }
}

Mario Alberto Hernández Pintor

student•

Hice una primera solución usando la distancia Manhatan, ya que solo nos pedían la distancia mas corta:


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

     const mapa3 = [
          [1,1,0,0,0],
          [1,0,0,0,0],
          [0,0,1,0,0],
          [0,0,0,0,1],
          [0,0,0,1,1]];

     const mapa4 = [
          [1,0,0,1],
          [1,0,0,0]
     ]


    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 obtener_adyacentes(celda) {
    	var adyacentes = [];
    	const direcciones = [
    		[0,1],[0,-1],[1,0],[-1,0]
    	];
    	for (const [r,c] of direcciones){
    		const nr = celda[0]+r;
    		const nc = celda[1]+c;
  
    		if (nr >= 0 && nr< DIMS[0] && nc >=0 && nc < DIMS[1]){
    		   if (!visitados[nr][nc]){
                 	adyacentes.push([nr,nc]);
             }}
    	};
    	return adyacentes;
    }

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

    		var adyacentes = obtener_adyacentes(celda_actual);
     
          if (adyacentes || adyacentes.length > 0){
    		  for (const adj of adyacentes){
    			
    			if (mapa[adj[0]][adj[1]]){
                   pila.push(adj)
                   isla.push(adj)
               }
    		}}

    		visitados[celda_actual[0]][celda_actual[1]] = true;
       }

       return isla;
    }

    function Manhatan(p1,p2) {
         return Math.abs(p1[0] - p2[0])+ Math.abs(p1[1]-p2[1]);
    }

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

     //console.log(lasIslas.length)
     var distancia = Infinity

     for (j = 0;j < lasIslas[0].length; j++){
          for (i=0;i< lasIslas[1].length;i++){
               var temp = Manhatan(lasIslas[0][j],lasIslas[1][i]);
               if (distancia > temp){
                    distancia = temp;
               }
          }
     }
     console.log("Distancia: ",distancia - 1)
     return distancia;
   }

//console.log("Manhatan: ", Manhatan([0,0],[0,3]))
Puente(mapa1);
console.log(visitados)

Manuel Juarez

student•

Acá les dejo mi solución al problema. Apunté a crear una solución general que admite cualquier número de islas, calcula todos los puentes posibles entre ellas y selecciona los de menor longitud. Tiene complejidad O(n²) y todavía hay mucho lugar para optimización, pero funciona bien para matrices menores a 10x10. El código:

import random
import collections
import itertools


def main():
    """
    Generates a random map of land and water, identifies islands, and finds the shortest bridges between them.

    The algorithm works as follows:
    1. Generates a 2D grid(map) with random land(1) and water(0) cells, based on given weights.
    2. Prints the original map for visualization.
    3. Uses Depth-First Search(DFS) to traverse the map and mark each island with a unique identifier(marker > 1).
    - This allows distinguishing between different islands.
    4. Counts the number of islands found.
    5. For each pair of islands, attempts to build all possible bridges(sequence of water cells) connecting them:
        - For each cell in an island, performs a Breadth-First Search(BFS) to explore possible bridges to other islands.
        - Keeps track of the shortest bridge found between each pair of islands.
    6. Prints the shortest bridge(if any) between each pair of islands, including its length.
    7. Prints the final map with islands marked by unique numbers.
    """

    def generate_land_map(row_number, column_number, land_weight, water_weight):
        return [[random.choices([0, 1], weights=[water_weight, land_weight])[0]
                 for _ in range(column_number)] for _ in range(row_number)]

    def format_map(land_map):
        return [[str(block) if block > 0 else ' ' for block in row] for row in land_map]

    def print_map(land_map):
        formated_map = format_map(land_map)
        for i in range(row_number):
            print(' '.join(formated_map[i]))

    def dfs(i, j, islands_marker):
        if 0 <= i < row_number and 0 <= j < column_number and land_map[i][j] == 1:
            land_map[i][j] = islands_marker

            dfs(i+1, j, islands_marker)
            dfs(i-1, j, islands_marker)
            dfs(i, j+1, islands_marker)
            dfs(i, j-1, islands_marker)

    def measure_island_extension(land_map, marker):
        return [(i, j) for i in range(len(land_map)) for j in range(len(land_map[0])) if land_map[i][j] == marker]

    def locate_islands_coordinates(land_map):
        island_extensions = []
        for k in range(number_of_islands):
            island_extension = measure_island_extension(
                land_map=land_map, marker=k+2)
            island_extensions.append(island_extension)
        return island_extensions

    def build_bridges(land_map: list[list[int]]):
        islands = locate_islands_coordinates(land_map=land_map)
        bridges = []
        queue = collections.deque()
        for island_index in range(len(islands)):
            island = islands[island_index]
            a, b = island[0]
            origin_island = land_map[a][b]

            for x, y in island:
                queue.append((x, y, []))

                while queue:
                    i, j, bridge = queue.popleft()

                    # Define directions: down, up, right, left
                    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

                    for di, dj in directions:
                        ni, nj = i + di, j + dj

                        # Check bounds, water cell, and not already in bridge
                        if (0 <= ni < len(land_map) and
                            0 <= nj < len(land_map[0]) and
                            land_map[ni][nj] == 0 and
                                (ni, nj) not in bridge):

                            # Create new bridge list
                            new_bridge = bridge + [(ni, nj)]

                            queue.append((ni, nj, new_bridge))

                        # Check bounds, water cell, and not already in bridge and different island than origin island
                        elif (0 <= ni < len(land_map) and
                              0 <= nj < len(land_map[0]) and
                              land_map[ni][nj] != 0 and
                              (ni, nj) not in bridge and
                                land_map[ni][nj] != origin_island):
                            destination_island = land_map[ni][nj]
                            bridges.append(
                                (bridge, origin_island, destination_island))

        combs = [(i, j) for i, j in itertools.combinations(
            range(2, len(islands)+2), 2)]
        for comb in combs:
            a_to_b_bridges = [
                bridge[0] for bridge in bridges if bridge[1] == comb[0] and bridge[2] == comb[1]]
            shortest_bridge = min(
                a_to_b_bridges, key=len) if a_to_b_bridges else []
            print(
                f"Shortest bridge from {comb[0]} to {comb[1]}: {shortest_bridge} (Length: {len(shortest_bridge)})"
                if len(shortest_bridge) else f"No bridge from {comb[0]} to {comb[1]}")
            

    row_number = 10
    column_number = 10
    land_weight = 0.5
    water_weight = 0.5
    land_map = generate_land_map(
        row_number, column_number,land_weight,water_weight)
    number_of_islands = 0

    print("\n", "Original map".center(column_number, "*"))
    print_map(land_map)

    """
    islands_marker marks the different island with different numbers,
     so the coordinates of the islands can be identified later on
    """
    islands_marker = 1
    for i in range(row_number):
        for j in range(column_number):
            if land_map[i][j] == 1:
                islands_marker += 1
                dfs(i, j, islands_marker,)
                number_of_islands += 1

    print(f"Number of Islands: {number_of_islands}")

    build_bridges(land_map)

    print("\n", "Final map".center(column_number, "*"))
    print_map(land_map)


if __name__ == '__main__':
    main()