MIT-Algorithmus löst "Problem des Handlungsreisenden" schneller MIT-Algorithmus löst "Problem des Handlungsreisenden" schneller - Computerwelt

Computerwelt: Aktuelle IT-News Österreich


MIT-Algorithmus löst "Problem des Handlungsreisenden" schneller

Am MIT (Massechusetts Institute of Technology) haben Mathematiker eine Formel entwickelt, mit der die Zeit reduziert wird, um etwa den besten Weg durch ein Netzwerk zu errechnen.

Beim "Problem des Handlungsreisenden" geht es darum, den optimalen Weg eines Vertreters inklusve Rückkehr zum Ausgangsort zu finden.

Beim "Problem des Handlungsreisenden" geht es darum, den optimalen Weg eines Vertreters inklusve Rückkehr zum Ausgangsort zu finden.

© Spectral-Design - Fotolia.com

Eine Gruppe von US-Forschern hat einen möglicherweise um einiges effizienteren Weg gefunden, um Computern dabei zu helfen, schwierige Optimierungsprobleme zu lösen. Solche Aufgaben werden oft auch als "Problem des Handlungsreisenden" bezeichnet. Dabei geht es darum, den optimalen, kürzesten Weg eines Vertreters inklusve Rückkehr zum Ausgangsort aufzuzeigen. Entsprechende Berechnungen spielen in der Informatik eine große Rolle: Eine Fluggesellschaft kann so etwa den optimalen Einsatz seiner Crew planen, oder Router kalkulieren den schnellsten Weg durch ein komplexes Netzwerk.

Die MIT-Mathematiker unter Leitung von Professor Jonathan Kelner haben nun einen Algorithmus vorgestellt, der solche Probleme effizienter und schneller lösen kann. Vor allem soll er sich "fast linear" skalieren lassen. Bislang stieg die benötigte Rechenleistung im Vergleich zur zunehmenden Komplexität eines Problems wesentlich stärker.

Die Forscher wollen die Formel dieser Tage am Symposium der Association Computing Machinery (ACM) über diskrete Algorithmen (SIAM) vorstellen, das in Portland im US-Bundesstaat Oregon stattfindet. Der Algorithmus hat noch keinen offiziellen Namen und wird derzeit nach den Anfangsbuchstaben des MIT-Teams "Klos Algorithm" genannt.

Bis die ersten Computer aber mit der Klos-Formel umgehen können, wird noch einige Zeit vergehen. "Die bislang veröffentlichte Arbeit konzentriert sich auf die Theorie, und es bleibt noch viel zu tun, um eine funktionierende, gute Implementation des Algorithmus zu erstellen", erklärt Kelner. So werden sich die Forscher zunächst darum bemühen müssen, den Algorithmus zu vereinfachen, bevor sie ihn umsetzen und in einer Software-Bibliothek implementieren können, so dass dieser auch einfach von Dritten verwendet werden kann.

Nicht nur in neue Algorithmen, auch in neue Computer werden große Hoffnungen gesetzt um das "Problem des Handlungsreisenden" rascher zu lösen. So hat etwa eine Studie, die einen Quantencomputer von D-Wave Systems und klassische Computer gegenüberstellt, ergeben, dass der neuartige Rechner bestimmte Aufgaben, die diesem Problem zumindest ähneln, tatsächlich wesentlich effektiver lösen kann. Allerdings ist umstritten, ob D-Waves Rechner wirklich als Quantencomputer im eigentlichen Sinne zu sehen sind.

* Jens Stark ist Redakteur der Schweizer Computerworld.

Diesen Artikel

Bewertung:

Übermittlung Ihrer Stimme...
Noch nicht bewertet. Seien Sie der Erste, der diesen Artikel bewertet!
Klicken Sie auf den Bewertungsbalken, um diesen Artikel zu bewerten.
  Sponsored Links:

IT-News täglich per Newsletter

E-Mail:
Weitere CW-Newsletter

CW Premium Zugang

Whitepaper und Printausgabe lesen.  

kostenlos registrieren

Aktuelle Praxisreports

(c) FotoliaHunderte Berichte über IKT Projekte aus Österreich. Suchen Sie nach Unternehmen oder Lösungen.

Zum Thema

  • eyepin GmbH

    eyepin GmbH Application Service Providing, Auftragsentwicklung für Software, Individual-Softwareentwicklung, Programmierung, Übernahme von Softwareprojekten mehr
  • Anexia

    Anexia Application Service Providing, Auftragsentwicklung für Software, Individual-Softwareentwicklung, RZ-Dienstleistungen, Übernahme von Softwareprojekten, User Helpdesk-Systeme und Hotlines mehr
  • Arrow ECS Internet Security AG

    Arrow ECS Internet Security AG WLAN-Systeme, VPN, Netzwerk-Systeme (LAN, MAN, WAN), Netzwerk-Management, Netzwerk-Diagnose-Systeme, Netzwerk-Betriebssysteme, Office Software,... mehr
  • Matrix42 AG

    Matrix42 AG Mobile Lösungen und Applikationen, Zugangs- und Zutrittskontrolle, Security Audits, Übernahme von Softwareprojekten, Programmierung, IT-Asset- und Lizenzmanagement, IKT-Consulting,... mehr

Hosted by:    Security Monitoring by: