Das Problem des Handlungsreisenden. Ein Kompendium: Traveling Salesman Problem. A Compendium

ISBN-13: 9783656553168 / Niemiecki / Miękka / 2013 / 50 str.

Kai Pohl

Opis

Bachelorarbeit aus dem Jahr 2013 im Fachbereich Informatik - Wirtschaftsinformatik, Note: 1.3, Leuphana Universitat Luneburg, Veranstaltung: Bachelorarbeit, Sprache: Deutsch, Anmerkungen: Es handelt sich hierbei um eine leicht uberarbeitete Version der Abgabeversion meiner Thesis. Es wurde u.a. der inhaltliche Fehler korrigiert, der zu einer 1.3 und nicht zu einer 1.0 gefuhrt hatte., Abstract: Ein Handlungsreisender soll eine gewisse Anzahl von Kunden in verschiedenen Stadten besuchen, in jeder Stadt einen Kunden, und anschlieend zum Ausgangspunkt zuruckkehren. Doch wie ist diese Reise zu wahlen, sodass der Handlungsreisende den moglichst kurzesten Gesamtweg beschreitet? Diese Fragestellung wird als das Problem des Handlungsreisenden bzw. das Traveling Salesman Problem (kurz TSP) bezeichnet. Diese etwas einfache Beschreibung trifft die Gesamtheit des Problems aber bei weiten nicht. Bei dem Problem des Handlungsreisenden handelt es sich um ein Minimierungsproblem aus dem Bereich der theoretischen Informatik. Genauer gesagt gehort es zu einer sehr wichtigen Klasse der theoretischen Informatik; den sogenannten NP-vollstandigen Problemen, fur die keine effizienten und exakten Losungsverfahren existieren bzw. existieren konnen (unter der Annahme das PNP gilt). Intuitiv kann ein Mensch mit Blick auf eine Karte und einer geringen Anzahl an Stadten, die es fur eine Rundreise zusammenzufuhren gilt, eine gute, gar optimale, Losung sehen. Dieses gilt aber nicht fur Maschinen und Softwareprogramme, denn diese konnen die Gesamtheit nicht wie ein Mensch begreifen. Somit mussen andere, konkretere, Losungen genutzt werden. Ziel dieser Arbeit ist es, einen Uberblick uber die Geschichte, Definition und Arten des Problems des Handlungsreisenden zu geben. Die Einordnung in der theoretischen Informatik zu klassifizieren und zu beschreiben sowie eine ausfuhrliche Ubersicht und Beschreibung von bekannten exakten und annahernden Losungsverfahren zu geben. Ziel soll ein Kompendium fu

O autorze

Pohl Kai ist 1964 in Wittenburg geboren und Mitbegründer und Redakteur bei floppy myriapoda.