✏️ Übungen zu Kap. 2 · Problem und Probleminstanz
Freiwillig – such dir aus, was du üben willst.
Von der Tabelle zum Graphen
Oft liegen die Daten als Tabelle vor. Die Tabelle zeigt die Entfernungen (km) zwischen saarländischen Städten, die direkt durch eine Straße verbunden sind.
| von | nach | km |
|---|---|---|
| St. Wendel | Merzig | 50 |
| St. Wendel | Saarlouis | 45 |
| St. Wendel | Neunkirchen | 20 |
| Merzig | Saarlouis | 24 |
| Saarlouis | Saarbrücken | 25 |
| Saarlouis | Neunkirchen | 40 |
| Saarbrücken | Neunkirchen | 23 |
| Saarbrücken | Homburg | 36 |
| Neunkirchen | Homburg | 19 |
MZG = Merzig, SLS = Saarlouis, SB = Saarbrücken, NK = Neunkirchen, WND = St. Wendel, HOM = Homburg
Übung 1: Stelle die Tabelle als gewichteten Graphen dar. Die Städte sind schon platziert.
Übung 1: Stelle die Tabelle als gewichteten Graphen dar. Die Städte sind schon platziert.
Übung 3: Beschreibe ein weiteres Optimierungsproblem aus deinem Alltag. Was ist gegeben, was ist gesucht, und was wäre eine konkrete Instanz?
Ein anderes Kriterium
Ob eine Lösung optimal ist, hängt vom Kriterium ab. Bisher war die Fahrzeit entscheidend. Ein Lieferdienst, der unterwegs in jedem Ort halten muss, sucht vielleicht lieber einen Weg durch möglichst wenige Orte.
S = Saarlouis, D = Dillingen, L = Lebach, W = Schwalbach, V = Völklingen, P = Püttlingen, R = Riegelsberg, H = Heusweiler, B = Saarbrücken
Übung 5: Wie ist der schnellste Weg aus Übung 4 einzuordnen, wenn das Kriterium „möglichst wenige Orte“ gilt?