Bereiche | Tage | Auswahl | Suche | Downloads | Hilfe

DY: Dynamik und Statistische Physik

DY 10: Allgemeine Statistische Physik I

DY 10.3: Vortrag

Dienstag, 18. März 1997, 11:00–11:15, R1

Renormierungsverfahren für kombinatorische Optimierung — •Arnulf Möbius¹ und Michael Schreiber² — ¹Institut für Festkörper- und Werkstofforschung, 01171 Dresden — ²Institut für Physik, Technische Universität Chemnitz-Zwickau, 09107 Chemnitz

Wir stellen ein auf der Renormierungsidee basierendes Monte-Carlo-Verfahren für die näherungsweise Lösung von Problemen der kombinatorischen Optimierung vor. Seine Vorzüge werden am travelling salesman Problem demonstriert. Unser Algorithmus arbeitet so effektiv, daß die exakten Lösungen des Grötschel- und des Padberg-Rinaldi-Problems auf einer modernen Workstation innerhalb ‘vernünftiger’ Rechenzeiten reproduziert werden können.

Gefördert durch das SMWK unter 7541.83-IFW / 502.