05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Institute: search.filters.UBSInstitut.Institut für Formale Methoden der InformatikPublication Type: search.filters.UBSTyp.Abschlussarbeit (Master)

Search Results

Now showing 1 - 10 of 34
  • Thumbnail Image
    ItemOpen Access
    Performance measurements for personalizable route planning for uncorrelated edge costs
    (2021) Bühler, Felix
    Nowadays, ordinary route planners compute paths by choosing the shortest or fastest route. However, there exist additional metrics from which users with varying preferences could benefit. Personalized route planning offers the possibility to combine different metrics with personal preferences. Nevertheless, personalized route planning has mainly been tested with correlated metrics. But when including uncorrelated metrics, the computing time increases significantly. Previous work found that the speedup technique “Customizable Route Planning” can lead to feasible speedups for single metric calculations. Thus, in this work, we investigate how this speedup technique for Dijkstra improves the query performances of “Personalizable Route Planning” compared to “Personalizable Contraction Hierarchies”. Furthermore, we study the performances on uncorrelated metrics. We introduce a graph structure to compare the personalized speedup techniques “Personalizable Contraction Hierarchies”, “Personalizable Customizable Route Planning” and “Personalizable Route Planning”. Three graph partitioning algorithms have been implemented to realize “Customizable Route Planning”: K-means, Gonzales, and Merge. Our experiments show that Merge works well in combination with “Personalizable Contraction Hierarchies” preprocessing. We found that “Personalizable Customizable Route Planning” is a good alternative, as it uses much fewer edges for finding the costs of the shortest path. For uncorrelated metrics, “Personalizable Customizable Route Planning” and “Personalizable Route Planning” achieved speedups higher than “Personalizable Contraction Hierarchies”. Our contribution comprises a novel graph structure for comparing different Dijkstra variants. With our experiments, we provide a deeper understanding of the personalized route planning problem. Additionally, we propose improvements for “Personalizable Contraction Hierarchies” for less contracted graphs with uncorrelated metrics.
  • Thumbnail Image
    ItemOpen Access
    Das Ordnungsproblem für Automatengruppen und verwandte Fragestellungen
    (2019) Bühler, Andreas
    In dieser Arbeit werden Problemstellungen in der Klasse der Automatenhalbgruppen untersucht. Ein besonderer Augenmerk gilt dabei dem Ordnungsproblem welches im Allgemeinen sowohl für Automatenhalbgruppen als auch für Automatengruppen unentscheidbar ist. Es wird dann für die Klasse der Automatenhalbgruppen mit beschränkter Aktivität ein Algorithmus mit überraschend geringem Platzbedarf vorgestellt. Danach wird ein Entscheidungsalgorithmus für das Mitgliedschaftsproblem in ultimativ periodischen Teilmengen von Automatenhalbgruppen beschränkter Aktivität erarbeitet. Dieses Problem beinhaltet insbesondere das Mitgliedschaftsproblem in monogenen Unterhalbgruppen, welches dadurch ebenfalls in Automatenhalbgruppen beschränkter Aktivität entscheidbar ist.
  • Thumbnail Image
    ItemOpen Access
    Multi-criteria bicycle routing
    (2018) Barth, Florian
    This thesis considers the problem of finding alternative routes by weighting multiple metrics. This approach has the benefit that it always yields a Pareto optimal path. These routes have to be then checked against a similarity measure to ensure that they are different enough for a user to consider them helpful. The Splitting Algorithm designed in this thesis uses a geometric intuition to explore the possible weightings and find good alternative routes heuristically. To achieve fast query times although many routes need to be calculated and compared, the algorithm builds upon the multi-criteria version of the contraction hierarchies speed-up technique. In an implementation for cyclists with three metrics, the algorithm found up to thirteen routes that share less than 50% of their length and four or five routes in half the cases.
  • Thumbnail Image
    ItemOpen Access
    Generierung und Abdeckung repräsentativer Pfadmengen in Straßennetzwerken
    (2022) Berner, Lukas
    Für die Suche nach kürzesten Pfaden in sehr großen Graphen wurden verschiedene Beschleunigungstechniken, wie z.B. Contraction Hierarchies, Hub-Labels oder Transit Node Routing, entwickelt. Um optimale Anfragezeiten und Speicherverbrauch zu erreichen, benötigen viele Beschleunigungstechniken eine Menge wichtiger Knoten. In dieser Arbeit wird eine Methode zur Berechnung wichtiger Knoten eines Graphen vorgestellt. Um diese Knoten zu finden, wird auf einer repräsentativen Pfadmenge ein Hitting Set Problem mit einem Greedy-Algorithmus gelöst. Die repräsentative Pfadmenge, die möglichst unterschiedliche kürzeste Pfade des Graphen enthalten soll, wird mit einer well-separated pair decomposition und einem Quadtree berechnet. Das Verfahren wurde mit dem deutschen Straßennetzwerk (25M Knoten) getestet und liefert hier einige tausend wichtige Knoten, mit denen bereits etwa 99,9 % aller kürzesten Pfade im Graph abgedeckt sind.
  • Thumbnail Image
    ItemOpen Access
    Contraction Hierarchies für kontinuierliche Graphsimplifizierung mit Qualitätsgarantien
    (2016) Rupp, Tobias
    Moderne Navigationsdienste können kürzeste Pfade berechnen und diese dann auf Straßenkarten anzeigen. Als zugrunde liegende Datenstruktur für beide Aufgaben kann eine Contraction Hierarchy verwendet werden. Ursprünglich waren Contraction Hierarchies dazu konzipiert, die Suche nach kürzesten Pfaden zu beschleunigen. In dieser Arbeit wurde untersucht, wie sich Contraction Hierarchies aufbauen lassen, sodass sie sich besser für kontinuierlich vereinfachte Darstellungen eignen. Dazu sollten vor allem die groben Straßenverläufe erhalten bleiben und topologische Inkonsistenzen wie Überschneidungen vermieden werden. Diese Anforderungen wurden formalisiert und in heuristischen Vereinfachungsalgorithmen zum Aufbau von Contraction Hierarchies umgesetzt. Für kleine Eingaben wurden mithilfe ganzzahliger linearer Programme garantiert optimale Lösungen berechnet. Damit konnten in empirischen Vergleichen auf dem Deutschlandgraphen Qualitätsgewinne nahe dem Optimum für vereinfachte Darstellungen von Contraction Hierarchies nachgewiesen werden. Außerdem mussten keine längeren Berechnungszeiten für kürzeste Pfade hingenommen werden.
  • Thumbnail Image
    ItemOpen Access
    Verbotsmuster für Logik mit zwei Variablen über endlichen und unendlichen Wörtern
    (2023) Heindl, Amelie
    Die Varietät DA, die mit der Logik erster Stufe über zwei Variablen übereinstimmt, bildet das höchste Level der Trotter-Weil-Hierarchie. Varietäten in dieser Hierachie können algebraisch über l-Gleichungen charakterisiert werden und haben teilweise äquivalente Klassen in der Quanto- renalternierungshierarchie innerhalb FO2. Um Sprachen mit diesen Klassen in Verbindung zu bringen, ist es möglich, das syntaktische Monoid auszurechnen und für alle möglichen Belegungen die l-Gleichung zu überprüfen. Aus komplexitätstheoretischer Sicht ist dieser Ansatz aufwändig und diese Arbeit befasst sich mit Kriterien, mit denen man die gesuchte Verbindung direkt auf den Automaten der Sprachen prüfen kann. Das zentrale Konzept stellen dabei Verbotsmuster dar. In dieser Arbeit wird eine Definition für Verbotsmuster bei nicht notwendigerweise minimalen DEAs und CMAs gegeben. Damit werden explizite Verbotsmuster für Sprachen über endlichen Wörtern für die Varietäten an den Enden der Hierarchie konstruiert und ein allgemeines Schema für die inneren Level angepasst. Aus diesen Mustern werden Verbotsmuster für fin-syntaktische Monoide von Sprachen über unendlichen Wörtern abgeleitet. Zusammen mit einem Verbotsmus- ter, das die Zugehörigkeit zu DA für inf-syntaktische Monoide entscheidet, lässt sich damit die Trotter-Weil-Hierarchie vollständig für DEAs und CMAs charakterisieren. Für alle konstruierten Verbotsmuster werden NL- und P-Algorithmen erstellt, die Automaten auf das Enthalten dieser Verbotsmuster prüfen. Dies beinhaltet sowohl Algorithmen, bei denen ein festes Verbotsmuster gegeben ist, als auch Algorithmen, bei denen es Teil der Eingabe ist. Für die Varietäten der Trotter-Weil-Hierarchie existieren auch Verbotsmuster mit Teilwortbeziehungen, die von Henriksson und Kufleitner definiert wurden. Die beiden Verbotsmusterarten werden in dieser Arbeit verglichen. Dabei werden insbesondere die Größen der Muster, die Komplexitätsschranken der Algorithmen und die gefundenen Zeugen berechnet. Es ergibt sich ein Größenvorteil der Teilwortmuster gegenüber den Faktormustern bei vergleichbaren Komplexitäten der Algorithmen.
  • Thumbnail Image
    ItemOpen Access
    Simulation and analysis of complex dynamics in a low-dimensional model of a vibration-machine
    (2021) Roggenbuck, Kay
    In the past decades, the importance of discontinuous piecewise-smooth models has been well-established. So far, the dynamics of such models are mostly analyzed based on functions with a single point of discontinuity. This class of functions is well-investigated in the literature and many theoretical results are known. Even though many physical phenomena can be described by this class, for more complex systems, a single point of discontinuity is not sufficient. In this thesis, this theory is extended by the analysis of a map in which the number of discontinuities varies based on different parameters. It is shown that this map does for integer-valued parameters result in clear dynamics, e.g. a sausage-shaped period-adding cascade. Even though these structures are already known in the literature, the understanding of its dynamics is key for the analysis of the structures for a more generalized range of parameter values. For example, for real-valued parameters the map show a much more complex structure consisting of a combination of period-adding and period-incrementing with different coexistence scenarios. Furthermore, it is shown that the iteratively increasing of a parameter related to the number of discontinuities destroys the sausage-shaped structure and transforms it for the next higher integer value to a more complex sausage-shaped structure. It is investigated how this structure is destroyed and how it evolves in the intermediate steps. Additionally, in this new structure an example configuration of the model is found where well-established results from a map with one discontinuity can not be applied.
  • Thumbnail Image
    ItemOpen Access
    Integration of CH/HL-based route planning in OSCAR
    (2020) Makolli, Sokol
    Efficient and fast shortest path routing on road networks is required to meet the demands of millions of users every day. In this work we document an implementation, which combines two popular speed up techniques. The results show that with little space overhead a speed up of one order of magnitude to conventional techniques is achievable, while also giving the choice of using either disk or RAM storage. The routing application is also integrated into the search engine OSCAR, which then allows for interactive exploration of locations along the route.
  • Thumbnail Image
    ItemOpen Access
    Analyse von Algorithmen zur Bahnverbindungssuche
    (2014) Wang, Mingyuan
    Diese Arbeit liefert einen Einblick in die Thematiken der elektronischen Fahrplanauskunft und beschreibt den Aufbau eines einfachen Reiseplanungs-systems. Vorteile des time-expanded- und time-dependent-Modells werden dabei kombiniert und ein dafür geeignet angepasster Dijkstra-Algorithmus vorgestellt. Des Weiteren beschäftigt sich die Arbeit mit der Analyse und dem Vergleich von HAFAS, einem gängigen Reiseplanungssystem, und dem Verbindungssuchalgorithmus von PRIMA, einem Nachfrageprognosemodell der Deutschen Bahn AG. Optimierungsvorschläge zum verbesserten Prognosepotenzial von PRIMA werden unterbreitet.
  • Thumbnail Image
    ItemOpen Access
    The Generalized Minimum Manhattan Network Problem
    (2015) Schnizler, Michael
    In this thesis we consider the Generalized Minimum Manhattan Network Problem: given a set containing n pairs of points in R2 or Rd, the goal is to find a rectilinear network of minimal length which contains a path of minimal length (a so-called Manhattan path) between the two points of each pair. We restrict our search to a discrete subspace and show that under specific conditions an optimal solution can be found in polynomial time using a dynamic program. The conditions concern the intersection graph of the bounding boxes of the pairs. Its maximum degree as well as the treewidth must be bounded by two constants which are independent of n. Finally, we present a simple greedy algorithm for practical purposes.