Dans Quelle Mesure Est-il Pratique De Laisser Un Professeur D’informatique Utiliser Un Algorithme Gourmand Pour Récupérer Un Véhicule Détourné ?

Par Super Neuro

Pendant les vacances de Noël de l'année dernière, Shi Yiyu, professeur associé titulaire et directeur de thèse au département d'informatique de l'université de Notre Dame, et également professeur associé titulaire au département d'électronique, a vécu une fouille de voiture de style hollywoodien.

Dans les 24 heures qui ont suivi le détournement de la voiture, le professeur Shi a utilisé la fonction de positionnement flou fournie par le véhicule lui-même pour approche gourmande, a localisé rapidement et précisément le véhicule et a récupéré sa voiture.

Examen de cas

 

South Bend 

Chicago

Déclencher

 

Pause déjeuner

Jour 1 00h00 Détournement de voiture Le professeur Shi s'est arrêté à une station-service pour gonfler les pneus. Alors que le professeur Shi vérifiait l'état de la voiture, deux gangsters en ont profité pour détourner la voiture. Pris de panique, le professeur Shi a secrètement mis son téléphone portable dans la poche derrière le siège.
	Jour 1 17h00 Commencer le suivi Après avoir appelé la police en vain, le professeur Shi a décidé de trouver lui-même l'emplacement de la voiture le plus rapidement possible. Je suis retourné à l’école et j’ai commencé à suivre, mais la localisation du téléphone n’était plus disponible.

Jour 2 5h00 positionnement flou Le professeur Shi a utilisé le système Mazda Mobile Start (MMS) intégré à la voiture pour trouver l'emplacement vague de la voiture, qui se trouvait à plus de 80 kilomètres de lui, avec une erreur système de 6 à 7 mètres.

Jour 2 7h00 À 60 mètres de distance ! Le professeur Shi a fait une déduction rapide grâce à l'algorithme glouton :Lorsque vous constatez que la distance relative ne diminue plus, arrêtez-vous à temps et continuez la recherche dans la direction verticale. Grâce à cette méthode, le professeur Shi a réduit la distance à seulement 60 mètres et a finalement réussi à localiser le véhicule avec précision dans un garage.

Jour 2 9h00 La police impuissante En attendant l'arrivée de la police, le professeur Shi et Xiao Wang ont découvert que les voleurs avaient peut-être remarqué quelque chose d'inhabituel et s'étaient enfuis. Le professeur Shi a remis le téléphone à la police et a continué à suivre le véhicule, mais la police n'a pas réussi à effectuer la recherche selon les instructions de l'algorithme du professeur Shi.

Jour 2 10h00 Récupérez votre voiture ! Après que le professeur Shi ait récupéré son téléphone portable, il a continué à utiliser son algorithme de recherche de voiture et a finalement trouvé la voiture volée dans un parking. La police a réussi à restituer la voiture au professeur Shi.

L'astuce ultime du professeur Shi pour chasser les voitures : l'algorithme gourmand

Cet incident de détournement de voiture tendu a été résolu en seulement 24 heures, tout cela grâce à l'exécution du professeur Shi et à la déduction précise de l'algorithme.

Même la police a été étonnée de la rapidité avec laquelle le professeur Shi a pu résoudre l’affaire :

« Ils n'auraient pas dû s'en prendre à des professeurs d'informatique ! Sont-ils stupides ? Comment ont-ils pu voler des professeurs d'informatique ? »

Le professeur Shi a expliqué que la technologie clé pour le positionnement des véhicules est en fait l’approche gourmande la plus directe des algorithmes informatiques.

Algorithme glouton,Également connu sous le nom d'algorithme glouton, c'est l'un des algorithmes les plus célèbres et les plus classiques en mathématiques et en informatique.

Lorsqu'il résout un problème, peu importe ce qui s'est passé avant ou après, il ne se soucie que de l'état actuel et n'obtient que la solution optimale pour le sous-problème actuel. Cependant, tant que la solution optimale locale obtenue à chaque fois peut être utilisée, la solution optimale globale ou la cible optimale peut être dérivée.

Le professeur Shi a appliqué l'algorithme glouton à la technique de recherche d'une voiture :
  Lorsque vous conduisez, si vous constatez que la distance relative entre vous et la voiture ne diminue plus, arrêtez immédiatement de conduire.
  Continuez ensuite la recherche dans le sens vertical.

Il s’agit d’une structure de recherche en spirale qui garantit qu’elle peut toujours converger vers une recherche monotone dans le sens d’une distance décroissante.

Ainsi, avec seulement deux personnes dans une voiture, le professeur Shi a rapidement localisé le véhicule volé grâce au guidage d'un logiciel de navigation avec une erreur de 3 kilomètres. L’algorithme glouton était l’outil le plus précis.

Autres applications classiques des algorithmes gloutons

En tant qu’algorithme classique, l’algorithme glouton n’est pas largement utilisé.

Parce que l'algorithme glouton ne peut atteindre la solution optimale globale qu'en résolvant la stratégie de solution optimale locale. Il faut donc se demander si le problème est adapté à la stratégie de l’algorithme glouton et si la solution trouvée est nécessairement la solution optimale au problème.

Par exemple, pour le problème du sac à dos et le problème du chemin, les algorithmes classiques suivants sont utilisés pour expliquer la beauté de la cupidité :

L'algorithme de DijkstraIl s'agit d'un algorithme de calcul du plus court chemin à source unique (SSSP) dans un graphe orienté pondéré, conçu par l'informaticien Edsger Dijkstra en 1956 et publié en 1959.

Les problèmes qu'il résout sont :
Étant donné un graphe G et un sommet source v, trouvez le chemin le plus court de v vers tous les sommets du graphe.

L'algorithme de Dijkstra est conçu à l'aide du paradigme de l'algorithme glouton :

Générez le chemin le plus court pour chaque sommet un par un dans l'ordre croissant de la longueur du chemin.Au cours de l'algorithme, un ensemble de sommets SS doit être maintenu, qui stocke les sommets pour lesquels le chemin le plus court a été trouvé. Il est également nécessaire de maintenir un tableau de distance dist, dist[i] représente la longueur de la distance entre le i-ème sommet et le nœud source s.

• Lorsque S est initialisé, il inclut uniquement le nœud source s ; dist[]dist[] est initialisé : dist[i]= arc[s][i], arc est la matrice d'adjacence du graphe. V−SV−S représente l’ensemble des sommets pour lesquels le chemin le plus court n’a pas été trouvé ;

• Mettez distdist dans l'ordre croissant, sélectionnez un chemin le plus court, ajoutez les sommets correspondants de V−SV−S à S, et chaque fois qu'un nouveau sommet u est ajouté à S, distdist doit être mis à jour, c'est-à-dire si s peut atteindre d'autres sommets plus proches via le sommet u. 
  Autrement dit, si dist[u] + arc[u][v] < dist[v], alors mettre à jour dist[v]=dist[u]+arc[u][v] 

• Répétez les étapes ci-dessus jusqu'à ce que S=VS=V 

Œuf de Pâques : Nouveau type de question de l'algorithme gourmand

C'était la fête nationale du pays H, et le roi a invité n ministres à jouer à un jeu avec des prix. Tout d'abord, il demanda à chaque ministre d'écrire un nombre entier sur sa main gauche et sa main droite, et le roi lui-même écrivit également un nombre entier sur sa main gauche et sa main droite.

Ensuite, laissez ces n ministres s'aligner en rangée, avec le roi debout à l'avant de l'équipe. Après s'être alignés, tous les ministres recevront un certain nombre de pièces d'or en guise de récompense de la part du roi. Le nombre de pièces d'or que chaque ministre reçoit est :Le résultat est le produit des nombres sur la main gauche de toutes les personnes devant le ministre, divisé par le nombre sur sa propre main droite, puis arrondi à l'inférieur.

Le roi ne veut pas qu'un ministre reçoive des récompenses particulièrement importantes, il aimerait donc que vous l'aidiez à réorganiser l'ordre de l'équipe afin que le ministre qui reçoit le plus de récompenses reçoive le moins de récompense possible.

(Notez que le roi est toujours en tête de la ligne.)