Du stehst in Musterstadt an der Haltestelle Königsplatz und möchtest im ÖPNV-Netzwerk möglichst viele verschiedene Stationen besuchen – allerdings ohne eine Station mehr als einmal anzufahren.
Du hast dir verschiedene Strategien überlegt, die du bei jeder Entscheidung anwendest, wenn du zwischen benachbarten Stationen wählen musst:
Fahre zu der benachbarten Station,
(1) die selbst die wenigsten noch unbesuchten Nachbarstationen hat.
(2) die selbst die meisten noch unbesuchten Nachbarstationen hat.
(3) von der aus du insgesamt noch die meisten unbesuchten Stationen erreichen kannst.
(4) (1)-(3) je mit (wenn möglich) Vermeidung von Stationen, die nur Blätter (Stationen, von denen keine weitere unbesuchte Station erreichbar ist) als Nachbar haben.
Ergibt eine der Strategien in jedem möglichen Netzwerk den besten Pfad?
