Alors pour le coup, vu la dimension du bazar je ne suis pas sur que faire un recuit simulé avec une décroissance de la température à une vitesse pas trop brutale soit plus rapide qu'un A*. Ton problème étant absolument bourré de minimum locaux (la montage on la contourne par la droite ou par la gauche), que un au final la décroissance de la température que tu devra mettre pour avoir un résultat proche de l'optimal rend inutile le soit que tu as apporté à l'initialisation du SA. Ou alors tu fous un SA avec une decroissance tellement rapide de la température, que ton algo ça va quasiment être un algo glouton. En plus dans tous les cas, tu as un résultat non garanti (et non deterministe). Bref, je ne suis pas favorable.
En plus entre les nœuds de ton maillage, il est pas possible de calculer le chemin le plus court, le chemin étant dépendant des paramètres. Une solution serait de discrétiser l'espace des paramètres, et pour chaque jeu de parametres calculer les chemin les plus court. Non, beaucoup, beaucoup trop gros.
Bref, il y a moyen de faire mieux que ce que j'ai, mais pas avec cette methode je pense. Une manière d'obtenir un résultat plus rapidement, serait d'utiliser une heuristique non-admissible dans l'A*, de telle sorte à avoir une solution plus rapide, mais au coût de perdre la garantie d'optimalité.
[^] # Re: Recherche de plus court chemin
Posté par jben . En réponse au journal rv/hervé : recherche d’itinéraire vélo minimisant l'énergie en utilisant les données d'OSM. Évalué à 2.
Alors pour le coup, vu la dimension du bazar je ne suis pas sur que faire un recuit simulé avec une décroissance de la température à une vitesse pas trop brutale soit plus rapide qu'un A*. Ton problème étant absolument bourré de minimum locaux (la montage on la contourne par la droite ou par la gauche), que un au final la décroissance de la température que tu devra mettre pour avoir un résultat proche de l'optimal rend inutile le soit que tu as apporté à l'initialisation du SA. Ou alors tu fous un SA avec une decroissance tellement rapide de la température, que ton algo ça va quasiment être un algo glouton. En plus dans tous les cas, tu as un résultat non garanti (et non deterministe). Bref, je ne suis pas favorable.
En plus entre les nœuds de ton maillage, il est pas possible de calculer le chemin le plus court, le chemin étant dépendant des paramètres. Une solution serait de discrétiser l'espace des paramètres, et pour chaque jeu de parametres calculer les chemin les plus court. Non, beaucoup, beaucoup trop gros.
Bref, il y a moyen de faire mieux que ce que j'ai, mais pas avec cette methode je pense. Une manière d'obtenir un résultat plus rapidement, serait d'utiliser une heuristique non-admissible dans l'A*, de telle sorte à avoir une solution plus rapide, mais au coût de perdre la garantie d'optimalité.