An efficient heuristic algorithm for minimum matching |
| |
Authors: | P Grassberger H Freund |
| |
Institution: | (1) Physics Department, University of Wuppertal, Gauss-Strasse 20, D-5600 Wuppertal 1 |
| |
Abstract: | We give a new heuristic algorithm for minimum matching problems and apply it to the Euclidean problem with random vertices in 2 dimensions. The algorithm is based on simulated annealing and performs in practice faster than previous heuristic algorithms yielding suboptimal solutions of the same good quality. From configurations with up toN=20.000 vertices in the unit square we estimate that the length of a minimum matching scales asymptotically asLN with (=0.3123±0.0016.
Zusammenfassung Wir stellen einen neuen heuristischen Algorithmus für minimale Matching-Probleme vor und wenden diesen auf das euklidische Problem mit zufÄlliger Punkteverteilung in 2 Dimensionen an. Auf Simulated Annealing basierend lÄuft der Algorithmus schneller als frühere heuristische Algorithmen und erreicht dabei suboptimale Lösungen gleich guter QualitÄt. Aus Konfigurationen mit bis zuN=20.000 Punkten im Einheitsquadrat schÄtzen wir, da\ für die LÄnge des minimalen Matchings asymptotischLN mit=0.3123±0.0016 gilt. |
| |
Keywords: | euclidean minimum matching problems heuristic algorithms simulated annealing asymptotic behaviour rate of convergence |
本文献已被 SpringerLink 等数据库收录! |