Direkt zum Inhalt

Lexikon der Mathematik: MST-Relaxation

die Relaxation des Travelling-Salesman-Problems, bei der ein minimaler Spannbaum (minimum spanning tree, MST), d. h. ein Baum, der jeden Ort berührt, berechnet wird.

Ein minimaler Spannbaum läßt sich sehr effizient berechnen. Die Kosten eines minimalen Spannbaums bilden eine untere Schranke für die Kosten einer optimalen Rundreise. Somit kann die MST-Relaxation für das Modul der Berechnung einer unteren Schranke in branch-and-bound Algorithmen für das TSP benutzt werden. Diese untere Schranke kann durch die Betrachtung von 1-Bäumen verbessert werden, dies sind Spannbäume mit einer zusätzlichen den Startort berührenden Kante.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos