„Minimális feszítőfa” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
párhuzamosított algoritmusok |
→Algoritmusok: speciális megközelítések |
||
31. sor:
A számítógép-tudomány egyik legrégibb nyitott kérdése, hogy mi a lehető leggyorsabb minimális költségű feszítő fát adó algoritmus. Nyilván van egy lineáris alsó határ, mivel minden költséget meg kell vizsgálni. Ha az élsúlyok egészek, és egy adott korlát alatt vannak, akkor ismertek lineáris polinomiális algoritmusok.<ref>Fredman, M. L. and Willard, D. E. 1994. [http://dx.doi.org/10.1016/S0022-0000(05)80064-9 Trans-dichotomous algorithms for minimum spanning trees and shortest paths]. J. Comput. Syst. Sci. 48, 3 (Jun. 1994), 533–551.</ref> Általában, vannak véletlen algoritmusok, amik várható futási ideje lineáris..<ref>Karger, D. R., Klein, P. N., and Tarjan, R. E. 1995. [http://doi.acm.org/10.1145/201019.201022 A randomized linear-time algorithm to find minimum spanning trees]. J. ACM 42, 2 (Mar. 1995), 321–328.</ref><ref>Pettie, S. and Ramachandran, V. 2002. [http://portal.acm.org/citation.cfm?id=545381.545477&coll=GUIDE&dl=GUIDE&CFID=60207697&CFTOKEN=18906052 Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms]. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, January 06 - 08, 2002). Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 713–722.</ref> De még mindig nyitott kérdés, hogy van-e lineáris idejű determinisztikus algoritmus általános élsúlyokra.<ref>Pettie, S. and Ramachandran, V. 2002. [http://portal.acm.org/citation.cfm?doid=505241.505243 An optimal minimum spanning tree algorithm]. J. ACM 49, 1 (Jan. 2002), 16–34.</ref>
A feladatot párhuzamosított algoritmussal is sikerült megoldani. Lineáris számú processzorral <math>O(\log n)</math> időben található egy minimális költségű feszítő fa.<ref>Chong, K. W., Han, Y., and Lam, T. W. 2001. [http://doi.acm.org/10.1145/375827.375847 Concurrent threads and optimal parallel minimum spanning trees algorithm]. J. ACM 48, 2 (Mar. 2001), 297–323.</ref><ref>Pettie, S. and Ramachandran, V. 2002. [http://dx.doi.org/10.1137/S0097539700371065 A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest]. SIAM J. Comput. 31, 6 (Jun. 2002), 1879–1895.</ref> David A. Bader és Guojing Cong egy 2003-as cikkükben közölt egy párhuzamosított algoritmust, ami 8 processzoron ötször gyorsabb, mint egy optimalizált szekvenciális algoritmus.<ref>Bader, D. A. and Cong, G. 2006. [http://dx.doi.org/10.1016/j.jpdc.2006.06.001 Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs]. J. Parallel Distrib. Comput. 66, 11 (Nov. 2006), 1366–1378.</ref> A Prim- és a Kruskal-algoritmus nem párhuzamosítható, ezért a párhuzamos algoritmusok a Boruvska-algoritmuson
Más speciális algoritmusok nagy, külső táron tárolt gráfokra alkalmasak. Kis gráfokon kétszer-ötször lassabbak, mint a hagyományos algoritmusok<ref>R. Dementiev, P. Sanders, D. Schultes, and J. Sibeyn. [http://citeseer.ist.psu.edu/dementiev04engineering.html Engineering an external memory minimum spanning tree algorithm]. In Proc. 3rd IFIP Intl. Conf. on Theoretical Computer Science, pages 195--208, 2004.</ref>
Ezt írták: „A több merevlemezt megtöltő gráfok feszítő fáinak megtalálása egy teljes éjszakába telik egy PC-n.”
Egy másik megközelítésben a gráf csúcsaiba processzorokat helyezünk, amik csak az élek mentén tudnak kommunikálni. Így is kiszámítható a gráf egy minimális költségű feszítő fája.
==Lásd még==
* [[Gráf]]
| |||