Hilfe zur Klausuraufgabe Klausur Mrz 2015 (WS 2014/15)

Hallo,

ich habe mich eben durch diese Klausur gewühlt und würde gerne meine Ergebnisse mit Euch vergleichen.

Aufgabe 1a) siehe Anhänge.

Aufgabe 1b) Ich habe drei Blätter und damit 3 Ketten:

• HA-DO-BO-HER-GE-OB-DU
• HA-DO-BO-E
• HA-DO-BO-W-HIL

Aufgabe 1c) Die Behauptung ist richtig. Ein minimales Gerüst minimiert die Summe der Gewichte. Somit kann es sein, dass zwei Orte nicht über den kürzesten Weg miteinander verbunden sind.

Aufgabe 2: als Wegstrecke mit dem Verteilzentrum HA erhalte ich 510. Die maximale Ersparnis kann durch Einfügen des Verteilzentrums BO erzielt werden. Die Ersparnis beträgt 160 und damit die neue Wegstrecke 350.

Aufgabe 3: Die Route ist HA-DO-BO-HER-GE-OB-DU-E-HIL-W-HA und beträgt 230.

Aufgabe 4a: siehe Anhang

Aufgabe 4b: 3 Konflikte, 2 Konflikte, 4 Konflikte

Aufgabe 4c: Nachbar in der zweiten Iteration [(BF),(EA),(CD),(GH)] und Nachbar in der dritten Iteration [(HF),(EA),(CD),(BG)]. Der letzte Nachbar ist konfliktfrei.

Aufgabe 5a+b: Kürzeste Wege

1. BO: 6-1 mit 37
2. DO: 6-2 mit 30
3. DU: 6-1-4-3 mit 79
4. E: 6-1-4 mit 56
5. GE: 6-1-7-5 mit 59
6. HA: 6 mit 0
7. HER: 6-1-7 mit 44
8. HIL: 6-10-8 mit 58
9. OB: 6-1-7-5-9 mit 76
10. W: 6-10 mit 34

Aufgabe 5c: Änderung in Iteration 8. OB ist nicht erreichbar.

Hallo
Laut Angabe soll hier doch der Prim-Algorithmus verwendet werden oder?
bei Aufgabe 1 a ii hat du den Kruskal verwendet oder?
Wenn man den Kruskal verwenden würde wäre aber die Reihenfolge eine andere. Wie hast du das gemacht?
Aufgabe 2: hier ist ein Lösungsshema angegeben, wie rechnest du 3 und 4? steh da voll am Schlauch, weiss nicht was die da wollen.
Aufgabe 3: ist das das A*-Verfahren oder Tabu-Search?
Wäre über deine Hilfe zu diesen Fragen sehr dankbar.
Leider belegen/schreiben das Modul sehr wenige, daher kann man sich kaum mit jemanden austauschen.
lg

Mimzy schrieb:

Laut Angabe soll hier doch der Prim-Algorithmus verwendet werden oder?
bei Aufgabe 1 a ii hat du den Kruskal verwendet oder?

Zum Vergrößern anklicken....

Ich habe den Prim verwendet. Bei Kruskal wäre als zweite Kante HA-BO hinzugekommen, da man von der Ausgangskante weitermacht, solange kein Kreis entsteht.

Mimzy schrieb:

Aufgabe 2: hier ist ein Lösungsshema angegeben, wie rechnest du 3 und 4?

Zum Vergrößern anklicken....

3 und 4? Ich sehe da nur a, b, und c. Was genau meinst Du?

Mimzy schrieb:

Aufgabe 3: ist das das A*-Verfahren oder Tabu-Search?

Zum Vergrößern anklicken....

Da Aufgabe 3 nur 5 Punkte bringt, kann die Lösung nicht aufwendig sein. Nächster Nachbar heißt, ich nehme immer die Kante mit dem geringsten Gewicht hinzu ohne einen Kreis zu erzeugen.

Aufgabe 2: hier ist ein Lösungsshema angegeben, wie rechnest du 3 und 4?
3 und 4? Ich sehe da nur a, b, und c. Was genau meinst Du?
Im Lösungsschema sind Nummern vermerkt, und bei 3 und 4 weiß ich nicht was die wollen.

Danke für deine Antworten.

Mimzy schrieb:

Aufgabe 2: hier ist ein Lösungsshema angegeben, wie rechnest du 3 und 4?
3 und 4? Ich sehe da nur a, b, und c. Was genau meinst Du?
Im Lösungsschema sind Nummern vermerkt, und bei 3 und 4 weiß ich nicht was die wollen.

Danke für deine Antworten.

Zum Vergrößern anklicken....

in der Aufgabenstellung steht bei 2b) , dass um die "3" und "4" im Lösungsschema zu ermitteln, bei Bochum 20 Km und bei Essen 25 Km hinzugerechnet werden sollen. Wenn du die Tabbele 1 in der Aufgabe 2 um diese Werte korrigierst für jeden Ort, hast du "3" und "4".

OK! Vielen Dank für deine Antwort.

Zu Aufgabe 3 habe ich in meinem vorherigen Post was geschrieben.
Bei Aufgabe 4a soll der Graph zum beschriebenen Problem gezeichnet werden. Die Knoten sind ja schon da, also fehlen noch die Kanten.
In Teilaufgabe 4b sind drei Lösungen angegeben, die bewertet werden sollen. Es müssen also die Anzahl der Konflikte ermittelt werden. Je weniger Konflikte, desto besser.
In 4c wird dann Simulated Annealing angewendet. Das Lösungsschema steht netterweise schon da und muss vervollständigt werden.