Vorlesung 11 Flashcards

1
Q

Traveling Salesman Problem (TSP)

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

je (2) Pro & Cons

Optimales Verfahren vs. Heuristik

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Wann sollte man optimale Verfahren,

wann heuristiken verwenden

A

Optimale Verfahren

keine Probleme

Heuristiken

sehr große Probleme

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Erkläre Nearest Neighbour

Pro / Contra (1)

A

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

+ sehr einfach

  • stark vereinfachend
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Erkläre Cheapest insertion Heuristik

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Weitere Optimierung vom TSP

A

durch Paarweise vertauschung

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Bin Packing

First Fit erklären

A

keine Sortierung,

1 Behälter solange auffüllen bis voll

2 Behälter etc

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Bin Packing

First Fit Descreasing

A

Sortierung

erst groß dann klein

und dann so wie bei First Fit

How well did you know this?
1
Not at all
2
3
4
5
Perfectly