Hamiltonscher Pfad

In der Problemstellung des Hamiltonschen Pfades vernachlässigt man Kanten im TSP. Man fragt einfach, ob es einen Pfad in einem Graphen gibt, der alle Knoten genau einmal besucht.
Im ersten Bild gibt es keinen Hamiltonschen Pfad. Erst wenn man die gepunktete Linie hinzufügt, gibt es einen Hamiltonschen Pfad, der in Bild 2 verdeutlicht wurde.

Bild 1	Bild 2

Das Rucksackproblem

Das Rucksackproblem, auch genannt knapsack problem ist ein Optimierungsproblem. Es geht darum, einen Rucksack so zu packen, daß mit den enthaletenen Gegenständen ein Maximum z.B. an Wert erreicht wird, ohne dabei die maximale Kapazität des Rucksacks zu überschreiten.

In der c't Heft 12/96 wird dazu ein Beispiel sowie ein Lösungsansatz durch Tabu Search beschrieben. In dem Beispiel geht es um einen Diplomaten, der seinen Koffer so füllen möchte, daß der Verkauf des Inhalts den größtmöglichen Gewinn erbringt. Der Koffer darf als Handgepäck aber nicht mehr als 20 kg wiegen.

Das Affenpuzzel

9 quadratische Karten sind mit stilisierten Affen bedruckt. Auf jeder Karte ist an jeder der 4 Kanten je ein halber Affe zu sehen, dessen Gegenstück sich auf einer anderen Karte befindet. Die Affen haben unterschiedliche Farben.
Das Ziel des Puzzels ist es, ein 3x3 Quadrat mit diesen Karten so auszulegen, daß die Affenhälften zusammenpassen und die Farben an den Kanten übereinstimmen.

Eine Variante ist hier zu sehen. Statt Affen werden hier unterschiedlich farbige Dreiecke verwendet.

Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996