AuK/Verzweigen und beschränken SS11/Aufgaben

Wiki-Quelltext dieser Seite.

= Aufgaben zu dem Themenbereich "Verzweigen und Beschrenken" =

== Anwendung auf das Rucksackproblem ==

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.

Zusatzaufgabe: Entwickeln Sie einen Algorithmus für das Rucksackproblem.

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

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

-->
</popup>

== TSP - Trade 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 Baumstrucktur. Überprüfen sie Ihr Ergebniss mit dem Racket Programm.
<br>(Nutzen Sie dazu bitte keinen Internet Explorer, da dort der Code nicht ordnungsgemäß ausgeführt wird. Getesteter Browser: Firefox)
<br>Verwenden sie dazu folgende Definition:

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

Zusatzaufgabe: Testen Sie die eine weitere Heuristik mit dem Lösungsbaum.

<popup name="Lösung">
Die Lösung wird später nachgetragen.
<!-- Lösung: 1    3    2    4  ->  119  -->
</popup>


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!