Proyecto 2: Árbol de expansión mínima

El problema que yo elegí es: Árbol de expansión mínima o minimum spanning tree (MST)

Objetivo:

Se pretende a partir de un grafo conexo, construir un árbol o subgrafo sin ciclos,  conteniendo todos los vértices del grafo inicial y con la suma de distancias o pesos mínimos posibles. Es decir, buscamos la expansión mínima.

Aplicaciones:

La aplicación de estos problemas se ubica en las redes de comunicación eléctrica, telefónica, carretera, ferroviaria, aérea, marítima, etc. En donde los nodos representan un consumo eléctrico, teléfonos aeropuertos, computadoras,etc

En sistemas distribuidos, interpretación de datos climatológicos, visión artificial, análisis de imágenes, extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros).

Ejemplo, si la compañía de televisión por cable desea instalar en un vecindario sus cables pero estos solamente pueden recorrer por patrones o caminos específicos, seria útil saber cuales caminos son los mas cortos para así ahorrar la mayor cantidad de cable posible.

Otra aplicación es la de las redes de telecomunicación para optimizar las distancias recorridas y asi mismo el material utilizado. Una similar a esta última es utilizada en redes de información entre servidores y computadoras cliente, para disminuir la distancia, aumentar la velocidad de transmisión de información y reducir los costos.

Otra aplicación mas, aunque menos obvia es que el árbol de expansión  total mínima puede ser usado como solución aproximada al problema del viajante de comercio (traveling salesman problem), recuerde que encontrar la solución óptima a este problema es NP-Hard.

Representación:

Nuestro grafo tiene un numero de vértices, así como ramas o conexiones entre estos vértices, además tiene un numero representante de la distancia o expansión entre ambos vértices. Matemáticamente se expresa G(V, E) donde V = (v1, v2, … vn ) es un conjunto finito de vértices (nodos) y E = Eij en un conjunto finito de enlaces que representan la conexión entre los terminales o estaciones. Cada enlace tiene un número positivo real asociado denotado por W = Wij representando distancia, costo, etc.

http://www.people.vcu.edu/~gasmerom/MAT131/mst.html

Definido matemáticamente:

Ejemplo de instancia y solución optima:

El tránsito de Rusia esta planificando la construcción de una línea de sistemas de transito que conecte 7 zonas principales de la ciudad. (A, B, C, D, E, F, G). Donde los kilómetros entre ellas se representan son un numero en el arista correspondiente. Cada kilómetro de construcción le costara al tránsito 4 millones.

El transito desea acortar la distancia de traslación entre las 7 zonas pero asegurando no gastar demasiado del presupuesto. Es decir, desean optimizar la construcción por kilómetro recorrido.

Esto se ilustra como:

Teniendo en cuenta las distancias entre las zonas, se puede resolver de la siguiente manera.

	AD y CE son las aristas mas cortas, con peso 5, y AD se ha elegido arbitrariamente, por tanto se resalta.
	Sin embargo, ahora es CE la arista mas pequeña que no forma ciclos, con distancia 5, por lo que se resalta como segunda arista.
	La siguiente arista, DF con distancia 6, ha sido resaltada utilizando el mismo método.
	La siguientes aristas mas pequeñas son AB y BE, ambas con distancia 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.
	El proceso continúa marcando las aristas, BE con distancia 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE), DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).
	Finalmente, el proceso termina con la arista EG de distancia 9, y se ha encontrado el árbol de expansión mínima.

El total de kilómetros obtenidos son 39 y el costo resultante es 156 millones.

Qué pasaría si se hubiera construido en lugar de la distancia BE, la distancia BC?

Respuesta: El costo aumentaría a 160 millones.

Formular un problema de decisión correspondiente:

Existe más de una forma de resolver la expansión mínima de un grafo G(V, E)?

Si, existen 4 algoritmos para su solución, estos son:

1.       Algoritmo de Kruskal

2.       Algoritmo de Prims

3.       Algoritmo de Boruvka

Con complejidad O(E log n)

4.       Algoritmo de Edmond

Con complejidad O(E log n) para un árbol esparcido y O(n²) para uno denso.

Este problema fue resuelto independientemente por Dijkstra (1959), Kruskal (1956) y Prim (1957) y la existencia de un algoritmo polinomial (que todos ellos demostraron) es una grata sorpresa, debido a que un grafo con N vértices puede llegar a contener N^N-2 subárboles T*.

La complejidad asintótica del algoritmo

El algoritmo de solución es NP duro?

Presentar un algoritmo para el problema de optimización

Algoritmo de Prim

Los pasos son:

1.      Se marca un nodo cualquiera, será el nodo de partida.

2.      Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente, y marcamos el otro nodo en el que incide.

3.      Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.

4.      El proceso termina cuando tenemos todos los nodos del grafo marcados.

Ejemplo: Determinar el árbol de mínima expansión para el siguiente grafo:

·         Siguiendo el algoritmo de Prim, tenemos:

o    Elegimos, por ejemplo, el nodo 1 y lo marcamos.

o    Elegimos la arista con menor valor incidente en 1, la (1, 3) = 1 la marcamos y marcamos el otro nodo en el que incide, el 3.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (1, 2) = 3 la marcamos y marcamos el nodo no marcado, el 2.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (2, 5) = 5 la marcamos y marcamos el nodo no marcado, el 5.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 6) = 1 la marcamos y marcamos el nodo no marcado, el 6.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 7) = 2 la marcamos y marcamos el nodo no marcado, el 7.

o    Elegimos la arista con menor valor incidente en un nodo marcado y otro que no lo esté, la (5, 4) = 6 la marcamos y marcamos el nodo no marcado, el 4.

o    FIN. Finalizamos dado que tenemos marcados los 7 nodos del grafo.

o    Por tanto el árbol de mínima expansión resultante sería:

Aquí hay un pseudocódigo de Prim para resolverlo, y otro ejemplo de ejecución.

   JARNIK (Grafo G, nodo_fuente s)

       // Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL

       // Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas del grafo

       por cada u en V[G] hacer

           distancia[u] = INFINITO

           padre[u] = NULL

           Añadir(cola,<u,distancia[u]>)

       distancia[s]=0

       mientras cola != 0 do

           // OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.

           u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.

           por cada v adyacente a 'u' hacer

               si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces

                   padre[v] = u

                   distancia[v] = peso(u, v)

                   Actualizar(cola,<v,distancia[v]>)

Imagen	Descripción	No visto	En el grafo	En el árbol
	Este es el grafo ponderado de partida. No es un árbol ya que requiere que no haya circuitos y en este grafo los hay. Los números cerca de las aristas indican el peso. Ninguna de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida.	C, G	A, B, E, F	D
	El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. De estos, 5 es el valor más pequeño, así que marcamos la arista DA.	C, G	B, E, F	A, D
	El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 es el valor más pequeño, así que marcamos el vértice F y a la arista DF.	C	B, E, G	A, D, F
	El algoritmo continua. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado.	null	C, E, G	A, D, F, B
	Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol.	null	C, G	A, D, F, B, E
	Sólo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se marca con el arco EC. El arco BC también se marca con rojo.	null	G	A, D, F, B, E, C
	G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39.	null	null	A, D, F, B, E, C, G

Finalmente les dejo un link para que vean como el algoritmo de Prim resuelve el problema paso a paso: Applet de simulacion de Prim

Bibliografía:

http://www.tcs.tifr.res.in/~prahladh/teaching/2009-10/limits/lectures/lec01.pdf

http://www.lab.dit.upm.es/~lprg/material/apuntes/o/index.html

http://www.people.vcu.edu/~gasmerom/MAT131/mst.html

http://www.ics.uci.edu/~eppstein/161/960206.html

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml

http://es.wikipedia.org/wiki/Algoritmo_de_Prim

http://lear.inforg.uniovi.es/ioperativa/TutorialGrafos/minimaexp/minimaexp.htm

http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal

http://en.wikipedia.org/wiki/Kruskal%27s_algorithm 

http://personales.upv.es/arodrigu/grafos/Kruskal.htm

http://www.mitecnologico.com/Main/ArbolesGeneradoresMinimales

http://docencia.udea.edu.co/regionalizacion/teoriaderedes/minimos.html

http://sisbib.unmsm.edu.pe/bibvirtual/publicaciones/indata/v05_n2/algorit_evo.htm

http://dns.uls.cl/~ej/fit_2009/teo_fit_2009/Lect_2009/Fit_1998/el.htm

http://www.algorithm-code.com/wiki/Prim%27s_algorithm

http://148.202.148.5/cursos/mt260/matedisc/unidad5/tem5.7.htm

Proyecto 1: #2 Buscar una buena ruta

Objetivo: Buscar una buena ruta de un lugar a otro en un mapa.

Pareja de proyecto: Alan http://twowolvescorp.blogspot.com/

Este es el pseudocodigo:

#include < stdio.h >

main()

{

#define si 1, no 0;

/*Se declaran algunas variables, i, j y k serán índices para evaluar repeticiones.*/

double ndir, i, j, k;

/*Estas son matrices que contienen palabras.*/

char direcciones[ ][ ], caminos[ ];

/*Y acá se encuentran algunos números de precisión.*/

long float distancias[ ][ ], suma, menor, menoralt[ ];

printf(“Este programa calcula la distancia mas corta de uno o varios trayectos \nque se puede recorrer en un mapa, desde una dirección inicial a una final.”);

printf(“Cuantas direcciones son?: ”)

scanf(“%ld”, &ndir);

/*Se define la primera matriz nxn.*/

direcciones[ndir][ndir];

/*Ahora se van llenando los espacios de la primera fila de la matriz.*/

while (i<=ndir)

{

printf(“Direccion %d?: ”, i);

scanf(“%s”, &direcciones[i][1]);

i++;

}

printf(“Asignar la conexión o unión entre las direcciones:”)

/*Se sigue llenando la matriz pero ahora completamente, las conexiones de cada camino se escriben inmediatamente debajo de la fila en cada columna.*/

for (i=1; i<=ndir; i++)

{

printf(“La direccion %s, se conecta con,”, direcciones[i][1]);

for (j=2; j<=ndir; j++)

{

/*Este while crea un lista de las uniones que puedes elegir para cada dirección.*/

while (i<=ndir)

{

printf(“\n%ld. %s”, i, direcciones[i][1]);

i++;

}

i-=i+1;

printf(“la dirección(numero): ”);

scanf(“%ld”, &opcion);

if (opcion=1)

{

/*Seria ir a la misma dirección, carece de sentido.*/

printf(“Opción invalida, elegir otra...”);

}

/*El switch va llenando la matriz según la el numero elegido, en su posición correspondiente.*/

switch (opcion)

{

case 2:

direcciones[i][j]=direcciones[i][1];

break;

case 3:

direcciones[i][j+1]=direcciones[i][1];

break;

continue case ndir:

direcciones[i][j+2]=direcciones[i][1];

break;

}

printf(“Se conecta además con otra dirección?: ”);

scanf(“%s”, &eleccion);

if (eleccion==1)

{

j++

/*Regreso a la linea 53 para seguir llenando la matriz en la siguiente columna.*/

return line 53;

}

/* Esto asegura no repetir las preguntas de uniones de las direcciones.*/

j++;

}

}

printf(“Asignar las distancias entre las direcciones:”);

/*Se define otra matriz nxn para las distancias (numero float).*/

distancias[ndir+1][ndir+1];

for ((i=1; i<=ndir; i++)&&(j=2; j<=ndir; j++))

{

/*Dice que si existe algo definido en la posición [i][j] de la matriz “direcciones”, asignara el numero 1 en la matriz de “distancias” en su posición equivalente.*/

if (exists(direccion[i][j])==1)

{

distancias[i][j]=1;

}

}

for (i=1; i<=ndir; i++)

{

for (j=2; j<=ndir; j++)

{

/*Y luego dice que si existe un 1 en las posiciones de la matriz “distancias”, te pedirá ingresar la distancia.*/

if (exists(direcciones[i][j])==1)

{

printf(“Cual es la distancia %s-%s?: ”, direcciones[i][1],direcciones[i][j])

scanf(“%lf”, distancias[i][j]);

}

/* Esto (j++) es para que no se repitan las preguntas de distancias iguales pero en diferente sentido. Es decir distancia=AB=BA*/

j++

}

}

printf(“Cual es la dirección inicial?: ”)

scanf(“%s”, &inicio);

printf(“Y cual es la dirección final o de llegada?: ”)

scanf(“%s”, &fin);

/*Esta es la parte que es un poco confusa porque todavía no sabemos como hacer diagramas de árbol.*/

generate diagram (caminos[])

/*Aquí solo le decimos que nos genere k-caminos posibles a partir de la matriz de las direcciones y que vaya sumando las distancias.*/

for (k=1; k<=distancias[i][j]; k++)

{

for (j=2; j<=tam(direcciones[i][j]))

{

/*Busca direcciones adyacentes o uniones.*/

search adyacent (direcciones[])

suma= distancias[i][j]+distancias[i][j++]

}

caminos[k]=suma;

suma=0;

}

/*Tomamos el primer numero de los caminos generados y lo comparamos con todos los demás, se le asignara la variable “menor” al menor numero de cada comparación hecha. Se hace esto porque hay veces que resultan 500 caminos diferentes.*/

k=1;

menor= caminos[k];

for (k=2; k<=size(caminos[]); k++)

{

if (menor>caminos[k])

{

menor=caminos[k];

}

else if (menor=caminos[k])

{

/*Menoralt significa menor alternativo, ya que a veces puedes encontrar 2 o mas caminos con la misma distancia.*/

menoralt[i]=caminos[k];

}

}

printf(“El camino mas corto que puede tomar de %s a %s es: %-s con una distancia de: %lf”, inicio, fin, caminos[k], menor);

/*Se comparan los resultados alternativos y se ofrecen en pantalla solo si son iguales al camino mas corto (menor).*/

j= size(menoralt[]);

if (menoralt[j]=menor)

{

for (i<=j; i=1; i- -)

{

while (menor=menoralt[i])

{

printf(“Otra alternativa es: %-s con la misma distancia”, caminos[i]);

}

}

}

getch ();

}

Un ejemplo:

Este es un ejemplo del algoritmo con un mapa simple:

1. Tomemos un mapa cualquiera, en este caso será el estado de Arizona, EU.

Fuente: http://i459.photobucket.com/albums/qq317/pauljorg31/arizona/cities-map-arizona-free.gif

2. Supongamos que deseas ir de Holbrook a Blythe, solo por los caminos resaltados en azul y las ciudades subrayadas con rojo.

3. El programa comienza pidiéndote la cantidad de ciudades o direcciones que existen: 11

Blythe, Needles, Kingman, Williams, Flagstaff, Sedona, Prescott, Wickenburg, Phoenix, Globe y Holbrook.

4. Entonces se define una matriz de 11x11.

5. Llena los espacios de la primera fila como van ingresando los datos.

6. Te pregunta cuales son las conexiones o uniones de la primera dirección (Blythe), en el mapa podemos observar que son Needles, Wickenburg y Phoenix. Y el programa las inserta justo debajo de la primera ciudad:

	i=1	i=2	i=3	i=4	i=5
j=1	Blythe	Needles	Kingman	Williams	…
j=2	Needles	Blythe	…	…	…
j=3	Wickenburg	…	…	…	…
j=4	Phoenix	…	…	…	…

7. Y hace lo mismo con las demás ciudades sin repetir las preguntas.

8. Se define una matriz para las distancias pero es 1 número más grande que la cantidad total de direcciones. Es decir de 12x12.

9. Si existe algún valor sea numérico o alfabético en la matriz de direcciones, se le asigna un 1 a su homologo en la matriz de distancias. Es decir distancias[i+1][j+1].

	Blythe	Needles	Kingman	Williams
Bythe
Needles	1
Kingman		…
Phoenix	1	…	…

10. Después, si existe un 1 en la matriz anterior, se pedirá la distancia de [i][1] a [i][j].

11. Se piden la dirección inicial y la dirección final: Holbrook y Blythe.

12. Comienza a hacer el diagrama de árbol a partir de ambas matrices y asignando los resultados en un arreglo llamado caminos[k].

Aquí se puede apreciar la complejidad del mapa con todos sus caminos posibles.

13. Mas tarde de haber generado todos los caminos[k], compara las distancias obtenidas, es decir cada una de las ramas del diagrama de árbol que terminan en Blythe, nuestro objetivo.

14. Casi por ultimo se determina cual fue el menor de todas las distancias y se ofrece como resultado final. Para fines prácticos nosotros supondremos que el camino mas corto es el que tiene menos direcciones de por medio. Se puede ver en el diagrama que esos caminos son:

Holbrook > Globe > Phoenix > Blythe.

15. Ya por ultimo se ofrecen algunas alternativas:

Otra opción puede ser:

Holbrook > Flagstaff > Williams > Prescott > Wickenburg > Bythe.

La complejidad del programa es aproximadamente NP ya que el diagrama de arbol aumenta exponencialmente conforme los caminos o conecciones entre ciudades aumentan.

Ejercicio 2 - De entero a binario

Aquí esta mi algoritmo en C para convertir un numero entero a un numero binario:

#include < stdio.h >
#include < math.h >
#include < stdlib.h >

main()
{
    int num1, i= 0, opcion;
    double base= pow(2,i);
   
    printf("Escribir un numero entero para convertir a binario: ");
    scanf("%d", &num1);
   
    while (base<=num1)
    {
          printf(" %lf", base);
          i++;
          base= pow(2,i);
    }
    i--;
    printf("\n i=%d\n\n", i);
    base= pow(2,i);
   
    while (num1>0)
    {
    if (base
    {
                  num1-=base;
                  i--;
                  base= pow(2,i);
                  printf("1");
    }
    else if (base>num1)
    {
        i--;
        base= pow(2,i);
        printf("0");
    }
    else if (base=num1)
    {
    num1-=base;
    printf("1");
    while (i>0)
    {
          printf("0");
          i--;
    }
    }
    }

    printf("\n\n.");
    system("pause");
    return 0;
}