Hamilton Kreise Übung

Aus ProgrammingWiki
Archivierte Version vom 2015-12-09T09:21:43+00:00. Aktuelle Version

Übung Teil 1: Hamilton Graphen und Travelling Salesman Problem

Wir haben folgenden Graphen:
Jowolf_LandkreisGörlitzGraph.png


Aufgaben:

  1. Stellen sie einen 2. Graphen auf, der die Fahrzeit beinhaltet. Die Durschnittsgeschwindigkeit beträgt 70 km/h. (Mögliches Mittel: GeoGebra)
  2. Erstellen Sie einen Hamiltonweg und einen Hamiltonkreis für den Graphen mit der Fahrzeit und der Strecke. Ihr Startpunkt wird Ihnen zugeteilt https://docs.google.com/spreadsheets/d/1dYIZjJl2tPKctqmwCNrGQ7tBpRiRB7I8hQtVnCXomFg/edit?usp=sharing. Geben Sie zum Vergleich die Länge bzw. die Gesamtfahrzeit des Kreises bzw. Graphen an. Tragen Sie diese Ergebnisse in die Datei https://docs.google.com/spreadsheets/d/1dYIZjJl2tPKctqmwCNrGQ7tBpRiRB7I8hQtVnCXomFg/edit?usp=sharing ein.
  3. Markieren Sie eine Dreiecksungleichung.

Zusatzaufgabe:
Entwickeln sie einen Pseudocode für die erschöpfende Suche.