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.
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(n2) 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 NN-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:
Entradas
Muy extenso tu reporte. El problema de decisión correspondiente sería: "Dado un grafo ponderado y un número K, ¿existe un árbol de expansión con peso total menor o igual a K?" A este pregunta se puede contestar sí o no y es esta pregunta que pertenece a P en sí, ya que P es una clase de problemas de decisión. Cuando se dice que "MST está en P", refieren a su versión de decisión.
ResponderEliminar