Sie sind hier
E-Book

Kaktus-Repräsentation der minimalen Schnitte eines Graphen und Anwendung im Branch-and-Cut Ansatz für das TSP

AutorKlaus Wenger
Verlagdiplom.de
Erscheinungsjahr2004
Seitenanzahl244 Seiten
ISBN9783832478032
FormatPDF
Kopierschutzkein Kopierschutz
GerätePC/MAC/eReader/Tablet
Preis38,00 EUR
Inhaltsangabe:Zusammenfassung: Diese Diplomarbeit leistet einen Beitrag zur algorithmischen Lösung des Problems des Handelsreisenden (Traveling Salesman Problem, TSP). Der Handelsreisende sucht eine kürzeste Rundreise durch eine fest gegebene Menge von Städten, wobei die Weglängen zwischen je zwei Städten bekannt sind. Die Anwendungen des TSPs gehen weit über Fahrtroutenoptimierung hinaus. Das erfolgreichste Verfahren zur exakten Lösung NP-schwerer diskreter oder kombinatorischer Optimierungsprobleme wie dem TSP ist Branch-and-Cut. Dieses Verfahren ist eine Kombination aus Branch-and-Bound und dem Schnittebenenverfahren. Die Diplomarbeit stellt ein Verfahren vor in dem Schnittebenen aus linearen Beschreibungen niedrigdimensionaler TSP Polytope gewonnen werden. Pionierarbeit in dieser Richtung wurde Mitte der 90er Jahre von Christof und Reinelt geleistet. Das hier vorgeschlagene Verfahren unterscheidet sich von diesen ersten Experimenten vor allem durch die Art der Dimensionsreduktion. Hierzu wird die sogenannte Kaktus-Darstellung aller minimalen Schnitte von TSP Trägergraphen, welche innerhalb des Branch-and-Cut Verfahrens für das TSP anfallen, verwendet. Ein Schnitt in einem Graph ist eine nichtleere echte Teilmenge der Knotenmenge. Das Gewicht eines Schnitts ist die Summe der Gewichte der Kanten mit genau einem Endknoten im Schnitt. Ein minimaler Schnitt ist ein Schnitt minimalen Gewichts. Die Kaktus-Darstellung der Menge aller minimalen Schnitte eines Graphen kann als Datenstruktur angesehen werden welche die Inklusions- und Überlappungsstruktur der Menge der minimalen Schnitte unter Verwendung von wenig Speicher widerspiegelt. Sie wurde erstmals Mitte der 70er Jahre von Dinitz et al. vorgeschlagen. Die Kaktus-Datenstruktur wird verwendet, um TSP Trägergraphen aussichtsreich zu schrumpfen. Für kleine geschrumpfte Graphen werden Schnittebenen in den linearen Beschreibungen von kleinen TSP Polytopen mittels des quadratischen Zuordnungsproblems (QAP) gesucht und eventuell geliftet. Im Zuge der Arbeit wurde der Kaktus-Konstruktionsalgorithmus von Fleischer (1999) implementiert. Dies ist als sehr seltene Implementierung eines derartigen Algorithmus anzusehen. Es werden umfangreiche Rechenresultate präsentiert. Das vorgestellte Verfahren zur Berechnung von Schnittebenen hat folgende Ähnlichkeit mit dem von Applegate et al. (1998,2001,2003) vorgeschlagenen im Concorde System enthaltenen „local cut“ Verfahren: In beiden Verfahren [...]

Kaufen Sie hier:

Horizontale Tabs

Blick ins Buch

Weitere E-Books zum Thema: Mathematik - Algorithmik - Arithmetik

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Operations Research

E-Book Operations Research
Linearoptimierung Format: PDF

Linearoptimierung wird als mathematische Methode innerhalb des Operations Research bei der Mengenplanung für Absatz und Produktion sowie für Transport-, Netzfluss- oder Maschinenbelegungs-Probleme…

Gewöhnliche Differenzialgleichungen

E-Book Gewöhnliche Differenzialgleichungen
Differenzialgleichungen in Theorie und Praxis Format: PDF

Im Anschluss an Vorlesungen in Analysis und Linearer Algebra folgen an nahezu allen technischen und wirtschaftswissenschaftlich orientierten Studiengängen an Hochschulen und Universitäten als eine…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Mathematik für Informatiker

E-Book Mathematik für Informatiker
Format: PDF

Die Informatik entwickelt sich in einer unglaublichen Geschwindigkeit. Häufig ist die Mathematik Grundlage von Neuerungen. Deshalb ist sie unverzichtbares Werkzeug jedes Informatikers und Pflichtfach…

Weitere Zeitschriften

FESTIVAL Christmas

FESTIVAL Christmas

Fachzeitschriften für Weihnachtsartikel, Geschenke, Floristik, Papeterie und vieles mehr! FESTIVAL Christmas: Die erste und einzige internationale Weihnachts-Fachzeitschrift seit 1994 auf dem ...

Arzneimittel Zeitung

Arzneimittel Zeitung

Die Arneimittel Zeitung ist die Zeitung für Entscheider und Mitarbeiter in der Pharmabranche. Sie informiert branchenspezifisch über Gesundheits- und Arzneimittelpolitik, über Unternehmen und ...

Atalanta

Atalanta

Atalanta ist die Zeitschrift der Deutschen Forschungszentrale für Schmetterlingswanderung. Im Atalanta-Magazin werden Themen behandelt wie Wanderfalterforschung, Systematik, Taxonomie und Ökologie. ...

Berufsstart Gehalt

Berufsstart Gehalt

»Berufsstart Gehalt« erscheint jährlich zum Sommersemester im Mai mit einer Auflage von 50.000 Exemplaren und ermöglicht Unternehmen sich bei Studenten und Absolventen mit einer ...

Deutsche Hockey Zeitung

Deutsche Hockey Zeitung

Informiert über das nationale und internationale Hockey. Die Deutsche Hockeyzeitung ist Ihr kompetenter Partner für Ihren Auftritt im Hockeymarkt. Sie ist die einzige bundesweite Hockeyzeitung ...