Fragen

[kumpelblase2]

• [x] Wie stellen Sie sicher, dass der generierte vollständige Graph, die Dreiecksungleichung erfüllt?
• [x] Welcher Algorithmus/Implementierung ist besser? Wie sieht das bei wiederholten Versuchen so etwa 100 aus?
• [x] Welcher der Beiden Algorithmen benötigt ein vollständiges, ein symetrisches und/oder ein metrisches TSP?
• [x] Wie könnten Sie Ihre Algorithmen anpassen, um in Graph3 eine möglichst kurze Rundreise durch Kiel, Husum, Lüneburg, Lübeck, Hameln, Paderborn, Hannover und Cuxhaven zu bekommen?

[kumpelblase2]

3: Nearest neighbour braucht nur vollständiges. MST hat an sich keine Präferenz, intern wird der Graph im Verlaufe jedoch zu einem metrischen TSP.

[kumpelblase2]

4: Falls es keine Kante zu einem der gesuchten Orte gibt, wird Dijkstra für die Suche des nächstgelegenen von den gesuchten Orte zu finden. (Nearest Neighbor) Bei der Spannbaumheuristik dann abbrechen, sobal alle gesuchten Orte sich in diesem befinden. (MST)