Les algorithmes Gloutons

Les algorithmes gloutons désignent en programmations les algorithmes qui recherchent localement la meilleure solution, ils ne sont pas forcément les plus efficaces mais ne demandent que très peu de ressource pour fonctionne et sont très facile à implémenter.

 

A étoile

A étoile est un algorithme très connu dans le domaine de l’intelligence artificielle et de la robotique, il s’agit d’un algorithme glouton et donc parfaitement adapté à ces domaines. L’algorithme de A* est particulièrement utile pour résoudre un labyrinthe ou se déplacer dans un espace comportant des obstacles.

 

Dijkstra

L’Algorithme des Dijkstra est assez similaire à celui de A* puisqu’il s’agit également d’un algorithme glouton, il est principalement utilisé dans le domaine des itinéraires routier pour rechercher les trajets les plus courts d’un point A à un point B mais il est également très présent dans les protocoles de routages interne qui ont pour but de trouver les chemins optimaux entre un certain point d’un réseau informatique et les destinations atteignables à partir de ce point.

Prim

L’algorithme de Prim est un algorithme glouton et fait partie des plus coûteux en mémoire présenté ici mais il permet de parcourir tous les sommets d’un graphe en empruntant le chemin le plus court possible. Il peut être utilisé dans un grand nombre de domaine différents comme par exemple dans l’urbanisation ou en réseaux informatique ou l’on cherche à relier différents endroit / éléments avec la plus courtes distances / coût possible. Comme par exemple le déploiement de la fibre optique dans une zone, la création de parcours pour les transports en commun ou même simplement dans la création de réseaux informatiques.

 

Floyd-Warshall

L’algorithme de Floyd-Warshall est un algorithme permettant de trouver le plus court chemin dans des graphes orientés non pondérés en en déterminant les courtes distances entre toute la paire d’un graphe. Il a la particularité de décrire les graphes par des matrices d’adjacence et est principalement utilisé en réseaux.