Rundreise zum Nächsten

Informationen

Kategorie

Schw.

Tags

Falscher Greedy

Aufgabe

Du möchtest deine BesucherInnen zu einer ganzen Reihe an Sehenswürdigkeiten herumführen. Da der Weg dazwischen eher langweilig ist, möchtest du den so kurz wie möglich halten. Du hast alle paarweisen Distanzen zwischen allen Sehenswürdigkeiten sowie auch deiner Wohnung (Start- und Zielpunkt der Reise). Du überlegst dir die folgende Strategie, um den kürzesten Rundweg zu finden. Von der Wohnung aus gehst du immer zur dichtesten Sehenswürdigkeit, bei der ihr noch nicht wart. Zeige, dass diese Strategie nicht für alle paarweisen Distanzen den kürzeste Rundweg findet.