Content deleted Content added
Open access status updates in citations with OAbot #oabot |
m CE sentence case |
||
Line 43:
[[Simulated annealing]], when used with a logarithmic cooling schedule, has been proven to find the global optimum of any optimization problem. However, such a cooling schedule results in entirely impractical runtimes, and is never used.<ref>{{cite journal |last1=Liang |first1=Faming |first2=Yichen |last2=Cheng |first3=Guang |last3=Lin |title=Simulated stochastic approximation annealing for global optimization with a square-root cooling schedule |journal=Journal of the American Statistical Association |volume=109 |issue=506 |year=2014 |pages=847–863|doi=10.1080/01621459.2013.872993 |s2cid=123410795 }}</ref> However, knowing this ideal algorithm exists has led to practical variants that are able to find very good (though not provably optimal) solutions to complex optimization problems.<ref>{{cite journal |author= Ingber, Lester |title=Simulated annealing: Practice versus theory |journal=Mathematical and Computer Modelling |volume=18 |issue=11 |year=1993 |pages=29–57|doi=10.1016/0895-7177(93)90204-C |doi-access=free |citeseerx=10.1.1.15.1046 }}</ref>
=== Minimum
The [[expected linear time MST algorithm]] is able to discover the [[minimum spanning tree]] of a graph in <math>O(m + n)</math>, where <math>m</math> is the number of edges and <math>n</math> is the number of nodes of the graph.<ref>{{Cite journal |last1=Karger |first1=David R. |last2=Klein |first2=Philip N. |last3=Tarjan |first3=Robert E. |date=1995-03-01 |title=A randomized linear-time algorithm to find minimum spanning trees |journal=Journal of the ACM |volume=42 |issue=2 |pages=321–328 |doi=10.1145/201019.201022 |issn=0004-5411|doi-access=free }}</ref> However, the constant factor that is hidden by the [[Big O notation]] is huge enough to make the algorithm impractical. An implementation is publicly available<ref>{{Cite web |last=Thiesen |first=Francisco |title=A C++ implementation for an Expected Linear-Time Minimum Spanning Tree Algorithm(Karger-Klein-Tarjan + Hagerup Minimum Spanning Tree Verification as a sub-routine) |url=https://github.com/FranciscoThiesen/karger-klein-tarjan |access-date=2022-11-19 |website=[[GitHub]]}}</ref> and given the experimentally estimated implementation constants, it would only be faster than [[Borůvka's algorithm]] for graphs in which <math>m + n > 9 \cdot 10^{151}</math>.<ref>{{Cite web |last=Geiman Thiesen |first=Francisco |title=Expected Linear-Time Minimum Spanning Trees |url=https://franciscothiesen.github.io/Linear-Time-MST/ |access-date=2022-11-13 |website=franciscothiesen.github.io}}</ref>
| |||