viernes, octubre 15, 2010

Ruta más corta - Solución por fuerza bruta

El problema de encontrar la ruta más corta entre dos puntos se puede abordar por diferentes enfoques de programación. La solución más obvia es la de evaluar todas las posibles rutas para luego compararlas y encontrar la más corta. Si bien esta solución puede encontrar la ruta más corta (o más larga) en forma absoluta, su implementación cuando la cantidad de nodos a evaluar es relativamente alta es demasiado costosa computacionalmente hablando porque la cantidad de rutas tiende a crecer exponencialmente.

Una posible implementación de esta evaluación de todas las rutas por fuerza bruta se presenta a continuación. El programa tiene dos partes, en la primera de ellas está la definición de una clase Grafo, con los métodos para la creación de los nodos y la asignación de rutas entre dos puntos y la distancia entre cada punto. Cada nodo puede ser identificado con una letra o caracter y, para efectos de simplificar el proceso estas denominaciones se envían al constructor del grafo en una cadena de caracteres. El grafo se representa por una matriz cuadrada donde cada elemento de la matriz representa la distancia entre el nodo fila y el nodo columna respectivo. Se han obviado las comprobaciones para dar mayor claridad al código:

import java.util.*;

public class Grafo {
    int[][] grafo;
    char[]  nodos;

    Grafo(String serieNodos) {
        nodos = serieNodos.toCharArray();
        grafo = new int[nodos.length][nodos.length];
    }

    // asigna el tamaño de la arista entre dos nodos
    public void agregarRuta(char origen, char destino, int distancia) {
        int n1 = posicionNodo(origen);
        int n2 = posicionNodo(destino);
        grafo[n1][n2]=distancia;
        grafo[n2][n1]=distancia;
    }

    // retorna la posición en el arreglo de un nodo específico
    private int posicionNodo(char nodo) {
        for(int i=0; i<nodos.length; i++) {
            if(nodos[i]==nodo) return i;
        }
        return -1;
    }

    // encuentra la ruta mínima entre dos nodos del grafo
    public void encontrarRutaMinimaFuerzaBruta(char inicio, char fin) {
        int p1 = posicionNodo(inicio);
        int p2 = posicionNodo(fin);
        // cola para almacenar cada ruta que está siendo evaluada
        Stack<Integer> resultado = new Stack<Integer>();
        resultado.push(p1);
        recorrerRutas(p1, p2, resultado);
    }

    // recorre recursivamente las rutas entre un nodo inicial y un nodo final
    // almacenando en una cola cada nodo visitado
    private void recorrerRutas(int nodoI, int nodoF, Stack<Integer> resultado) {
        // si el nodo inicial es igual al final se muestra y evalúa la ruta en revisión
        if(nodoI==nodoF) {
            for(int x: resultado) System.out.print(nodos[x]+ " ");
            System.out.print(": " + evaluar(resultado));
            System.out.println();
            return;
        }
        // Si el nodoInicial no es igual al final se crea una lista con todos los nodos
        // adyacentes al nodo inicial que no estén en la ruta en evaluación
        List<Integer> lista = new Vector<Integer>();
        for(int i=0; i<grafo.length;i++) {
            if(grafo[nodoI][i]!=0 && !resultado.contains(i))lista.add(i);
        }
        // se recorren todas las rutas formadas con los nodos adyacentes al inicial
        for(int nodo: lista) {
            resultado.push(nodo);
            recorrerRutas(nodo, nodoF, resultado);
            resultado.pop();
        }
    }

    // evaluar la longitud de una ruta
    public int evaluar(Stack<Integer> resultado) {
        int  resp = 0;
        int[]   r = new int[resultado.size()];
        int     i = 0;
        for(int x: resultado) r[i++]=x;
        for(i=1; i<r.length; i++) resp+=grafo[r[i]][r[i-1]];
        return resp;
    }

    public static void main(String[] args) {
        Grafo g = new Grafo("abcdef");
        g.agregarRuta('a','b', 5);
        g.agregarRuta('a','e', 3);
        g.agregarRuta('b','e', 6);
        g.agregarRuta('b','f', 9);
        g.agregarRuta('b','c', 10);
        g.agregarRuta('c','d', 15);
        g.agregarRuta('c','f', 9);
        g.agregarRuta('d','e', 1);
        g.agregarRuta('d','f', 2);
        g.agregarRuta('e','f', 12);
        char inicio = 'a';
        char fin    = 'd';
        g.encontrarRutaMinimaFuerzaBruta(inicio, fin);
    }
}

14 comentarios:

  1. Excelente, aunque ineficiente.
    Chévere porque esta es la base para entender protocolos de enrutamiento.
    Gracia por el aporte!!
    WFZ.

    ResponderBorrar
  2. Muchas gracias, próximamente estaré subiendo el código utilizando otras estrategias de solución.

    ResponderBorrar
  3. Anónimo2:13 p.m.

    Me gustaria ver el grafo

    ResponderBorrar
  4. Anónimo10:54 p.m.

    It's really very complex in this busy life to listen news on TV, so I simply use the web for that purpose, and get the newest news.

    Visit my web page Cityadslive.com
    Also see my site > V2 Cigs Reviews

    ResponderBorrar
  5. Anónimo10:03 p.m.

    Нi, just wanted tο sау, I likeԁ thiѕ
    post. It ωas inѕpіrіng.
    Кееρ on pοsting!


    Feеl free to vіsit mу web blog - please click the up coming website Page

    ResponderBorrar
  6. Anónimo9:06 a.m.

    Great article, totally what I nеeԁed.

    My ωeb рage Piratpartiet.Se

    ResponderBorrar
  7. Anónimo12:32 p.m.

    Aw, this was a гeally good poѕt.
    Spendіng some tіmе and аctual effοrt to generate a reallу good аrtiсle… but what can I sаy… I hesitatе a whole lot and dοn't manage to get anything done.

    my web-site; V2 Cig Review

    ResponderBorrar
  8. Anónimo3:13 p.m.

    Great goods frоm yоu, mаn. I have
    bear in mind youг stuff prior to and you're simply too magnificent. I actually like what you've received right here, really like what you're saying and the way in which in which you are saying it. You're making it entertaining and уou
    still carе fоr to κeep it smагt.

    I can't wait to learn much more from you. This is really a great site.

    Review my web site ... http://www.internationaltalentgallery.com/

    ResponderBorrar
  9. Anónimo12:50 p.m.

    Thanκѕ for fіnally wгitіng about > "Ruta m�s corta - Soluci�n por fuerza bruta" < Loved it!

    My blog post; reputatіоn managemеnt

    ResponderBorrar
  10. Anónimo10:59 a.m.

    Have you ever considered about adding a little bit more than just your articles?
    I mean, what you say is valuable and all. However imagine if you
    added some great images or video clips to give your posts more, "pop"!

    Your content is excellent but with pics and clips, this blog could undeniably be one of the most beneficial in its niche.

    Awesome blog!

    Also visit my site - die besten mp3 player

    ResponderBorrar
  11. interesante pero si yo quisisera hacer con String los nodos en ves de Char como seria el cambio lo siento por mas que pienso no encuentro la solucion

    ResponderBorrar
  12. Anónimo12:59 a.m.

    También quiero hacerlo con string en vez de Char pero no he sido capaz...

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...