Parts | Days | Selection | Search | Downloads | Help
DY: Dynamik und Statistische Physik
DY 18: POSTER I
DY 18.12: Poster
Monday, March 23, 1998, 14:30–17:30, D
Searching for Backbones für Spingläser und kombinatorische Optimierungsprobleme — •Johannes Schneider1, Ingo Morgenstern1, Andreas Beckmann1, Ralf Kinder1, Markus Puchta1, Martin Schmid1 und Johannes Maria Singer2 — 1Fakultät Physik, Universität Regensburg, Universitätsstr. 31, D-93053 Regensburg — 2Physikinstitut, Universität Zürich, Winterthurerstr. 190, CH-8057 Zürich
Optimale Ergebnisse für das Traveling Salesman Problem lassen sich auf Parallelrechnern erzielen, wenn man ausnützt, daß verschiedene gute Lösungen für ein Problem in vielen Teilen übereinstimmen, wie wir 1995 zeigen konnten [1]. Indem man diese Teilstücke aus dem System eliminiert, kann man die Rechenzeit auf die schwierigen Teile konzentrieren und dadurch verbesserte Lösungen erhalten.
Wie in [1] angekündigt, haben wir nun dieses Searching for Backbones Verfahren auf andere Problemklassen ausgedehnt. Neben Touren- und Produktionsplanungsproblemen betrachten wir insbesondere das Sherrington-Kirkpatrick-Modell für Spingläser.
[1] J. Schneider, Ch. Froschhammer, I. Morgenstern, Th. Husslein, J. M. Singer, Computer Physics Communications 96 (2/3) (1996) 173–188