Wie Praktikabel Ist Es, Einen Informatikprofessor Einen Greedy-Algorithmus Zur Bergung Eines Entführten Fahrzeugs Verwenden Zu Lassen?

Von Super Neuro

Während der Weihnachtsfeiertage im letzten Jahr wurde Shi Yiyu, außerordentlicher Professor und Doktorvater im Fachbereich Informatik der University of Notre Dame und außerordentlicher Professor im Fachbereich Elektronik, Opfer einer Autodurchsuchung im Hollywood-Stil.

Innerhalb von 24 Stunden nach der Entführung des Autos nutzte Professor Shi die Fuzzy-Positionierungsfunktion des Fahrzeugs selbst, um gieriger Ansatz, lokalisierte das Fahrzeug schnell und präzise und bekam sein Auto zurück.

Fallüberprüfung

 

South Bend 

Chicago

Losfahren

 

Mittagspause

Tag 1 00:00 Uhr Carjacking Professor Shi hielt an einer Tankstelle, um den Reifendruck zu erhöhen. Als Professor Shi den Zustand des Autos überprüfte, nutzten zwei Gangster die Gelegenheit, das Auto zu entführen. In Panik steckte Professor Shi heimlich sein Mobiltelefon in die Tasche hinter dem Sitz.
	Tag 1 17:00 Uhr Starten Sie die Verfolgung Nachdem sein Anruf bei der Polizei vergeblich war, beschloss Professor Shi, den Standort des Autos so schnell wie möglich auf eigene Faust herauszufinden. Ich kehrte zur Schule zurück und begann mit der Ortung, aber der Standort des Telefons war nicht mehr verfügbar.

Tag 2 5:00 Uhr Fuzzy-Positionierung Professor Shi nutzte das im Auto eingebaute Mazda Mobile Start (MMS), um den ungefähren Standort des Autos zu bestimmen, der mehr als 80 Kilometer von ihm entfernt war, mit einem Systemfehler von 6-7 Metern.

Tag 2 7:00 Uhr 60 Meter Abstand! Professor Shi zog mithilfe des Greedy-Algorithmus eine schnelle Schlussfolgerung:Wenn festgestellt wird, dass die relative Entfernung nicht mehr abnimmt, stoppen Sie rechtzeitig und setzen Sie die Suche in vertikaler Richtung fort. Mit dieser Methode konnte Professor Shi die Distanz einmal auf nur 60 Meter reduzieren und es schließlich präzise in einer Garage orten.

Tag 2 9:00 Uhr Polizei machtlos Während sie auf das Eintreffen der Polizei warteten, stellten Professor Shi und Xiao Wang fest, dass den Räubern möglicherweise etwas Ungewöhnliches aufgefallen war, und fuhren davon. Professor Shi übergab der Polizei das Telefon und verfolgte das Fahrzeug weiter, doch die Polizei führte die Suche nicht gemäß den Anweisungen des Algorithmus von Professor Shi durch.

Tag 2 10:00 Uhr Holen Sie sich Ihr Auto zurück! Nachdem Professor Shi sein Mobiltelefon wiedererlangt hatte, nutzte er weiterhin seinen Autosuchalgorithmus und fand das gestohlene Auto schließlich auf einem Parkplatz. Der Polizei gelang es, Professor Shi das Auto zurückzugeben.

Professor Shis ultimativer Trick bei der Autoverfolgung: Der Greedy-Algorithmus

Dieser spannende Carjacking-Vorfall konnte dank Professor Shis Ausführung und präziser algorithmischer Ableitung innerhalb von nur 24 Stunden aufgeklärt werden.

Sogar die Polizei war erstaunt, wie schnell Professor Shi die Angelegenheit klären konnte:

„Sie hätten sich nicht mit Informatikprofessoren anlegen sollen! Sind sie dumm? Wie konnten sie Informatikprofessoren ausrauben?“

Professor Shi erklärte, dass die Schlüsseltechnologie zur Positionierung von Fahrzeugen tatsächlich der direkteste Greedy-Ansatz in Computeralgorithmen sei.

Greedy-Algorithmus,Auch als Greedy-Algorithmus bekannt, ist er einer der bekanntesten und klassischsten Algorithmen in der Mathematik und Informatik.

Wenn es ein Problem löst, kümmert es sich, unabhängig davon, was vorher oder nachher passiert ist, nur um den aktuellen Zustand und erhält nur die optimale Lösung für das aktuelle Teilproblem. Solange jedoch die jeweils erhaltene lokale Optimallösung verwendet werden kann, kann die globale Optimallösung oder das optimale Ziel abgeleitet werden.

Professor Shi hat den Greedy-Algorithmus auf die Technik zur Autosuche angewendet:
  Wenn Sie beim Fahren feststellen, dass der relative Abstand zwischen Ihnen und dem Auto nicht mehr abnimmt, hören Sie sofort auf zu fahren.
  Setzen Sie die Suche anschließend in vertikaler Richtung fort.

Dabei handelt es sich um eine spiralförmige Suchstruktur, die dafür sorgt, dass bei einer monotonen Suche immer in Richtung abnehmender Distanz konvergiert werden kann.

So gelang es Professor Shi schließlich, mit nur zwei Personen im Auto und mithilfe einer Navigationssoftware das gestohlene Fahrzeug schnell zu orten, allerdings mit einer Fehlerquote von 3 Kilometern. Der Greedy-Algorithmus war das genaueste Tool.

Andere klassische Anwendungen von Greedy-Algorithmen

Als einer der klassischen Algorithmen wird der Greedy-Algorithmus nicht häufig verwendet.

Denn der Greedy-Algorithmus kann die globale Optimallösung nur erreichen, indem er die lokale Optimallösungsstrategie löst. Daher müssen wir darauf achten, ob das Problem für die Strategie des Greedy-Algorithmus geeignet ist und ob die gefundene Lösung unbedingt die optimale Lösung des Problems ist.

Beispielsweise werden beim Rucksackproblem und beim Pfadproblem die folgenden klassischen Algorithmen verwendet, um die Schönheit der Gier zu erklären:

Dijkstras AlgorithmusEs handelt sich um einen Algorithmus zur Berechnung des kürzesten Pfades aus einer Quelle (SSSP) in einem gewichteten gerichteten Graphen, der 1956 vom Informatiker Edsger Dijkstra konzipiert und 1959 veröffentlicht wurde.

Die Probleme, die es löst, sind:
Gegeben sei ein Graph G und ein Quellknoten v. Finden Sie den kürzesten Pfad von v zu allen Knoten im Graphen.

Der Dijkstra-Algorithmus basiert auf dem Greedy-Algorithmus-Paradigma:

Generieren Sie nacheinander den kürzesten Pfad für jeden Scheitelpunkt in der Reihenfolge zunehmender Pfadlänge.Während des Algorithmus muss ein Knotensatz SS gepflegt werden, der die Knoten speichert, für die der kürzeste Pfad gefunden wurde. Es ist auch notwendig, ein Distanzarray dist beizubehalten, dist[i] stellt die Distanzlänge zwischen dem i-ten Scheitelpunkt und dem Quellknoten s dar.

• Wenn S initialisiert wird, enthält es nur den Quellknoten s; dist[]dist[] wird initialisiert: dist[i]= arc[s][i], arc ist die Adjazenzmatrix des Graphen. V−SV−S stellt die Menge der Knoten dar, für die der kürzeste Pfad nicht gefunden wurde;

• Ordnen Sie distdist in aufsteigender Reihenfolge an, wählen Sie einen kürzesten Pfad aus, fügen Sie die entsprechenden Scheitelpunkte von V−SV−S zu S hinzu und jedes Mal, wenn ein neuer Scheitelpunkt u zu S hinzugefügt wird, muss distdist aktualisiert werden, d. h., ob s andere Scheitelpunkte näher über Scheitelpunkt u erreichen kann. 
  Das heißt, wenn dist[u] + arc[u][v] < dist[v], dann aktualisiere dist[v]=dist[u]+arc[u][v] 

• Wiederholen Sie die obigen Schritte, bis S=VS=V 

Easter Egg: Neuer Fragetyp des Greedy-Algorithmus

Es war zufällig der Nationalfeiertag des Landes H und der König lud n Minister zu einem Spiel mit Preisen ein. Zunächst bat er jeden Minister, eine ganze Zahl auf seine linke und rechte Hand zu schreiben, und auch der König selbst schrieb eine ganze Zahl auf seine linke und rechte Hand.

Dann lassen Sie diese n Minister in einer Reihe aufstellen, wobei der König an der Spitze des Teams steht. Nach dem Aufstellen erhalten alle Minister vom König eine Anzahl Goldmünzen als Belohnung. Die Anzahl der Goldmünzen, die jeder Minister erhält, beträgt:Das Ergebnis ist das Produkt der Zahlen auf den linken Händen aller Personen vor dem Pfarrer, geteilt durch die Zahl auf seiner eigenen rechten Hand und dann abgerundet.

Der König möchte nicht, dass ein Minister besonders große Belohnungen erhält. Deshalb möchte er, dass Sie ihm dabei helfen, die Reihenfolge des Teams so umzugestalten, dass der Minister, der die meisten Belohnungen erhält, so wenig Belohnung wie möglich erhält.

(Beachten Sie, dass der König immer vorne in der Reihe steht.)