Algorithme de minimisation du bon chemin 2D en Java et VTK

Question

Je voudrais trouver un algorithme de minimisation de chemin avec certaines contraintes en Java avec VTK. En entrée, je vais donner une zone pour le polygone qui est constante, le centre de masse du polygone et une image de coût. En sortie je voudrais une liste de points qui composent un chemin en 2D qui est la longueur de chemin minimale sur l'image de coût satisfaisant les deux contraintes de zone spécifique et de centre de masse. Est-ce que quelqu'un sait d'une manière de faire ceci avec Java et VTK? Je cherchais à construire à partir de vtkDijkstraImageGeodesicPath, mais je ne suis pas sûr même par où commencer. Honnêtement, mes maths dans ce domaine sont rouillés.

Merci

Answer 1

Comme mentionné il semble que le problème du voyageur de commerce. Une façon que j'ai trouvée pour obtenir des réponses raisonnables est de commencer avec trois nœuds (une seule solution possible) et ensuite, pour chaque nœud suivant, de déterminer où il est le moins cher d'insérer le nœud dans le chemin existant. Cela fonctionne dans n^2 temps et ne va certainement pas vous donner la meilleure solution, mais il devrait donner des solutions raisonnables.