Eine neue Methode, um komplexe Probleme zu lösen

Viele praktische Organisationsprobleme (unter anderem der Fahrzeugverkehr in Großstädten, die Erkennung eines Geräuschsignals oder physikalische Probleme) fordern die optimale Bestimmung von Variabeln des Problems, mit Berücksichtigung von Zwangsbedingungen. In einfachen Fällen kann man diese Probleme manuell oder mit einem Computer lösen. Wächst die Zahl der Variabeln jedoch (z.B. die Anzahl der Fahrzeuge in einem Verkehrsoptimierungsproblem), kann es passieren, dass die nötige Zeit, um das Problem zu lösen, exponentiell mit der Zahl der Variabel wächst. Man spricht dann von komplexen Problemen, und die gewohnten Optimierungsmethoden werden unbrauchbar.

Ein Forscher des CNRS schlägt eine neue Methode vor, um diese komplexen Probleme zu lösen. Diese Methode besteht aus sogenannten Algorithmen zur „Nachrichtenübertragung“, mit deren Hilfe sich Informationen zwischen der Problemvariabel und den Zwangsbedingungen austauschen lassen. Diese Methode führt zu schnellen Lösungen von komplexen Problemen mit Millionen Variabeln und Zwangsbedingungen. Diese Algorithmen sind in sehr verschiedenen Bereichen effizient, wie z.B. in der Kommunikationstheorie (Kodierung von Telefongesprächen und Satellitenübertragungen), der kombinatorischen Optimierung (Logistik, Kalenderoptimierung) oder der statistischen Physik (Studie der ungeordneten Materialien wie Glas).

Es erscheint merkwürdig, dass verschiedene Disziplinen dieselben Konzepte und Methoden anwenden können. Diese Tatsache mag jedoch ein Hinweis darauf sein, dass komplexe Probleme aus anscheinend völlig verschiedenen Bereichen tatsächlich eng miteinander verwandt sind. Ein Patent wurde im Juni 2003 angemeldet.

Kontakt:

Marc Mézard
Laboratoire de physique théorique et modèles
Université Paris-Sud
15 rue Georges Clémenceau, 91405 Orsay cedex
Tel. +33 1 69 15 73 33
Fax +33 1 69 15 65 25
mezard@lptms.u-psud.fr