En el diseño de circuitos electrónicos, a menudo tenemos la necesidad de interconectar un conjunto de pines o pernos por medio de algún tipo de cableado eléctrico, de tal forma que todos estén conectados entre si. Si tenemos un conjunto de $n$ pines, podríamos usar $n-1$ cables para la conexión de cada dos pines. Sin embargo, de todas las conexiones posibles la que utiliza la menor cantidad de cable suele ser la mas deseable.
Nosotros podemos modelar este cableado con un grafo conexo no dirigido $G(V,E)$ donde $V$ es el conjunto de pines y $E$ el conjunto de posibles interconexiones entre pares de pines
Ya que $T$ es acíclico y conecta todos los vértices este debe formar un árbol, el cual llamaremos árbol de expansión y el árbol con peso total mínimo, árbol de mínima expansión.
Nosotros llamaremos el problema de determinar el árbol $T$, problema de árbol de mínima expansión.
Existen dos algoritmos que nos ayudan a resolver este tipo de problemas el algoritmo de Kruskal y el Algoritmo de Prim, cada uno fácilmente puede correr en un tiempo $O(\|E\|lg\|V\|)$ usando binary heaps ordinarios, aunque el algoritmo de Prim puede ser mas rápido si usamos Fibonacci Heaps en un tiempo de $O(\|E\| + \|V\|lg\|V\|)$.
Estos dos algoritmos usan la heurística de optimización llamada estrategia "Greedy". La cual consiste (tomada de Wikipedia, pues me pareció que estaba muy bien explicado) en escoger en cada paso al mejor elemento $x\inC$ posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos $(C\leftarrowC-\{x\})$ y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados $(S\cup \{x\})$ produce una solución factible.
En caso de que así sea, se incluye ese elemento en $S$. Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.
Una vez finalizado el bucle, el algoritmo comprueba si el conjunto $S$es una solución o no, devolviendo el resultado apropiado en cada caso.
Los algoritmos de Kruskal y Prim hacen uso de una regla muy particular y es la regla de encontrar "safe edges", pero antes de empezar a definir que es una "safe edge", veamos algunas definiciones y generalidades.
y para cada arista $(u,v) \in E$ nosotros especificamos un peso $w(u,v)$ que indica el monto de cable necesitado para conectar $u$ a $v$. Nosotros deseamos encontrar un conjunto $T \subseteq E$ acíclico que conecte todos los vértices y cuyo peso total sea el mas mínimo posible.
Nosotros podemos modelar este cableado con un grafo conexo no dirigido $G(V,E)$ donde $V$ es el conjunto de pines y $E$ el conjunto de posibles interconexiones entre pares de pines
Ya que $T$ es acíclico y conecta todos los vértices este debe formar un árbol, el cual llamaremos árbol de expansión y el árbol con peso total mínimo, árbol de mínima expansión.
Nosotros llamaremos el problema de determinar el árbol $T$, problema de árbol de mínima expansión.
Existen dos algoritmos que nos ayudan a resolver este tipo de problemas el algoritmo de Kruskal y el Algoritmo de Prim, cada uno fácilmente puede correr en un tiempo $O(\|E\|lg\|V\|)$ usando binary heaps ordinarios, aunque el algoritmo de Prim puede ser mas rápido si usamos Fibonacci Heaps en un tiempo de $O(\|E\| + \|V\|lg\|V\|)$.
Estos dos algoritmos usan la heurística de optimización llamada estrategia "Greedy". La cual consiste (tomada de Wikipedia, pues me pareció que estaba muy bien explicado) en escoger en cada paso al mejor elemento $x\inC$ posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos $(C\leftarrowC-\{x\})$ y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados $(S\cup \{x\})$ produce una solución factible.
En caso de que así sea, se incluye ese elemento en $S$. Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.
Una vez finalizado el bucle, el algoritmo comprueba si el conjunto $S$es una solución o no, devolviendo el resultado apropiado en cada caso.
Los algoritmos de Kruskal y Prim hacen uso de una regla muy particular y es la regla de encontrar "safe edges", pero antes de empezar a definir que es una "safe edge", veamos algunas definiciones y generalidades.
y para cada arista $(u,v) \in E$ nosotros especificamos un peso $w(u,v)$ que indica el monto de cable necesitado para conectar $u$ a $v$. Nosotros deseamos encontrar un conjunto $T \subseteq E$ acíclico que conecte todos los vértices y cuyo peso total sea el mas mínimo posible.
Un corte $(S,V-S)$ de un grafo no dirigido $G(V,E)$ es una particion de $V$.
Nosotros decimos que una arista $(u,v)$ cruza el corte $(S,V-S)$ si y solo si los extremos están uno en $S$ y el otro en $V-S$
Decimos que un corte $(S,S-V)$ respeta un conjunto $A$ de aristas, si ninguna arista en $A$ cruza el corte.
Una arista ligera es la arista que cruza el corte con menor peso.
Ahora nosotros definimos una "safe edge" como aquella arista mas prometedora, que puede ser adicionada a un conjunto $A$ contenido en un árbol de mínima expansión $T$.
Mas formalmente tenemos el siguiente teorema.
Teorema:
Sea $G(V,E)$ un grafo conexo no dirigido con una función de valor real w definida sobre $E$. Sea $A$ un subconjunto de $E$, contenido en algún árbol de mínima expansión para G, sea $(S,V-S)$ algún corte que respete a $A$ y sea $(u,v)$ una arista ligera que cruza $(S,V-S)$, entonces $(u,v)$ es una "safe edge" para $A$.
Corolario:
Sea $G(V,E)$ un grafo conexo no dirigido con una función de valor real w definida sobre $E$. Sea $A$ un subconjunto de $E$, contenido en algún árbol de mínima expansión para $G$ y sea $C$ un componente conexo (árbol) en el bosque $G_{A}(V,A)$. Si $(u,v)$ es una arista ligera que conecta $C$ con algun otro componente en $G_{A}$, entonces $(u,v)$ es una "safe edge" para $A$.
En forma genérica el algoritmo se basa en lo siguiente:
Kruskal y Prim son elaboraciones de este algoritmo, sin embargo cada uno tiene su propia forma de determinar una "safe edge" enunciada en la linea 3 del GENERIC-MST.
En Kruskal (que es el que describiremos a continuación) el conjunto A es un bosque y la "safeedge" que es añadida a A es siempre la arista de menor peso que une dos componentes disjuntos del grafo. En el algoritmo de Prim el conjunto A forma un solo árbol y la "safe edge" que es añadida a A es siempre la arista de menor peso que conecta el árbol a un vértice que no esta en el árbol.
Algoritmo de Kruskal.
Como habíamos mencionado el algoritmo de Kruskal se basa directamente en el algoritmo genérico del minimun spanning tree . Kruskal para encontrar una "safe edge" se basa en el corolario antes mencionado, este encuentra la "safe edge" a adicionar en el bosque de aumento $A$ buscando todas las aristas que conecten dos arboles en el bosque, tomando la de menor peso. Sin perdida de generalidad sea $C_{1}$y $C_{2}$ dos arboles conectados por una arista $(u,v)$, si $(u,v)$ es la arista de menor peso esta debe ser una arista ligera que conecta $C_{1}$ a algún árbol, y por el corolario esto implica que (u,v) es una "safe edge" para C1. Kruskal es un algoritmo "greedy" porque en cada paso este añade a al árbol la arista de menor peso posible.
A continuación mostremos una implementación sencilla del mismo. Esta implementación hace uso de las funciones de la estructura de datos de conjuntos disjuntos, como por ejemplo la función FIND-SET() y UNION(). En esta estructura cada conjunto contiene un elemento que lo representa. La operación FIND-SET(u) retorna el elemento representativo del conjunto que contiene a u, mientras que UNION(u,v) une los conjuntos de los cuales u y v son representantes y destruye a cada conjunto, dejando como representante a alguno de los dos u o v del nuevo conjunto unido, en este caso tomaremos como representante a v.
Ejemplo: Hallar el árbol de mínima expansión en el siguiente grafo.
Una manera eficiente de correr nuestro algoritmo es haciendo una tabla, donde se muestre el orden no decreciente de las aristas, ya saben que se hace según el peso de la misma, y vamos observando que sucede en cada paso con la $UNION(u,v)$ y nuestro conjunto $A$, como se muestra a continuación:
Finalmente el conjunto $A$ es retornado dando como resultado el siguiente árbol de mínima expasión:
$A=\{(h,g),(c,i),(f,g),(a,b),(c,f),(a,h),(d,e)\}$
Hasta entonces espero les haya gustado...
0 comentarios:
Publicar un comentario