Bachelorarbeit aus dem Jahr 2013 im Fachbereich Informatik - Wirtschaftsinformatik, Note: 1.3, Leuphana Universitaet Lueneburg, Veranstaltung: Bachelorarbeit, Sprache: Deutsch, Abstract: Ein Handlungsreisender soll eine gewisse Anzahl von Kunden in verschiedenen Staedten besuchen, in jeder Stadt einen Kunden, und anschliessend zum Ausgangspunkt zurueckkehren. Doch wie ist diese Reise zu waehlen, sodass der Handlungsreisende den moeglichst kuerzesten 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 gehoert es zu einer sehr wichtigen Klasse der theoretischen Informatik; den sogenannten NP-vollstaendigen Problemen, fuer die keine effizienten und exakten Loesungsverfahren existieren bzw. existieren koennen (unter der Annahme das PNP gilt). Intuitiv kann ein Mensch mit Blick auf eine Karte und einer geringen Anzahl an Staedten, die es fuer eine Rundreise zusammenzufuehren gilt, eine gute, gar optimale, Loesung sehen. Dieses gilt aber nicht fuer Maschinen und Softwareprogramme, denn diese koennen die Gesamtheit nicht wie ein Mensch begreifen. Somit muessen andere, konkretere, Loesungen genutzt werden. Ziel dieser Arbeit ist es, einen UEberblick ueber die Geschichte, Definition und Arten des Problems des Handlungsreisenden zu geben. Die Einordnung in der theoretischen Informatik zu klassifizieren und zu beschreiben sowie eine ausfuehrliche UEbersicht und Beschreibung von bekannten exakten und annaehernden Loesungsverfahren zu geben. Ziel soll ein Kompendium fuer das Problem des Handlungsreisenden sein. Fuer diese Arbeit wird vorausgesetzt, dass der Leser grundlegende Kenntnisse der Mathematik, Graphentheorie und theoretischen Informatik besitzt.
