Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


44. Erschöpfendes Durchsuchen



Übungen

  1. Welchen Algorithmus würden Sie vorziehen: Einen, der N5 Schritte erfordert, oder einen, der 2N Schritte erfordert?
  2. Enthält der »Labyrinth«-Graph aus Kapitel 29 einen Hamilton-Zyklus?
  3. Skizzieren Sie den der Abbildung 44.4 entsprechenden Baum, der sich ergibt, wenn Sie in dem Graphen einen Hamilton-Zyklus suchen und im Knoten B statt im Knoten A beginnen.
  4. Wieviel Zeit könnte erschöpfendes Durchsuchen erfordern, um einen Hamilton-Zyklus in einem Graph zu finden, in dem alle Knoten mit genau zwei anderen Knoten verbunden sind? Beantworten Sie die gleiche Frage für den Fall, daß alle Knoten mit genau drei anderen Knoten verbunden sind.
  5. Wie viele Aufrufe von visit (als Funktion von V) erfolgen bei der Prozedur zur Erzeugung von Permutationen?
  6. Leiten Sie aus dem angegebenen Programm eine nichtrekursive Prozedur zur Erzeugung von Permutationen ab.
  7. Erstellen Sie ein Programm, mit dessen Hilfe bestimmt werden kann, ob zwei gegebene Adjazenz-Matrizen den gleichen Graph darstellen oder nicht, wenn man von unterschiedlichen Bezeichnungen der Knoten absieht.
  8. Erstellen Sie ein Programm zur Lösung des Rucksack-Problems aus Kapitel 42, wenn die Größen reelle Zahlen sein können.
  9. Erstellen Sie ein Programm zur Ermittlung der Anzahl von Spannbäumen für eine Menge von N Punkten in der Ebene ohne sich schneidende Kanten.
  10. Lösen Sie das Euklidische Problem des Handlungsreisenden für unser Beispiel mit sechzehn Punkten.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]