Mathematik im Alltag: der Satellitennavigation
Der Satellitennavigator ist sicherlich ein sehr verbreitetes Werkzeug, und es wird oft angenommen, dass seine Funktion lediglich darin besteht, Informationen von Satelliten zu empfangen, die "den Weg weisen". In Wirklichkeit ist seine Fähigkeit, die Route zum Erreichen eines beliebigen Ziels festzulegen, das Ergebnis einer Kombination verschiedener Techniken, die die Fähigkeit betreffen, jederzeit genau zu identifizieren, wo wir uns befinden, die Verfügbarkeit genauer und aktualisierter Straßenkarten und vor allem die Fähigkeit, die beste Route zu berechnen, um unser Ziel zu erreichen. In diesem Artikel werden wir unsere Aufmerksamkeit auf diesen letzten Punkt richten und erklären, dass der Grundlage dieser Berechnung eine sehr genaue mathematische Theorie zugrunde liegt, die "Graphentheorie„So können wir nachvollziehen, wie es möglich ist, den kürzesten Weg zwischen zwei Punkten zu ermitteln. In der Praxis sehen wir, wie ein abstrakter wissenschaftlicher Begriff zur Grundlage eines praktischen, realen und vor allem sehr nützlichen Objekts wird.
Beginnen wir zunächst von unten: Was ist ein Graph?
In Wirklichkeit ist es nichts weiter als eine Menge von miteinander verbundenen Elementen: Jedes der Elemente wird als "Knoten" bezeichnet, und die Verbindungen werden als "Bögen" bezeichnet. Ein Beispiel für einen Graphen ist der, dessen Elemente eine Reihe von Städten sind, die über das Autobahnnetz miteinander verbunden sind. In diesem Fall sind die Knoten die Städte und die Bögen die Autobahnabschnitte zwischen den Städten. Wir können uns ein Diagramm als eine Reihe farbiger Kugeln oder Kreise (die Knoten) vorstellen, die durch Linien (die Bögen) miteinander verbunden sind. Ein Bogen kann orientiert oder nicht orientiert sein: Ein orientierter Bogen ist derjenige, der nur den Durchgang vom Startknoten zum Ankunftsknoten erlaubt (und nicht umgekehrt). Ein ungerichteter Bogen ermöglicht den Durchgang in beide Richtungen. In unserem Navigator-Beispiel kann eine Straße als orientierter Bogen betrachtet werden, wenn es sich um eine Einbahnstraße handelt, während sie als ungerichteter Bogen betrachtet werden kann, wenn es sich um eine Zweibahnstraße handelt.
Ein Graph wird als gewichtet bezeichnet, wenn jedem Bogen ein Wert zugeordnet ist, der als Gewicht bezeichnet wird. Dieser Wert kann im Allgemeinen positiv oder negativ sein. In Bezug auf das vorherige Beispiel von Städten und Autobahnen können wir ein gewichtetes Diagramm erhalten, indem wir jeden Autobahnabschnitt mit seiner Länge in Kilometern verknüpfen. In einem Diagramm ist es theoretisch möglich, mit verschiedenen Bögen auf verschiedene Weise von Knoten A zu Knoten B zu gelangen, genauso wie es in der Realität möglich ist, mit verschiedenen Straßen von einer Stadt zur anderen zu gelangen. Wir werden dann "kürzester Weg" den "kürzesten Weg" nennen, um Knoten A mit Knoten B zu verbinden.
Für unseren Satellitennavigator ist das Finden des Pfades zwischen dem Startpunkt und dem Endpunkt dasselbe wie das Finden des kürzesten Pfades innerhalb eines Diagramms. In der mathematischen Theorie der Graphen wurde das Problem der Berechnung des kürzesten Weges unter allen Gesichtspunkten untersucht und analysiert, und es werden viele Algorithmen erzeugt. Eine der am häufigsten verwendeten ist zum Beispiel Dijkstra-Algorithmus, aber es gibt viele andere. Es ist daher die Wahl des Browserherstellers, den Algorithmus zu wählen, den er für am besten geeignet hält. Bei dieser Auswahl muss sicherlich berücksichtigt werden, dass die Theorie, die der Suche nach dem kürzesten Weg zwischen zwei Knoten zugrunde liegt, sehr komplex sein kann, insbesondere wenn es darum geht, die Berechnung auf sehr komplexen Straßenkarten durchzuführen. Beispielsweise wurde der Algorithmus A * entwickelt, der unter Verwendung einer "statistischen Schätzung" für jeden Knoten nach dem kürzesten Weg sucht; In „schwierigen Worten“ ausgedrückt, stellt diese Schätzung die a priori Bewertung des Vorteils dar, auf dem Weg zum endgültigen Ziel durch einen Knoten gegenüber einem anderen zu gelangen. In jedem Fall wird das Eingehen auf die Details der Algorithmen etwas kompliziert und erfordert spezifisches Wissen. Wir hoffen auf jeden Fall, eine grundlegende Vision des Problems geliefert zu haben und vielleicht das Interesse an einer mathematischen Theorie mit vielen praktischen Auswirkungen auf den Alltag geweckt zu haben.
John Calcerano