problème du chemin le plus court

Le problème du chemin le plus court est un problème d'algorithme classique dans la recherche en théorie des graphes, visant à trouver le chemin le plus court entre deux nœuds dans un graphe (composé de nœuds et de chemins). Le problème du chemin le plus court est l’un des problèmes classiques dans le domaine de l’optimisation combinatoire. Il est largement utilisé dans de nombreux domaines tels que l’informatique, l’ingénierie des transports, l’ingénierie des communications, l’ingénierie des systèmes, la recherche opérationnelle, la théorie de l’information et la théorie du contrôle. L'algorithme de Dijkstra est un algorithme classique du plus court chemin.

Les formes spécifiques de l'algorithme incluent : (apprentissage recommandé : Tutoriel vidéo PHP)

Le problème de la détermination du chemin le plus court à partir du point de départ - c'est-à-dire le problème de trouver le chemin le plus court étant donné le nœud de départ.

Le problème de la détermination du chemin le plus court jusqu'au point final - Contrairement au problème de la détermination du point de départ, ce problème consiste à trouver le chemin le plus court étant donné le nœud final. Dans un graphe non orienté, ce problème est tout à fait équivalent au problème de détermination du point de départ. Dans un graphe orienté, ce problème est équivalent au problème de détermination du point de départ en inversant les directions de tous les chemins.

Le problème de déterminer le chemin le plus court du point de départ au point final - c'est-à-dire, étant donné le point de départ et le point final, trouver le chemin le plus court entre les deux nœuds.

Problème global du chemin le plus court - trouvez tous les chemins les plus courts dans le graphique.

Algorithme de Dijkstra

L'algorithme de Dijkstra est un algorithme classique de chemin le plus court. Son idée de base est de définir un ensemble S pour stocker les sommets du chemin le plus court qui ont été trouvés. , et l'état initial de S Il ne contient que le point source v. Pour vi∈V-S, on suppose que l'arête dirigée du point source v à vi est le chemin le plus court. Dans le futur, chaque fois qu'un chemin le plus court v, ..., vk est obtenu, vk est ajouté à l'ensemble S, et le chemin v, ..., vk, vi est comparé à l'hypothèse d'origine, et à celle avec la longueur de chemin la plus petite est choisie comme chemin le plus court, et le processus ci-dessus est répété jusqu'à ce que tous les sommets de l'ensemble V soient ajoutés à l'ensemble S. Cet algorithme est utilisé pour trouver le chemin le plus court globalement optimal. Lorsque le nombre de nœuds du réseau et le nombre de bords du réseau sont importants, il existe des inconvénients tels qu'une utilisation importante de la mémoire et une complexité temporelle élevée. De plus, l'algorithme de Dijkstra ne peut pas résoudre les problèmes. il faut bien passer les contraintes de point.

Algorithme de colonie de fourmis

L'algorithme de colonie de fourmis a été proposé pour la première fois par Dorigo, Maniezzo et Colorni en 1991. Il est dérivé du comportement de recherche de nourriture des fourmis. Grâce à des recherches, il a été découvert que les informations sont transmises entre les fourmis individuelles via un type de phéromone appelée phéromones. Les fourmis peuvent sentir l'intensité des phéromones environnantes pendant la marche et se déplacer dans la direction où la concentration de phéromones est élevée. Lorsqu'une fourmi trouve de la nourriture, elle libère des phéromones comme marque sur le chemin du retour au nid. Une fois que le compagnon l'a découverte, elle le fera. trouver de la nourriture le long de cette route. Lorsque plusieurs fourmis parmi les compagnons ont trouvé de la nourriture mais que la longueur du chemin est différente, parce que le temps nécessaire aux fourmis pour aller et venir sur le chemin court est relativement court, de plus en plus de fourmis traversent le chemin dans une unité de temps. la concentration de phéromones sera plus forte, il y aura donc de plus en plus de fourmis sur le chemin et un chemin optimal sera progressivement sélectionné.

Classification

peut être divisée en deux sous-problèmes, à savoir le problème du chemin le plus court à source unique et le problème du chemin le plus court entre toutes les paires de sommets. Le premier consiste à trouver le chemin le plus court entre un certain sommet et tous les autres sommets du graphe. Les principaux algorithmes incluent l'algorithme de Dixcher ; le second consiste à trouver le chemin le plus court entre chaque paire de sommets du graphe. .Algorithme allemand, etc.

Pour plus d'articles techniques liés à PHP, veuillez visiter la colonne Tutoriel graphique PHP pour apprendre !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!