Aufgabe 2 - Graphen und Graphenalgorithmen · Abitur NRW Informatik LK · Haupttermin 2022

Aufgabenstellung: Evakuierungskonzept für den Zoo „Tweety’s Home“

Im Zoo „Tweety’s Home“ stehen Renovierungsarbeiten an. In diesem Zusammenhang soll auch ein Konzept entwickelt werden, mit dem die Besucherinnen und Besucher im Notfall evakuiert werden können. Der Zoo setzt sich aus mehreren Attraktionen zusammen, zwischen denen Wege verlaufen. Jede Attraktion darf nur von einer bestimmten Höchstzahl an Gästen gleichzeitig besucht werden. Da die Wege zwischen den Attraktionen unterschiedlich breit sind, können sich darauf pro Minute unterschiedlich viele Gäste von einer Attraktion zur anderen bewegen. Für den Evakuierungsfall ist für jede Attraktion immer dasjenige Wegstück als bevorzugter Notausgang ( [Notausgangs-Symbol]) gekennzeichnet, über das sich die größtmögliche Anzahl an Gästen pro Minute bewegen kann; nur der Eingang und die Ausgänge verfügen nicht über diese Markierung.

Abbildung 1 zeigt beispielsweise:

Ein-/Ausgang und Spielplatz sind über einen großzügigen Weg verbunden, über den jeweils bis zu 500 Personen pro Minute in jede der beiden möglichen Richtungen zwischen diesen Attraktionen wechseln können.

Für das Delfinarium sind maximal 2000 Gäste zur gleichen Zeit vorgesehen.

Im Evakuierungsfall sollen sich die Gäste des Ziegen-Geheges auf den Weg zum Esel-Gehege begeben.

Eine Softwarefirma hat schon für andere (Freizeit-)Parks eine Software zur Steuerung der Besucherströme programmiert. Es soll geprüft werden, ob sich diese Software für diesen Zoo eignet. Die Firma legt dazu einen Ausschnitt aus einem Implementationsdiagramm (Abbildung 2) vor. Eine Dokumentation der verwendeten Klassen findet sich im Anhang.

Notfall-Räumung einzelner Attraktionen

Ein Teil des Evakuierungskonzepts des Zoos beschäftigt sich mit der Notfall-Räumung einzelner Attraktionen. In einem solchen Fall kann mit einer Attraktion wie folgt verfahren werden:

Eine Attraktion...

wird geräumt: Alle Gäste, die sich an dieser Attraktion befinden, müssen sie verlassen. Dabei wird für die Simulation festgelegt, dass die Gäste die zur Verfügung stehenden Wege absteigend nach ihrer Kapazität nutzen, also zunächst den markierten Notausgang und als Ausweichmöglichkeit alle anderen Wege in absteigender Reihenfolge ihrer Kapazität. Zu räumende Attraktionen dürfen aber immer noch von Gästen neu betreten werden, wenn die Attraktion auf deren Fluchtweg zum Ausgang des Zoos liegt. Die Gäste aber dürfen dort nicht verbleiben, sondern müssen (wie alle anderen) die Attraktion schnellstmöglich verlassen.

ist gesperrt: Gesperrte Attraktionen werden geräumt und dürfen von niemandem neu betreten werden.

Anhang: Dokumentationen der verwendeten Klassen

Die Klasse Besucherverwaltung

Ein Objekt dieser Klasse verwaltet den Lageplan des Zoos mit seinen Attraktionen und aktueller Anzahl von Besucherinnen und Besuchern.

Ausschnitt aus der Dokumentation der Klasse Besucherverwaltung

Besucherverwaltung()

Eine Besucherverwaltung mit dem aktuellen Lageplan des Zoos, allen Attraktionen und den gegenwärtigen Besucherzahlen wird initialisiert. Alle Attraktionen befinden sich im Normalbetrieb, d. h., sie sind nicht gesperrt und werden nicht geräumt.

Die Klasse Attraktion

Ein Objekt dieser Klasse verwaltet eine Attraktion des Zoos, an der sich Gäste sammeln können, z. B. ein Gehege oder einen besonderen Platz, wie Spielplätze oder Sanitärhäuser.

Ausschnitt aus der Dokumentation der Klasse Attraktion

Attraktion(Graph pLageplan, String pID, int pMaxBesucherzahl, int pAktBesucherzahl)

Eine Attraktion wird mit den angegebenen Werten initialisiert: befindet sich auf dem durch pLageplan angegebenen Lageplan; bekommt die interne ID pID; kann maximal pMaxBesucherzahl Gäste zur gleichen Zeit aufnehmen (ist diese als Ausgang anzusehen, wird die Anzahl auf Integer.MAX_VALUE festgelegt); ist aktuell mit pAktBesucherzahl besetzt.

int gibMaxBesucherzahl()

Die maximale Anzahl der Besucherinnen und Besucher, die diese Attraktion gleichzeitig betreten dürfen, wird zurückgegeben.

int gibAktBesucherzahl()

Die aktuelle Anzahl an Besucherinnen und Besuchern dieser Attraktion wird zurückgegeben.

void setzeAktBesucherzahl(int pAktBesucherzahl)

Die aktuelle Anzahl der Besucherinnen und Besucher dieser Attraktion wird auf den Wert pAktBesucherzahl gesetzt.

boolean istGesperrt()

Wenn diese Attraktion zum Zeitpunkt des Methodenaufrufs gesperrt ist, wird true zurückgegeben, ansonsten false. Ist die Attraktion gesperrt, darf sie nicht mehr betreten werden und wird so schnell wie möglich geräumt.

void setzeIstGesperrt(boolean pIstGesperrt)

Der Sperrstatus wird auf den Wert gesetzt. Hat pIstGesperrt den Wert true, wird die Attraktion gleichzeitig als „zu räumen“ markiert. Hat pIstGesperrt den Wert false, wird der Räumungsstatus nicht verändert.

boolean wirdGeraeumt()

Wenn diese Attraktion geräumt werden muss, wird true zurückgegeben, ansonsten false.

void setzeWirdGeraeumt(boolean pWirdGeraeumt)

Der Räumungsstatus dieser Attraktion wird auf den Wert von pWirdGeraeumt gesetzt.

int ermittleMaxAbgabe(Attraktion pNachbar)

Ermittelt die maximale Anzahl an Besucherinnen und Besuchern, die von dieser Attraktion aktuell an die durch pNachbar angegebene Nachbarattraktion abgegeben werden können. Falls pNachbar nicht auf eine Nachbarattraktion verweist, liefert die Methode -1 zurück.

List<Attraktion> wasLiefereIch()

Diese Methode wird im Rahmen von Aufgabenteil c) analysiert.

Die Klasse Graph

Die Klasse Graph stellt einen ungerichteten, kantengewichteten Graphen dar.

Dokumentation der Klasse Graph

Graph()

Ein leerer Graph wird erstellt.

void addVertex(Vertex pVertex)

Fügt den Knoten pVertex ein, sofern es noch keinen Knoten mit derselben ID gibt und pVertex eine ID ungleich null hat.

void addEdge(Edge pEdge)

Fügt die Kante pEdge ein, sofern beide Knoten im Graphen enthalten, nicht identisch sind und noch keine Kante zwischen beiden existiert.

void removeVertex(Vertex pVertex)

Entfernt den Knoten pVertex und löscht alle Kanten, die mit ihm inzident sind.

void removeEdge(Edge pEdge)

Entfernt die Kante pEdge aus dem Graphen.

Vertex getVertex(String pID)

Liefert das Knotenobjekt mit pID als ID oder null.

List<Vertex> getVertices()

Liefert eine neue Liste aller Knotenobjekte vom Typ List<Vertex>.

List<Vertex> getNeighbours(Vertex pVertex)

Liefert alle Nachbarn des Knotens pVertex als neue Liste vom Typ List<Vertex>.

List<Edge> getEdges()

Liefert eine neue Liste aller Kantenobjekte vom Typ List<Edge>.

List<Edge> getEdges(Vertex pVertex)

Liefert eine neue Liste aller inzidenten Kanten zum Knoten pVertex.

Edge getEdge(Vertex pVertex, Vertex pAnotherVertex)

Liefert die Kante, welche die Knoten pVertex und pAnotherVertex verbindet, oder null.

void setAllVertexMarks(boolean pMark)

Setzt die Markierungen aller Knoten des Graphen auf den Wert pMark.

boolean allVerticesMarked()

Liefert true, wenn die Markierungen aller Knoten des Graphen den Wert true haben, ansonsten false.

void setAllEdgeMarks(boolean pMark)

Setzt die Markierungen aller Kanten des Graphen auf den Wert pMark.

boolean allEdgesMarked()

Liefert true, wenn die Markierungen aller Kanten des Graphen den Wert true haben, ansonsten false.

boolean isEmpty()

Liefert true, wenn der Graph keine Knoten enthält, ansonsten false.

Die Klassen Vertex, Edge und List<ContentType>

Klasse Vertex

Vertex(String pID): Erstellt neuen Knoten mit ID pID, Markierung false.

String getID(): Liefert die ID des Knotens.

void setMark(boolean pMark): Setzt Markierung des Knotens.

boolean isMarked(): Liefert Markierungsstatus.

Klasse Edge

Edge(Vertex pVertex, Vertex pAnotherVertex, double pWeight): Verbindet zwei Knoten mit Kantengewicht.

void setWeight(double pWeight) / double getWeight(): Setzt bzw. liefert das Gewicht.

Vertex[] getVertices(): Liefert Feld der beiden inzidenten Knoten (Index 0 und 1).

void setMark(boolean pMark) / boolean isMarked(): Markierungsverwaltung der Kante.

Generische Klasse List<ContentType>

List(), boolean isEmpty(), boolean hasAccess(), void next(), void toFirst(), void toLast(), ContentType getContent(), void setContent(ContentType pContent), void append(ContentType pContent), void insert(ContentType pContent), void concat(List<ContentType> pList), void remove().

Teilaufgabe a)

Der Zoo soll um eine Attraktion Pinguine erweitert werden. Diese Attraktion soll alle folgenden Eigenschaften erfüllen:

Die Attraktion kann maximal $100$ Gäste aufnehmen.

Die neue Attraktion ist durch direkte Wege jeweils mit den Ziegen- und Esel- Attraktionen verbunden.

Von der Ziegen-Attraktion können $30$ Gäste pro Minute zur neuen Attraktion gelangen.

Sollte die neue Attraktion geräumt werden müssen, sollen die Gäste als Fluchtweg zunächst zur Esel-Attraktion gehen.

a.1

Geben Sie zunächst ohne Berücksichtigung der geplanten Erweiterung an, wie viele Gäste höchstens pro Minute aus den benachbarten Attraktionen zusammen zum Delfinarium gelangen können.

a.2

Ergänzen Sie Abbildung 1 um die Attraktion Pinguine und bestimmen Sie dabei eine passende (bzw. die kleinstmögliche) Kapazität für den Weg von den Pinguinen zur Esel-Attraktion.

Hinweis: Es genügt, nur die Abweichungen gegenüber Abbildung 1 zu zeichnen.

Teilaufgabe b)

Ein Softwareunternehmen hat schon für andere (Freizeit-)Parks eine Software zur Steuerung der Besucherströme programmiert. Es stellt dazu einen Ausschnitt eines Implementationsdiagramms (Abbildung 2) bereit.

b.1

Erläutern Sie die Beziehungen zwischen den Klassen Besucherverwaltung, Attraktion, Graph und Vertex in der durch Abbildung 2 gegebenen Teilmodellierung.

b.2

Begründen Sie, weshalb es in der vorliegenden Modellierung sinnvoll ist, dass jedes Objekt der Klasse Attraktion auf ein Objekt der Klasse Graph zugreifen kann.

Teilaufgabe c)

Die Klasse Attraktion enthält die folgende Methode ohne Dokumentation:

public List<Attraktion> wasLiefereIch() {

List<Attraktion> ret = new List<Attraktion>();

List<Vertex> allenachbarn = lageplan.getNeighbours(this);

List<Vertex> nachbarn = new List<Vertex>();

allenachbarn.toFirst();

while (allenachbarn.hasAccess()) {

Attraktion aktN = (Attraktion) allenachbarn.getContent();

if (!aktN.istGesperrt()) {

nachbarn.append(aktN);

}

allenachbarn.next();

}

nachbarn.toFirst();

while (nachbarn.hasAccess()) {

Attraktion aktN = (Attraktion) nachbarn.getContent();

ret.toFirst();

while (ret.hasAccess()

&& lageplan.getEdge(this, aktN).getWeight()

<= lageplan.getEdge(this, ret.getContent()).getWeight()) {

ret.next();

}

if (ret.hasAccess()) {

ret.insert(aktN);

} else {

ret.append(aktN);

}

nachbarn.next();

}

return ret;

}

c.1

Analysieren Sie die Methode und erläutern Sie, wie sie arbeitet.

c.2

Ermitteln Sie schrittweise, was die Methode zurückgibt, wenn sie für das Objekt aufgerufen wird, das in Abbildung 1 die Attraktion Streicheltiere darstellt, und nur diese Attraktion gesperrt ist.

c.3

Erläutern Sie, welchem Zweck die Methode im Sachzusammenhang dient.

Teilaufgabe d)

Wird eine Attraktion geräumt, werden die Gäste in benachbarte Attraktionen gebracht. Die Methode ermittleMaxAbgabe der Klasse Attraktion soll ermitteln, wie viele Gäste derzeit zu einer gewählten Nachbarattraktion wechseln und dort untergebracht werden können. Ihr Methodenkopf lautet:

public int ermittleMaxAbgabe(Attraktion pNachbar)

Falls pNachbar keine benachbarte Attraktion bezeichnet, soll die Methode den Fehlerwert -1 zurückgeben.

d.1

Entwickeln Sie für diese Methode einen algorithmischen Lösungsansatz.

d.2

Implementieren Sie diese Methode in Java:

public int ermittleMaxAbgabe(Attraktion pNachbar)

Teilaufgabe e)

Bei einem schweren Notfall können mehrere Attraktionen gleichzeitig Alarm melden. Für eine schrittweise Räumung wird der Algorithmus aus Abbildung 3 vorgeschlagen:

Der Algorithmus soll nun am ursprünglichen Lageplan aus Abbildung 1 betrachtet werden.

e.1

Analysieren und erläutern Sie den Algorithmus im Sachzusammenhang.

e.2

Beurteilen Sie den Algorithmus im Sachzusammenhang anhand der folgenden Szenarien:

i) Alarm wird von den Attraktionen Streicheltiere, Ziegen und Esel gemeldet.

ii) Alarm wird von den Attraktionen Streicheltiere, Spielplatz, Delfinarium und Esel gemeldet.