Problem des Handlungsreisenden

Angefangen wurde die Stunde wie üblich durch das Besprechen des vorherigen Protokolls. Hierbei wurden wir nochmal auf einen Fehler in der Ausdrucksweise aufmerksam gemacht:
Es gibt keine „leichten“ oder „schweren“ Probleme in NP, es gibt lediglich Probleme in NP und NP-vollständige Probleme.

Problemreduktion am Beispiel des Problems des Handlungsreisenden und dem Hamilton-Problem

Zu Beginn muss der Unterschied zwischen den zwei Problemen klar gemacht werden. Das Hamilton-Problem lautet wie folgt:
Beim Hamilton-Problem ist ein (ungerichteter und ungewichteter) Graph mit seinen Knoten und Kanten gegeben. Zu entscheiden ist, ob es einen Hamiltonkreis gibt – d.h. eine Rundreise durch den Graphen, in der jeder Knoten genau einmal vorkommt – nur Start- und Zielknoten kommen genau zweimal vor.

Im Vergleich dazu; das Problem des Handlungsreisenden (auch bekannt als TSP=Traveling Salesman Problem):
Beim Problem des Handlungsreisenden ist ein (ungerichteter und gewichteter) Graph mit seinen Knoten und gewichteten Kanten sowie eine Gewichtsschranke gegeben. Zu entscheiden ist, ob es eine Rundreise durch den Graphen gibt (in der jeder Knoten genau einmal vorkommt – nur Start- und Zielknoten kommen genau zweimal vor), so dass die Summe der Gewichte längs der Rundreise kleiner oder gleich der Gewichtsschranke ist.

Auf Inf-Schule wird nun erklärt, wie das Hamilton-Problem, anhand eines Graphen, auf das Problem des Handlungsreisenden reduziert werden kann.
Hierbei wird geprüft, ob man bei dem gegebenen, ungewichteten Graphen G einen Hamiltonkreis bilden kann.
Zum ungewichteten Graphen G wird jetzt ein gewichteter Graph G' konstruiert, indem die Knoten und Kanten von G übernommen werden, die Kanten von G mit dem Gewicht 1 bewertet und sämtliche noch möglichen Kanten zwischen Knoten von G hinzugenommen und mit dem Gewicht 2 bewertet werden.
Nun wird aus einem Algorithmus, der für das Lösen des Problem des Handlungsreisenden konstruiert wird, ein Algorithmus zum Lösen des Hamilton-Problems entwickelt.
Man spricht hierbei von einer polynomialen Problemreduktion.

Hausaufgaben

Die Hausaufgabe ist zu finden in Herr Karp’s Protokoll: „Problemreduktion und Zusammenfassung

Schreibe einen Kommentar