Technische Universit ̈at Berlin WiSe 2019/20 Fakult ̈at II, Institut fu ̈r Mathematik
Sekretariat MA 5–2, Dorothea Kiefer-Hoeft
Dr. Frank Lutz
Sarah Morell, Manuel Radons
13. Programmieraufgabe Computerorientierte Mathematik I Abgabe: 14.02.2020 u ̈ber den Comajudge bis 16 Uhr
1 Anmerkungen zur Bonusaufgabe
Diese Bonusaufgabe geho ̈rt nicht zu den regula ̈ren Programmieraufgaben, welche zur Erlangung des Scheinkriteriums bearbeitet werden mussten. Sie ist deutlich umfangreicher als die Aufgaben 1-12. Wer sich an ihr versucht, darf sich daher jederzeit mit Fragen bei mir melden oder bei mir im Bu ̈ro vorbeischauen. Falls ein ernsthafter Wunsch zu erkennen ist, diese Aufgabe erfolgreich zu bearbeiten, werde ich gerne u ̈ber das u ̈bliche Maß hinaus Hilfestellungen geben.
2 Hierarchische Wegfindung in Videospielen
Wegfindung ist in der Informatik die algorithmengestu ̈tzte Suche nach dem oder den optimalen Wegen (englisch path) von einem gegebenen Startpunkt zu einem oder mehreren Zielpunkten. In Videospielen ist es oftmals wichtiger einen hinreichend guten Weg mit wenig Aufwand zu finden, als einen optimalen Weg, der mo ̈glicherweise nur mit betra ̈chtlichem Rechenaufwand zu berechnen ist. Insbesondere ist dies der Fall, falls Wegberechnungen, wie zum Beispiel in Echtzeitstrategiespielen, sehr ha ̈ufig vorgenommen werden.
Eine Mo ̈glichkeit, die Berechnung von Wegen effizient zu gestalten, ist eine hierarchische Un- terteilung des Wegfindungsprozesses. Eine Karte M wird in kleinere Teilkarten unterteilt, in welchen die Wegfindung mit geringem Aufwand zu bewa ̈ltigen ist. Auf der u ̈bergeordneten Ebene werden die Teilkarten als Knoten in einem Graphen repra ̈sentiert. Kanten in G entsprechen Wegen in M, Kantengewichte werden durch die La ̈ngen der besagten Wege gegeben. Aufgrund der begrenzten Zahl der Kanten in G ko ̈nnen die entsprechenden Wege und Wegla ̈ngen einmalig berechnet und, zum Beispiel, in einer Tabelle verfu ̈gbar gemacht werden.
Ein zu berechnender Weg setzt sich dann aus drei Teilstu ̈cken zusammen: Zwei neu zu berech- nenden Teil-Wegen in den Start- bzw. Ziel-Teilkarten, sowie einem mittleren Wegstu ̈ck, das aus der Tabelle ausgelesen wird und die erstgenannten Teilstu ̈cke verbindet.
3 Aufgabe – U ̈bersicht
In der vorliegenden Aufgabe soll eine stark vereinfachte Form des oben geschilderten Problems gelo ̈st werden. Diese Vereinfachungen betreffen drei Aspekte des Problems:
• Unterteilung der Karte: Die Karte in der Aufgabe wird sich aus vier Rechtecken mit iden-
tischen Abmessungen zusammensetzen. In realistischen Anwendungen haben die Teilkarten verschiedene Abmessungen, was die Implementation stark verkompliziert (siehe Abbildung 1).
1
Abbildung 1: Quelle: Wikimedia Commons
• Wegl ̈angen statt Wegen: Statt Wegen sollen in dieser Aufgabe lediglich Wegla ̈ngen ermittelt werden. Dies hat den entscheidenden Vorteil, dass Sie sich die no ̈tigen Techniken hierzu bereits in den Programmieraufgaben 6 und 7 erarbeitet haben. Dies bedeutet jedoch nicht, dass die vorliegende Aufgabe auf den letztgenannten aufbaut (siehe den na ̈chsten Punkt).
• Beschr ̈ankung auf Teilaspekte der Implementation: Sie werden Teile des Programmcodes zur Verfu ̈gung gestellt bekommen. Ihre Aufgabe wird es sein, unter genauen Instuktionen die Lu ̈cken des Programmes zu schließen.
Anmerkung: Diese Aufgabe dient auch als gedankliche Vorbereitung auf das na ̈chste Semester. In diesem werden Sie Techniken kennenlernen, mit denen sich die hier angerissene Problemstellung auf einem nochmals anderen Niveau bearbeiten la ̈ßt. Das Paradigma der objektorientierten Programmierung wird es Ihnen ermo ̈glichen, komplexe Programme sinnvoll zu strukturieren. Fortschrittlichere Algorithmen und Datenstrukturen (z.B. Ku ̈rzeste Wege Suche mittels des Dijkstra Algorithmus) werden es Ihnen erlauben, die hier geschilderten Teilprobleme effizienter und eleganter zu lo ̈sen.
3.1 Skizze des Wegfindungsalgorithmus
Die Karte, auf der die ku ̈rzesten Wege gefunden werden sollen, besteht aus vier Teilkarten, welche im Format der PA07 in einer Textdatei abgelegt sind. Der Algorithmus zur Bestimmung vieler ku ̈rzester Wege hat die Folgenden Grundbausteine:
• Extrahiere aus der besagten Textdatei die Teilkarten.
• Bilde zu jeder Teilkarte nach folgendem Rezept einen ungerichteten Graphen: Jedes Feld ’P’ im Rand der Teilkarte wird repra ̈sentiert einen Knoten vi. Zwecks Einfachheit der Notation identifizieren wir Felder mit den Knoten, die sie repra ̈sentieren.
Zu jedem Paar vi,vj mit i≠ j fu ̈ge dem Graphen die Kante (vi,vj) hinzu, falls innerhalb der Teilkarte ein Weg zwischen den beiden existiert. Das Gewicht der Kante ist die La ̈nge eines ku ̈rzesten Weges zwischen den beiden Knoten.
• Die Knoten der Teilgraphen entsprechen U ̈berga ̈ngen zwischen Teilkarten. Durch identifikation der U ̈bergangspunkte lassen die Teilgraphen sich zu einem einzelnen Graphen G zusammen- setzen. Lo ̈se fu ̈r diesen das All-pairs shortest path (APSP) Problem und speichere die Lo ̈sung.
2
• Gegeben einen Startpunkt s und einen Endpunkt t, welche nicht in derselben Teilkarte liegen, erga ̈nze G um die Knoten s und t. (Falls sie in derselben Teilkarte liegen, berechne den ku ̈rzesten Weg zwischen den beiden direkt.) Es seien v1,…,vk die Knoten von G in der Teilkarte, die s entha ̈lt. Fu ̈ge G eine Kante (s,vi) hinzu, falls ein Weg zwischen s und vi in der s enthaltenden Teilkarte existiert. Als Kantengewicht wa ̈hle die La ̈nge eines ku ̈rzesten Weges zwischen s und vi. Gehe fu ̈r t analog vor.
• Ermittle in dem so erga ̈nzten Graphen mit Hilfe der abgespeicherten Informationen u ̈ber ku ̈rzeste Wege in G die La ̈nge eines ku ̈rzesten Weges zwischen s und t.
4 Anforderungen
Sie erhalten eine Datei PA13solution_Students.py. Diese entha ̈lt eine Lo ̈sung der Auf- gabe, aus der einige Funktionen partiell oder vollsta ̈ndig entfernt wurden. Die Datei besteht aus drei Abschnitten – dem Hauptteil und zwei Teilen mit Hilfsfunktionen, die durch Kommentare vom Hauptteil abgetrennt sind. Die Hilfsfunktionen sind vollsta ̈ndig. Alle Lu ̈cken befinden sich im Hauptteil der Datei. Wir gehen nun auf die Funktionen dieses Teils ein. Funktionen, die der Vervollsta ̈ndigung bedu ̈rfen, werden mit einem Stern markiert.
4.1 Funktionen zur Erzeugung der verschiedenen Graphen
• extractPartialMaps() DieseHilfsfunktionextrahiertausderTextdatei students.in die Teilkarten. Jede Zeile einer Teilkarte wird in einer Liste von Strings mit den Werten U oder P abgelegt. Die Teilkarte wird als Liste solcher Listen gespeichert. Der Ru ̈ckgabewert der Funktion ist eine Liste der Teilkarten. Das obere linke Element der ersten Teilkarte ist dann, zum Beispiel, partialMaps[0][0][0] – wobei partialMaps der Name der Liste der Teilkarten ist. Die Teilkarten sind nach folgendem Schema nummeriert:
– Oben links: partialMaps[0].
– Oben rechts: partialMaps[1]. – Unten links: partialMaps[2]. – Unten rechts: partialMaps[3].
Alle Teilkarten haben immer die Abmessungen 7 Zeilen und 10 Spalten.
Anmerkung zur Umrechnung von Koordinaten: Ra ̈nder angrenzender Teilkarten werden miteinander identifiziert. Das heißt, in der Gesamtkarte sind, zum Beispiel, partial- Maps[0][0][9] und partialMaps[1][0][0] dasselbe Feld.
• verticesFromMaps(partialMaps)∗ Nimmt die Liste der Listen der Teilkarten entgegen. Fu ̈rjedeTeilkartewerdendieRand-Felderermittlet,diedenString P enthalten.Diesewerden im Format
(Index der Zeile, Index der Spalte)
in einer Liste abgelegt. Die so zusammengestellten Listen werden in einer Liste allVer- tices zusammengefasst und von der Funktion zuru ̈ckgegeben.
Anmerkung: Zur Sortierung der Knoten finden sich Instruktionen in der Lo ̈sungsschablone.
• edgesFromMaps(partialMaps, allVertices)∗ Fu ̈r jede Teilkarte partialMaps[i] wird das Folgende durchgefu ̈hrt: Fu ̈r jedes Paar von Tupeln vj,vk in allVertices[i], wobei vj ≠ vk, wird ermittelt, ob in partialMaps[i] ein Weg zwischen vj und vk existiert. Falls ja, wird die Information in folgendem Format in einer Liste (von gewichteten Kanten des der Teilkarte partialMaps[i] korrespondierenden Graphen) abgelegt:
3
[v_j,v_k, Länge des Weges]
Die Funktion gibt eine Liste allEdges von Listen von gewichteten Kanten zuru ̈ck.
Anmerkung: Zur Sortierung der Knoten finden sich Instruktionen in der Lo ̈sungsschablone. • generateTopVertices(partialMapsVertices) Erzeugt eine Liste von Knoten des Graphen G. Wir nennen G den Top-Graphen. Die Knoten werden im selben Format abgelegt, wie von der Funktion generateTopVertices. Es findet hier erstmals ein U ̈bergang von Betrachtungen in den Teilkarten zu Betrachtungen in der Gesamtkarte statt. Dies heißt insbesondere, dass Teilkarten-Koordinaten in Koordinaten in der gesamtkarte umgerechnet werden. Hierzu dienen die zwei Funktionen vertexShiftUp und vertexShiftDown
im Hilfsfunktionen-Abschnitt von PA13solution_Students.py.
Daru ̈ber hinaus ist zu beachten, dass alle Knoten aufgrund der oben erwa ̈hnten Ra ̈nder- Identifizierung doppelt vorkommen. Diese Doppelungen mu ̈ssen bereinigt werden.
• generateTopEdges(partialMapsEdges)∗ Generiert aus den Listen der gewichteten Kanten in partialMapsEdges eine Liste topEdges von gewichteten Kanten des Top- Graphen im selben Format und gibt diese zuru ̈ck. Die Koordinaten-Verschiebung kann, wie oben erwa ̈hnt, mit der Hilfsfunktion vertexShiftUp realisiert werden.
Es ist folgende Konvention zu beachten: Es sei [v,w,Gewicht] eine Kante in der Liste. Dann sollen v,w in der Reihenfolge abgelegt sein, die sich durch Sortierung der Liste [v,w] mittels sort() ergibt. Die restliche Sortierung der Eintra ̈ge der Liste wird durch die vorgegebenen Code-Snippets realisiert.
• generateTopMatrix(topVertices, topEdges) Gibt die Adjazenzmatrix des Top- Graphen zuru ̈ck. Die Matrix wird gegeben als Liste von Zeilen, wobei jede Zeile wiederum eine Liste ist. Da der Top-Graph ungerichtet ist, ist die Matrix symmetrisch. Folgende Konventionen sind zu beachten:
– Der Zeilen- bzw. Spaltenindex, der einem Knoten v entspricht, soll derselbe sein, wie der IndexdesKnotensvinderListe topVertices.HierzukanndieFunktion elemIndex im Hilfsfunktionen-Abschnitt genutzt werden.
– Die Liste topEdges kann Doppelkanten enthalten. In diesem Fall soll der niedrigere Gewichtswert in die Matrix eingetragen werden.
– Sind zwei Knoten nicht durch eine Kante verbunden, wird in den entsprechenden Feldern der String ’inf’ eingetragen. Ein mo ̈gliches Vorgehen ist, mittels der Hilfsfunktion infMatrix(n) aus dem Abschnitt Matrix-Operationen eine n×n Matrix mit ’inf’- Eintra ̈gen zu erzeugen und dann in den durch die Kanten in topEdges gegebenen Feldern das ’inf’ durch ein entsprechendes Kantengewicht zu ersetzen.
– Alle Diagonaleintra ̈ge werden auf 0 gesetzt. 4.2 All-pairs shortest path
Sie haben in der PA06 die min-plus Matrixmultiplikation kennengelernt. Fu ̈r die (symmetri- sche) Adjazenzmatrix A eines ungerichteten Graphen G=(V,E) mit positiven Kantengewichten gilt das Folgende: Es sei d eine positive ganze Zahl, so dass gilt Ad =Ad+1 =:B. Dann ist der Eintrag bij von B die La ̈nge eines ku ̈rzesten Weges zwischen vi und vj in G. Die Zahl d existiert immer und ist kleinergleich der Knotenzahl des Graphen G.
• allPairsShortestPath(adjacencyMatrix)∗ Nimmt eine Adjazenzmatrix entgegen und gibt eine Matrix mit ku ̈rzesten Wegen zuru ̈ck. Die zuru ̈ckgegebene Matrix hat dasselbe Format wie adjacencyMatrix, u ̈berschreibt diese aber nicht.
4
4.3 Erg ̈anzung um Start- und Zielknoten
Wir suchen nun den ku ̈rzesten Weg zwischen zwei Feldern s und t in der Gesamtkarte. Der interessante Fall ist, dass s und t nicht in derselben Teilkarte liegen. Fu ̈r diesen Fall sollen die Funktionen dieses Abschnittes das folgende Vorgehen realisieren:
• Es sei K die Teilkarte in der s liegt. Fu ̈r jedes Feld v mit Inhalt ’P’ im Rand von K
u ̈berpru ̈fe, ob in K ein Weg von s zu besagtem Feld existiert. Falls ja, fu ̈ge die gewichtete Kante
[s,v, Länge kürzester Weg von s zu v] einer Liste sEdges hinzu. Fu ̈hre die analoge Prozedur fu ̈r t durch.
• Es sei allPairs die Matrix, der die ku ̈rzesten Wege im Top-Graphen, wie oben geschildert, eingeschrieben sind. Es habe allPairs die Abmessungen n×n. Lege eine neue Matrix newAllPairs mit den Abmessungen (n+2)×(n+2) an, bette allPairs in die obe- re linke n×n Submatrix ein und befu ̈lle die zwei verbleibenden Zeilen/Spalten mit den Informationen aus sEdges und tEdges.
• Es sei I die Menge der Indizes der Knoten in topVertices, die weder mit s, noch t verbunden sind. Entferne fu ̈r alle i in I die Zeile und Spalte mit dem Index i aus newAllPairs.
• Lo ̈se fu ̈r das so reduzierte newAllPairs erneut das APSP Problem. Der vorletzte Eintrag der letzten Zeile (und der vorletzte Eintrag der letzten Spalte) ist die La ̈nge eines ku ̈rzesten Weges zwischen s und t.
Das so geschilderte Vorgehen wird mittels folgender Funktionen realisiert:
• generateAdjoiningEdges(vertex,allPartialMaps,allVertices) Nimmtein Karten-Feld im oben eingefu ̈hrten Format, sowie alle Teilkarten und Teilkarten-Knoten ent-
gegen. Gibt eine Liste gewichteter Kanten zur Erga ̈nzung des Top-Graphen zuru ̈ck. Die gewichteten Kanten haben das folgende Format:
[vertex, Knoten im Top-Graph, Kantengewicht]
• adjoinEdgesToMatrix(sEdges,tEdges,adjMatrix,topVertices)∗ Realisiert die im zweiten Punkt oben geschilderte Generierung der Matrix newAllPairs. Zur Zuordnung
der Knoten zu Indizes kann wiederum elemIndex genutzt werden. Es habe adjMatrix die Abmessungen n×n. Dann sollen die Informationen aus sEdges in die (n+1)-te Spalte mit dem Index n eingebettet werden und die Informationen aus tEdges in (n+2)-te Spalte mit dem Index n+1. Die u ̈bergebene Adjazenzmatrix soll nicht von der zuru ̈ckzugebenden Matrix newAllPairs u ̈berschrieben werden.
• extractSubmatrix(matrix, indices)∗ Entfernt fu ̈r alle Indices in indices die entsprechende Zeile und Spalte aus matrix. Hat als Ru ̈ckgabewert die reduzierte Matrix.
4.4 Synthese
Idealerweise sollten Sie in der Lage sein, die beschriebenen Teilfunktionen zu einer Funktion
synthPath(s,t,partMaps,partMapVertices,topVertices,allPairsMatrix)
zusammenzusetzen, deren Ru ̈ckgabewert die La ̈nge eines ku ̈rzesten s-t-Pfades ist. Dies wird jedoch nicht vom Comajudge abgefragt. Ich empfehle allerdings stark eine solche Funktion zu Ihrer eigenen U ̈bung zu programmieren.
5