English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphes et réseauxLe problème du vendeur ambulant
Pensons encore une fois aux réseaux et aux cartes. Imaginez qu'un service de livraison doive se rendre
Le camion de livraison doit visiter toutes les villes, dans n'importe quel ordre. Dans le problème des ponts de Königsberg, nous voulions trouver des chemins qui parcourent chaque bord exactement un. Nous voulons maintenant trouver des chemins qui visitent chaque sommet exactement une fois. Ces chemins s'appellent cycles hamiltoniens.
Il existe d'innombrables possibilités pour les cycles hamiltoniens dans des graphiques complets. En fait, nous pouvons choisir n’importe quel sommet comme sommet de départ, puis choisir l’une des villes restantes dans n’importe quel ordre:
Diagram coming soon…
Diagram Coming Soon…
Dans un graphique comportant
- ${tsmString(tsn1)}
Cela signifie qu’au total, il existe ${tsnPaths(tsn1)} chemins possibles. Un raccourci pour ce produit est ${tsn1}! ou ${tsn1} factoriel.
Vous pouvez imaginer qu'il ne serait pas possible de voyager directement entre deux villes sans passer par une autre ville. Dans ce cas, nous n’avons plus de graphique complet et il est beaucoup plus difficile de trouver le nombre de cycles d’Hamilton, s’ils existent.
Jusqu'ici, nous avons ignoré le fait que certaines villes pourraient être plus éloignées que d'autres. Cependant, dans la vie réelle, il s'agit d'une considération très importante: nous ne voulons pas simplement trouver un chemin mais nous voulons aussi trouver le chemin le plus court. Ce problème s'appelle le voyageur itinérant. Ce problème doit être résolu non seulement dans les domaines du transport et de la logistique, mais également lors du positionnement des transistors sur des puces, afin de rendre les ordinateurs plus rapides, ou lors de l'analyse de la structure de
Une méthode simple serait d'essayer tous les chemins possibles, en trouvant la longueur de chacun, puis en choisissant le plus court. Cependant, nous venons de montrer que, même avec seulement
Malheureusement, il n’existe pas d’algorithme plus efficace pour résoudre le problème du voyageur voyageur. Au lieu de cela, les mathématiciens et les informaticiens ont mis au point divers algorithmes permettant de trouver bonnes solutions, même s’ils ne sont pas forcément les meilleurs. Ces algorithmes, qui ne donnent que des solutions approximatives, sont appelés heuristiques.
Essayez de réorganiser les villes sur cette carte et observez l’évolution du chemin le plus court entre elles. Vous pouvez supprimer des villes en les touchant et vous pouvez ajouter des villes en cliquant n'importe où sur la carte (jusqu'à 8):
L’algorithme Greedy (ou l’algorithme du voisin le plus proche) est très simple: vous commencez dans une ville aléatoire et vous vous déplacez ensuite dans la ville la plus proche que vous n’avez jamais visitée. Une fois que vous avez visité toutes les villes, vous vous arrêtez.
Animation à venir…
Vous pouvez montrer qu'en moyenne, les chemins trouvés à l'aide de l'algorithme glouton sont 25% plus longs que le chemin le plus court possible.
L’algorithme 2-Opt commence par un chemin possible aléatoire. Ensuite, vous sélectionnez à plusieurs reprises deux bords et vous les échangez si cela réduisait la longueur du chemin. Vous vous arrêtez lorsque vous ne pouvez plus réduire la longueur en échangeant des paires d'arêtes.
Animation à venir…
Il se trouve que bien avant que les ordinateurs n'existent, la Nature avait trouvé un moyen intelligent de trouver des chemins optimaux entre différents lieux: dans des colonies de fourmis.
Les fourmis veulent trouver les itinéraires les plus courts possibles entre leur nid et les sources possibles de nourriture. Ils peuvent communiquer les uns avec les autres par le biais de produits chimiques qu’ils laissent le long de leur chemin et que les autres fourmis peuvent suivre.
- La colonie de fourmis envoie de nombreux éclaireurs qui se déplacent initialement dans des directions aléatoires. Une fois qu'ils ont trouvé de la nourriture, ils reviennent, laissant derrière eux une traînée de phéromone.
- Les autres fourmis ont tendance à suivre un sentier quand ils en trouvent un, ce qui les mène à la nourriture. À leur retour, ils déposent davantage de phéromone, renforçant ainsi le sentier.
- Au fil du temps, la phéromone s'évapore. Plus un chemin est long, plus les fourmis mettent du temps à le parcourir et la phéromone a donc plus de temps pour s'évaporer. Les chemins courts, en revanche, peuvent être renforcés plus rapidement, leur résistance augmente donc plus rapidement.
Schéma à venir…
Les algorithmes Ant Colony System (ACS) tentent de reproduire ce comportement sur des ordinateurs, en utilisant de nombreuses fourmis «virtuelles». Ils peuvent rapidement trouver de très bonnes solutions au problème du voyageur de commerce.
Une propriété particulièrement utile des algorithmes ACS est qu’ils peuvent être exécutés en continu et s’adapter en temps réel aux modifications apportées au graphique. Ces changements pourraient être causés par des accidents de voiture et des fermetures de routes sur les réseaux routiers, ou par des pics de trafic vers les serveurs Web sur des réseaux informatiques.
Le problème du voyageur de commerce est
Trouver un algorithme rapide et exact aurait de sérieuses implications dans le domaine de l'informatique: cela signifierait qu'il existe des algorithmes rapides pour tous les problèmes difficiles. Cela rendrait également la majeure partie de la sécurité Internet inutile, ce qui repose sur le fait que certains problèmes sont jugés très difficiles pour les ordinateurs.
Trouver un algorithme rapide pour résoudre le problème du voyageur voyageur résoudrait également l'un des problèmes les plus connus en mathématiques et en informatique, le problème P vs NP. Il s’agit de l’un des sept