AuK/Verzweigen und beschränken SS11/Aufgaben

Wiki-Quelltext dieser Seite.

= Aufgaben zu dem Themenbereich "Verzweigen und Beschränken" =
__NOTOC__
== 1. Wege und Entfernungen ==

Gegeben ist folgende Entfernungsmatrix:

{| class="wikitable"
!style="text-align:center"| von \ nach
!style="width: 4em; text-align:center"| 1
!style="width: 4em; text-align:center"| 2
!style="width: 4em; text-align:center"| 3
!style="width: 4em; text-align:center"| 4 
|-
! 1
|style="text-align:center"| 0
|style="text-align:center"| 5
|style="text-align:center"| 88
|style="text-align:center"| 49
|-
!style="text-align:center"| 2
|style="text-align:center"| 4
|style="text-align:center"| 0
|style="text-align:center"| 64
|style="text-align:center"| 70
|-
! 3
|style="text-align:center"| 97
|style="text-align:center"| 17
|style="text-align:center"| 0
|style="text-align:center"| 78
|-
! 4
|style="text-align:center"| 2
|style="text-align:center"| 79
|style="text-align:center"| 35
|style="text-align:center"| 0
|}


Ermitteln sie alle möglichen Routen und deren Strecken.

<popup name="Lösung">

Es existieren 3! Lösungen:

1->2->3->4->1  : 149<br>
1->2->4->3->1  : 207<br>
1->3->2->4->1  : 177<br>
1->3->4->2->1  : 249<br>
1->4->3->2->1  : 105<br>
1->4->2->3->1  : 289<br>

</popup>

== 2. Anwendung des Rucksackproblems ==

Gegeben ist folgende Wertetabelle:

{| class="wikitable"
!class="hintergrundfarbe6" | i
! 1 !! 2 !! 3 !! 4 
|-
! <math>w_i</math> 
| 35 || 18  ||  9  || 4
|-
! <math>g_i</math> 
| 7 || 6 || 3 || 2
|-
! <math>wq_i</math> 
| 5 || 3 || 3 || 2
|}

Das zulässige Gesammtgewicht des Rucksackes beträgt 12.

Lösen sie das Rucksackproblem mit einem Breitensuchbaum.

<popup name="Lösung">
Die Lösung wird später nachgetragen.

[[Bild:S3erjaeh_Lösung-Aufgabe-1.2-.gif]]

</popup>

== 3. TSP - Traveling Salesman Problem ==

Gegeben ist folgende Entfernungsmatrix:


{| class="wikitable"
!style="text-align:center"| von \ nach
!style="width: 4em; text-align:center"| 1
!style="width: 4em; text-align:center"| 2
!style="width: 4em; text-align:center"| 3
!style="width: 4em; text-align:center"| 4 
|-
! 1
|style="text-align:center"| 0
|style="text-align:center"| 65
|style="text-align:center"| 14
|style="text-align:center"| 93
|-
!style="text-align:center"| 2
|style="text-align:center"| 87
|style="text-align:center"| 0
|style="text-align:center"| 55
|style="text-align:center"| 13
|-
! 3
|style="text-align:center"| 6
|style="text-align:center"| 59
|style="text-align:center"| 0
|style="text-align:center"| 74
|-
! 4
|style="text-align:center"| 33
|style="text-align:center"| 27
|style="text-align:center"| 71
|style="text-align:center"| 0
|}

Finden Sie die kürzeste Rundreise mithilfe der Baumstruktur. Überprüfen sie Ihr Ergebniss mit dem Racket Programm.
<br>(Hinweis: Sollte es zu Problemen in der Ausführung des Programmes kommen, versuchen Sie es bitte mit einem anderen Browser)
<br>Verwenden sie dazu folgende Definition:

 (define matrix2 '((0 65 14 93) (87 0 55 13) (6 59 0 74) (33 27 71 0)))

<popup name="Lösung">
Lösung: 1 -> 3 -> 2 -> 4 -> 1  :  119 

[[Bild:S3erjaeh_Lösung-Aufgabe-3.gif]]
</popup>

<!-- Wenn ich sage es ist sinnlos, wäre es auch sinnlos eine auszurechnen^^

Gegeben ist folgende Entfernungsmatrix:


{| class="wikitable"
!style="text-align:center"| von \ nach
!style="width: 4em; text-align:center"| 1
!style="width: 4em; text-align:center"| 2
!style="width: 4em; text-align:center"| 3
!style="width: 4em; text-align:center"| 4 
|-
! 1
|style="text-align:center"| x
|style="text-align:center"| 9
|style="text-align:center"| 5
|style="text-align:center"| 3
|-
!style="text-align:center"| 2
|style="text-align:center"| 11
|style="text-align:center"| x
|style="text-align:center"| 17
|style="text-align:center"| 5
|-
! 3
|style="text-align:center"| 17
|style="text-align:center"| 13
|style="text-align:center"| x
|style="text-align:center"| 19
|-
! 4
|style="text-align:center"| 19
|style="text-align:center"| 21
|style="text-align:center"| 1
|style="text-align:center"| x
|}

Stellen Sie die reduzierte Entfernungsmatrix auf!


-->

== Zusatzaufgaben: ==


Testen Sie die eine weitere Heuristik Ihrer Wahl mit dem Lösungsbaum und der Entfernungsmatrix aus Aufgabe 3. Entwickeln sie dafür zuerst eine geignete Schranke und vergleichen Sie anschließend Ihre Ergebnisse.

Entwickeln Sie einen Algorithmus für das Rucksackproblem.