Diferencia entre revisiones de «Algoritmo de Boruvka»
m |
|||
| Línea 1: | Línea 1: | ||
| − | {{ | + | {{Definición|Nombre=Algoritmo de Boruvka|imagen=Algoritmo_de_Boruvka.png|concepto=Algoritmo para encontrar el Árbol de expansión mínima(MTS) en un grafo ponderado en el que todos sus arcos tienen distinto peso}}<div align="justify">'''Algoritmo de Borůvka''' es un [[Algoritmo]] para encontrar el MST (Árbol de expansión mínima) en un grafo ponderado en el que todos sus arcos tienen distinto peso. |
| − | == Historia | + | == Historia == |
| + | Fue formulado inicialmente por [[Otakar Boruvka]] en [[1926]] quien se dice tuvo que aprender de éste durante la construcción de la red eléctrica de del sur de [[Moravia]].<ref>{{cita libro | apellido = Boruvka | nombre = Otakar | enlaceautor = Otakar Boruvka | año = 1926 | título = O jistém problému minimálním (About a certain minimal problem) | publicación = Práce mor. prírodoved. spol. v Brne III | volumen = 3 | páginas = 37–58 | idioma = Czech, German summary }}</ref><ref>{{cita libro | apellido = Boruvka | nombre = Otakar | enlaceautor = Otakar Boruvka | año = 1926 | título = Príspevek k rešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks) | publicación = Elektronický Obzor | volumen = 15 | páginas = 153–154 | idioma = Czech }}</ref> donde él proporcionó una solución para hallar la distribución más económica a través de una red de una línea de energía. | ||
| − | El | + | El algoritmo fue redescubierto por [[Gustave Choquet|Choquet]] en [[1938]];<ref>{{cita libro | apellido = Choquet | nombre = Gustave | enlaceautor = Gustave Choquet | año = 1938 | título = Étude de certains réseaux de routes | publicación = Comptes-rendus de l’Académie des Sciences | volumen = 206 | páginas = 310–313 | idioma = French }}</ref> de nuevo por [[Kazimierz Florek|Florek]], [[Jan Lukasiewicz|Lukasiewicz]], [[Julian Perkal|Perkal]], [[Hugo Steinhaus|Steinhaus]] y [[Stefan Zubrzycki|Zubrzycki]] en [[1951]]; y de nuevo por [[Sollin]] a principio de la década de [[1960]]. Debido a que [[Sollin]] fue el único de ellos que era científico en computación, este algoritmo es frecuentemente llamado Algoritmo de Sollin. |
| − | + | == Algoritmo == | |
| − | + | El algoritmo de Boruvka obtiene un árbol recubridor mínimo en un grafo | |
| + | G ponderado y conexo (no se admiten ponderaciones negativas). | ||
| − | El algoritmo | + | El algoritmo de Boruvka consiste en elegir desde cada vértice la arista |
| + | de menor peso que sale de él, y así formar al inicio un conjunto de | ||
| + | componentes de vértices unidos por dichas aristas. | ||
| − | + | A partir de entonces en cada paso se busca la arista de menor peso | |
| − | + | entre los vértices de cada componente y un vértice que no lo sea, es decir, | |
| − | + | cada componente se unirá a otra distinta. El algoritmo termina cuando todos los | |
| − | + | vértices del grafo pertenecen a la misma componente. | |
| − | + | ||
| − | + | A este algoritmo también se le denomina "el algoritmo de las burbujas". | |
| − | + | El grafo se cubre por una colección de burbujas y en cada paso cada burbuja | |
| − | + | se adhiere a su burbuja más cercana. | |
| − | + | ||
| − | + | ES un algoritmo con una velocidad de convergência (o resolución) bastante rápida siendo ideal para implementación en ordenadores paralelos ya que la Minimum Spanning Tree de cada uno de los subgrafos puede ser calculada en una máquina diferente. | |
| + | |||
| + | Este algoritmo es recursivo y sólo termina cuando existe sólo un vértice. | ||
| + | |||
| + | El algoritmo de Baruvka comprende los siguientes pasos: | ||
| + | |||
| + | #- para cada vértice escoger su arco con peso mínimo. De este paso podrán resultar varios subgrafos. | ||
| + | #- caso el paso 1 dé origen la grafos no conectados, considérese cada subgrafo generado en el paso anterior como un vértice del grafo final. Estos vértices del grafo final contendrán los vértices de cada umdos subgrafos generados en el paso 1. Para cada uno de los subgrafos generados ejecútese de nuevo el paso 1 (recursividade). En este momento se puede, si existan varias máquinas diferentes, correr este algoritmo en las varias máquinas siendo que cada máquina irá a tener assignada a sí uno de los subgrafos generados en el paso 1 (este tipo de distribución de procesamiento es más conocido como Single Instruction Multiple Data ya que cada máquina va a ejecutar las mismas instrucciones pero sobre un conjunto de datos diferentes. | ||
| + | #- Cuando sea encontrada a Minimum Spanning Tree para cada uno de los grafos generar un nuevo grafo donde cada uno vértices de este grafo es uno de los subgrafos. El objetivo ahora será volver a ejecutar los pasos 1 a 3 hasta que existan sólo 2 vértices y un único arco. | ||
== Complejidad == | == Complejidad == | ||
| Línea 32: | Línea 44: | ||
El algoritmo más rápido para hallar el árbol de recubrimiento mínimo aleatorio está basado en parte en el algoritmo de Boruvka gracias a [[Karger]], [[Klein]] y [[Tarjan]] y se obtiene una complejidad O(E). | El algoritmo más rápido para hallar el árbol de recubrimiento mínimo aleatorio está basado en parte en el algoritmo de Boruvka gracias a [[Karger]], [[Klein]] y [[Tarjan]] y se obtiene una complejidad O(E). | ||
| − | El mejor [[Algoritmo]] (determinista) conocido para encontrar el | + | El mejor [[Algoritmo]] (determinista) conocido para encontrar el Árbol mínimo de recubrimiento de [[Bernard Chazelle]] está también basado en parte en el Algoritmo de Boruvka y tiene complejidad temporal O(Ealfa(V)), donde alfa es la inversa de la [[Función de Ackermann]]. Estos algoritmos aleatorios y deterministas combinan pasos del Algoritmo de Boruvka reduciendo el numero de nodos que quedan por conectar, con pasos de diferente tipo que reduzcan el numero de arcos entre cada par de nodos. |
| − | |||
== Referencia == | == Referencia == | ||
| + | {{listaref}} | ||
| − | + | ==Fuentes== | |
| − | + | *[http://es.wikilingue.com/pt/Algoritmo_de_Boruvka Algoritmo de Boruvka] | |
| + | *[http://es.wikipedia.org/wiki/Algoritmo_de_Boruvka Algoritmo de Boruvka - Wikipedia] | ||
| + | *[http://www.scribd.com/doc/41011030/Algoritmos-De-Grafos Algoritmos De Grafos] | ||
| + | </div> | ||
[[Category:Algoritmos]] | [[Category:Algoritmos]] | ||
Revisión del 15:26 15 nov 2010
| ||||||
Historia
Fue formulado inicialmente por Otakar Boruvka en 1926 quien se dice tuvo que aprender de éste durante la construcción de la red eléctrica de del sur de Moravia.[1][2] donde él proporcionó una solución para hallar la distribución más económica a través de una red de una línea de energía.
El algoritmo fue redescubierto por Choquet en 1938;[3] de nuevo por Florek, Lukasiewicz, Perkal, Steinhaus y Zubrzycki en 1951; y de nuevo por Sollin a principio de la década de 1960. Debido a que Sollin fue el único de ellos que era científico en computación, este algoritmo es frecuentemente llamado Algoritmo de Sollin.
Algoritmo
El algoritmo de Boruvka obtiene un árbol recubridor mínimo en un grafo G ponderado y conexo (no se admiten ponderaciones negativas).
El algoritmo de Boruvka consiste en elegir desde cada vértice la arista de menor peso que sale de él, y así formar al inicio un conjunto de componentes de vértices unidos por dichas aristas.
A partir de entonces en cada paso se busca la arista de menor peso entre los vértices de cada componente y un vértice que no lo sea, es decir, cada componente se unirá a otra distinta. El algoritmo termina cuando todos los vértices del grafo pertenecen a la misma componente.
A este algoritmo también se le denomina "el algoritmo de las burbujas". El grafo se cubre por una colección de burbujas y en cada paso cada burbuja se adhiere a su burbuja más cercana.
ES un algoritmo con una velocidad de convergência (o resolución) bastante rápida siendo ideal para implementación en ordenadores paralelos ya que la Minimum Spanning Tree de cada uno de los subgrafos puede ser calculada en una máquina diferente.
Este algoritmo es recursivo y sólo termina cuando existe sólo un vértice.
El algoritmo de Baruvka comprende los siguientes pasos:
- - para cada vértice escoger su arco con peso mínimo. De este paso podrán resultar varios subgrafos.
- - caso el paso 1 dé origen la grafos no conectados, considérese cada subgrafo generado en el paso anterior como un vértice del grafo final. Estos vértices del grafo final contendrán los vértices de cada umdos subgrafos generados en el paso 1. Para cada uno de los subgrafos generados ejecútese de nuevo el paso 1 (recursividade). En este momento se puede, si existan varias máquinas diferentes, correr este algoritmo en las varias máquinas siendo que cada máquina irá a tener assignada a sí uno de los subgrafos generados en el paso 1 (este tipo de distribución de procesamiento es más conocido como Single Instruction Multiple Data ya que cada máquina va a ejecutar las mismas instrucciones pero sobre un conjunto de datos diferentes.
- - Cuando sea encontrada a Minimum Spanning Tree para cada uno de los grafos generar un nuevo grafo donde cada uno vértices de este grafo es uno de los subgrafos. El objetivo ahora será volver a ejecutar los pasos 1 a 3 hasta que existan sólo 2 vértices y un único arco.
Complejidad
Con el Algoritmo de Boruvka se puede obtener una Complejidad de O(log V) iteraciones en el bucle externo antes de terminar, y por lo tanto su Complejidad temporal es O(ElogV), donde E es el número de arcos, y V es el número de vértices de G. En Grafos planos puede implementarse para ejecutarse en tiempo lineal, eliminando los arcos de menor peso entre cada par de nodos después de cada etapa del algoritmo.
Otros algoritmos
Entre otros Algoritmos para este problema se incluyen el Algoritmo de Prim (realmente descubierto por Vojtech Jarnik) y el Algoritmo de Kruskal. Algoritmos más rápidos pueden ser obtenidos combinando el Algoritmo de Prim con el Algoritmo de Boruvka.
El algoritmo más rápido para hallar el árbol de recubrimiento mínimo aleatorio está basado en parte en el algoritmo de Boruvka gracias a Karger, Klein y Tarjan y se obtiene una complejidad O(E).
El mejor Algoritmo (determinista) conocido para encontrar el Árbol mínimo de recubrimiento de Bernard Chazelle está también basado en parte en el Algoritmo de Boruvka y tiene complejidad temporal O(Ealfa(V)), donde alfa es la inversa de la Función de Ackermann. Estos algoritmos aleatorios y deterministas combinan pasos del Algoritmo de Boruvka reduciendo el numero de nodos que quedan por conectar, con pasos de diferente tipo que reduzcan el numero de arcos entre cada par de nodos.
Referencia
- ↑ Boruvka, Otakar (1926). págs. 37–58. Práce mor. prírodoved. spol. v Brne III.
- ↑ Boruvka, Otakar (1926). págs. 153–154. Elektronický Obzor.
- ↑ Choquet, Gustave (1938). págs. 310–313. Comptes-rendus de l’Académie des Sciences.
