Regensburg 1998 – scientific programme

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 Schneider¹, Ingo Morgenstern¹, Andreas Beckmann¹, Ralf Kinder¹, Markus Puchta¹, Martin Schmid¹ und Johannes Maria Singer² — ¹Fakultät Physik, Universität Regensburg, Universitätsstr. 31, D-93053 Regensburg — ²Physikinstitut, 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