Vorlesung 11

Question 1

Traveling Salesman Problem (TSP)

Answer 1

• Ein Handelsreisender muss 𝐽 Kunden besuchen
• Die Standorte der Kunden sind bekannt
• Die Entfernungen zwischen den Standorten sind bekannt
• Jeder Kunde wird genau einmal besucht
• Start und Zielpunkt sind identisch

Ziel: Minimiere die Anzahl gefahrener Kilomete

Question 2

je (2) Pro & Cons

Optimales Verfahren vs. Heuristik

Answer 2

Optimales Verfahren

+ genaue, sichere beste Lösung

+ hohe realibilität

• sehr aufwenidig
• geringer Mehrwert bei sehr vielen Optionen

Heuristik

+ Schnell, ressourcen sparend

+ ähnlich zu optimaler Lösung

• nicht optimal
• verzerrung

Question 3

Wann sollte man optimale Verfahren,

wann heuristiken verwenden

Answer 3

Optimale Verfahren

keine Probleme

Heuristiken

sehr große Probleme

Question 4

Erkläre Nearest Neighbour

Pro / Contra (1)

Answer 4

Wähle den Ort mit dem kleinsten Abstand, der noch nicht besucht wurde.

+ sehr einfach

• stark vereinfachend

Question 5

Erkläre Cheapest insertion Heuristik

Answer 5

Knoten wählen, dass Kosten so gering wie möglich erhöht werden.

1 Iteration: günsigster Weg vom Lager hin & zurück

2 Iteration: alle Knoten durch probieren: Vor oder Nach letzten Knoten einfügen? Günstigste nehmen

Question 6

Weitere Optimierung vom TSP

Answer 6

durch Paarweise vertauschung

Question 7

Bin Packing

First Fit erklären

Answer 7

keine Sortierung,

1 Behälter solange auffüllen bis voll

2 Behälter etc

Question 8

Bin Packing

First Fit Descreasing

Answer 8

Sortierung

erst groß dann klein

und dann so wie bei First Fit