05 Fakultät Informatik, Elektrotechnik und Informationstechnik
Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6
Browse
70 results
Search Results
Item Open Access Fully-polynomial-time approximation schemes for the Euclidean shortest path problem(2024) Schneewind, AxelThe shortest path problem is a well-studied problem in computer-science. For transport networks, there exist natural graph representations and highly efficient algorithms that can compute shortest paths on millions of nodes within milliseconds. In contrast, computing shortest paths in space (e.g. in R^2) poses some challenges. Shortest path computations in space have applications in robotics, naval routing or video games. As shortest paths in a continuum are hard to compute (with the Euclidean shortest-path problem in 3D even proven to be NP-hard), approximations can be necessary to obtain acceptable runtimes. In this thesis, an approximation scheme is studied that guarantees solutions with cost at most (1+ε) times the optimum. It uses a triangulation of the domain and, given ε, construct a discretization. By performing a Dijkstra search, one can then approximate shortest paths with the given quality guarantee. This scheme is implemented and its practicality evaluated on larger instances.Item Open Access Experimentelle Bestimmung vergleichsoptimaler Sortieralgorithmen(2019) Obst, JulianDie gängigsten Sortierverfahren sortieren Mengen, indem sie zwei Elemente miteinander vergleichen und damit Schritt für Schritt eine Ordnung aufbauen. Es stellt sich die Frage, was die minimale Anzahl an Vergleichen ist, die benötigt wird, um eine beliebige Permutation einer Menge zu sortieren. Das zentrale Ziel dieser Arbeit ist es, die theoretischen Grundlagen zur Bestimmung vergleichsoptimaler Sortieralgorithmen zu erläutern und die Anzahl der Vergleiche von solchen Algorithmen zu bestimmen. Dabei werden auch die praktischen Ansätze besprochen, die benutzt wurden, um einen Algorithmus zu erstellen, der dieses Problem lösen soll. In diesem Zusammenhang werden die Aspekte der Implementierung dieses Algorithmus beleuchtet. Vor allem werden in diesem Punkt aber auch Optimierungen beschrieben, die helfen sollen, die Laufzeit zu verkürzen. Für n = 12, 13 konnten bekannte Ergebnisse bestätigt werden.Item Open Access Neue Bedienkonzepte für mobile Routenplaner(2014) Bahle, StefanieBei Routenplanern werden Start und Ziel typischerweise über eine Display-Tastatur eingegeben, was insbesondere bei Smartphones mit kleinem Display mühsam sein kann. Vor allem unter erschwerten Bedingungen, wie während der Fahrt auf dem Fahrrad oder mit Handschuhen, ist eine Eingabe über die Display-Tastatur kaum möglich. Aus diesem Grund wurden in dieser Arbeit Bedienmethoden entwickelt, welche die Bedienung unter erschwerten Bedingungen erleichtern sollen. Die Ansätze sind verschiedene Suchen mit zwei, drei oder vier Buttons zur Auswahl des Zielortes sowie eine Methode die die Lautstärketasten des Smartphones nutzt. Hierbei muss der gesuchte Ort alphabetisch eingeordnet werden und der entsprechende Button ausgewählt. Diese Bedienmethoden wurden in einer Benutzerstudie mit bekannten Eingabemethoden verglichen um festzustellen, ob die neuen Methoden eine bessere Alternative darstellen. Dies konnte zwar nicht bestätigt werden, dennoch sollte ein Weiterverfolgen der zugrunde liegenden Idee nicht ausgeschlossen werden.Item Open Access Experimental analysis of randomized calculations of average rankings(2016) Zeiß, TimListing a set of points, such that a point gets a higher rank, if none of its coordinates is smaller, creates a partial order. It is possible to get a ranking without randomly favoring certain points, by averaging all valid rankings. However, this brute force algorithm is too slow for more than ten points. To handle more points, we will give a randomized, approximative approach to solve this problem and analyze the convergence rates of different strategies.Item Open Access Das Geographiespiel in der Theorie und seine Realisierung als App(2013) Steinhart, DavidDas sogenannte "Geographiespiel" ist ein simples Spiel, welches dem Leser eventuell in einer Variante bekannt ist. Dabei nennen zwei Spieler abwechselnd Städtenamen, wobei diese jeweils mit dem Endbuchstaben der vorherigen Stadt beginnen müssen. Nennt Spieler A beispielsweise "Stuttgart", so kann Spieler B "Tübingen" als Antwort geben. Daraufhin wären "Nürnberg" oder "New York" mögliche Antworten. Das Ende des Spieles ist erreicht, wenn einem der beiden Spieler keine weitere Stadt einfällt und er somit das Spiel verliert. Bereits genannte Städte dürfen nicht erneut verwendet werden. Denkbar wäre auch eine Variante, in der Personen oder Automarken genannt werden. Beim Geographiespiel wird untersucht, welcher Spieler bei einer festgelegten Städteliste und optimaler Spielweise gewinnen wird. Das Spiel wird dahingehend erweitert, dass die Anzahl der Anfangs- und Endbuchstaben nun nicht mehr auf 26 festgelegt ist. Das Auswerten einer erweiterten Version des Spieles, die eine unbegrenzte Anzahl an Buchstaben zulässt, liegt in P-SPACE. Gibt es dagegen nur endlich vielen Buchstaben, liegt das Problem in P. Zudem ist es für sehr kleine Instanzen (nur 1 bzw. 2 Buchstaben) möglich, diese in logarithmischem Platz zu lösen. Ziel dieser Arbeit ist es, Instanzen mit endlich vielen Buchstaben genauer zu untersuchen. Einerseits wird der Fall mit 3 bzw. 4 Buchstaben betrachtet. Andererseits wird die Möglichkeit untersucht, das Auswertungsproblem für Schaltkreise auf das Geographiespiel mit endlich vielen Buchstaben zu reduzieren und so die P-Vollständig zu zeigen. Als praktischer Teil der Arbeit wurde das Geographiespiel als App implementiert. Dies dient der Untersuchung, mit welchem Aufwand und bis zu welchen Grad die Umsetzung realisierbar ist.Item Open Access Berechnung kürzester Wege mit negativen Kantenkosten(2024) Holtz, PatrickDas Kürzeste-Wege-Problem ist ein elementares Problem der Graphentheorie. Während sich für Graphen mit positiven Kantenkosten schon lange nahe-lineare Algorithmen wie der Dijkstra-Algorithmus etabliert haben, sind im Allgemeinen für Graphen mit beliebigen, also auch negativen Kantenkosten, nur Algorithmen mit schlechterer Komplexität bekannt. Bekannte Beispiele hierfür sind der Bellman-Ford Algorithmus oder der Goldberg-Algorithmus, die in O(nm) bzw. O(m√n log W ) laufen. Der 2022 vorgestellte Algorithmus von Bernstein et al. verspricht mit O(m log⁸(n) log W) erstmals eine nahe-lineare Komplexität, die die bestehenden Algorithmen in der Theorie verbessert. In dieser Arbeit wird Bernsteins Algorithmus vereinfacht und von Grund auf erklärt und eine praktische Implementierung vorgestellt. Außerdem wird durch Laufzeittests untersucht, wie Bernsteins Algorithmus im Vergleich mit ausgewählten bestehenden Algorithmen abschneidet. Die Tests erfolgen auf drei verschiedenen Graphklassen. Es konnte festgestellt werden, dass Bernsteins Algorithmus auf zufällig generierten Graphen mit etwa 106 Knoten um ein Vielfaches langsamer ist als eine effiziente Implementierung von Bellman-Ford (SPFA). Trotzdem konnte gezeigt werden, dass die nahe-lineare Komplexität erreicht wird. Somit ergibt sich bei der Anwendung auf praktische Probleme für Bernsteins Algorithmus kein Laufzeitvorteil, weshalb er die anderen Algorithmen erst bei weitaus größeren Eingabegraphen zeitlich überbieten kann.Item Open Access Improved approximation schemes for the restricted shortest path problem(2016) Holzmüller, DavidIn this thesis we present several variants of an approximation scheme for the restricted shortest path problem. This problem concerns finding a shortest path with respect to one criterion while not exceeding a length bound with respect to another criterion. After formally introducing the problem, we describe the approximation scheme by Lorenz and Raz. Our algorithm then introduces additional steps to reduce the runtime complexity from O(|E|n(1/epsilon + log log n)) to O(|E|n(1/epsilon + \log \log \log n)). A variant of this algorithm yields a complexity of O(|E|n(1/epsilon + (n log n) / m)), which is a further improvement for sufficiently dense graphs. Furthermore, a slight modification leads to an O(|E|n(1/epsilon + 1))-algorithm for directed acyclic graphs, providing an arguably easier algorithm than the algorithm proposed by Ergun et al.Item Open Access OSM ticket to ride(2022) Friedsam, WenzelBoard games such as Ticket to Ride by Days of Wonder use game boards which are based on real geographic data. In this particular example the game map is an abstract railway graph consisting of a set of train stations, that are connected by train routes. Generating such maps by hand is a long and time consuming process. Therefore we present an algorithm that can generate playable maps for the game Ticket to Ride for different countries and continents. The result of this work is an application which is able to automatically create a game graph using OpenStreetMap data as input. We try to keep the generated graph as similar as possible to the original game in terms of important metrics that affect the gameplay, while trying to keep the result close to the geographic data during the abstraction process. The result is exported into a format that can be imported by an open source web version of Ticket to Ride, which allows players to play on the generated map.Item Open Access Visualisierung großer Straßengraphen mittels Vulkan(2019) Bektas, SabriDas Ziel dieser Forschung ist es einen dreidimensionalen Straßengraphen in Globusdarstellung auf Basis der Vulkan Grafikkarten API zu erstellen. Die Vulkan API ist eine Computergrafikschnittstelle, die einen plattformunabhängigen Zugriff auf moderne GPUs ermöglicht. Als Grundlage für die Straßendaten dient die Geodatenbank OpenStreetMap, welche aus Längen- und Breitengrad aufgebauten Knotendaten liefert. Mithilfe dieser Datenform wird eine Globusdarstellung ermöglicht. Der auf Vulkan basierte Straßengraph bietet eine dynamische Änderung des angezeigten Graphen. Es können Straßenkategorien, wie zum Beispiel Autobahnen oder Landstraßen, ein- und ausgeblendet werden. Zuerst werden verwandte Arbeiten zu dem Vulkan basierten Straßengraphen vorgestellt. Nach einem allgemeinen Überblick auf Straßengraphen, werden die Grundlagen dieses Projekts nahegelegt. OpenStreetMap und ihre grundlegende Struktur der Daten bilden das erste Fundament der Grundlagen. Hier soll verdeutlicht werden, welche Daten für einen Straßengraphen von Bedeutung sind. Im Anschluss wird die Vulkan API analysiert, indem die spezifischen Vulkan Objekte erklärt werden. Nach dem vermittelten Grundwissen folgt die Offenlegung des vulkanbasierten Straßengraphen von der Entwicklungsumgebung über die verwendeten Bibliotheken bis hin zum Benchmarking des Programms. Auf dieser Grundlage ist es empfehlenswert die Vulkan API als Basis für Straßengraphen zu wählen. Die hardwarenahe Programmierung erfordert ein stabiles Grundwissen, kann jedoch für eine gesteigerte Effizienz in der Darstellung sorgen. Weiterführende Implementierung könnte sich mit Text- oder Flächendarstellung beschäftigen oder eine Überführung zu mobilen Endgeräten realisieren.Item Open Access Generierung von Minecraft Welten aus OpenStreetMap-Daten(2024) Dürr, FriedrichDiese Arbeit erforscht die Konvertierung von OpenStreetMap-Daten in spielbare Minecraft Welten. Durch die Nutzung von Höhendaten und Daten aus OpenStreetMap (OSM) wird eine nahtlose Integration von realen Straßen, Gebäuden und Geländemerkmalen in Minecraft ermöglicht. Der Fokus liegt auf der Automatisierung des Prozesses, um vom Nutzer ausgewählte OSM-Datensätze effizient in Minecraft zu übertragen. Verschiedene Herausforderungen wie Datenaufbereitung, Effizienz und Detailgenauigkeit werden untersucht, um realistische Minecraft-Welten zu schaffen. Die resultierenden Welten dienen nicht nur als unterhaltsame virtuelle Umgebungen, sondern auch als nützliche Schablone, um die echte Welt in Minecraft nachzubauen und als Werkzeug für städtische Planung und Geoinformatik-Anwendung.