Bon algorithme de minimisation de chemin 2D en Java et VTK

Question

Je voudrais trouver un algorithme de minimisation de chemin avec certaines contraintes en Java avec VTK. Comme entrée, je vais donner un espace pour le polygone qui est constant, 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 du chemin minimal sur l'image coût satisfaisant les deux contraintes de surface spécifique et le centre de masse. Est-ce que quelqu'un sait d'une façon de le faire avec Java et VTK? Je cherchais à construire hors de vtkDijkstraImageGeodesicPath, mais je ne suis pas sûr même où commencer. Honnêtement, mes maths dans ce domaine est rouillé.

Merci

Answer 1

Comme mentionné il semble que le problème de vendeur ambulant. Une façon que j'ai trouvé pour obtenir des réponses raisonnables est de commencer avec trois noeuds (une seule solution possible), puis pour chaque hors de travail de nœud suivant où il est moins cher d'insérer le nœud dans le chemin d'accès existant. Il fonctionne dans le temps n ^ 2 et ne va certainement pas vous donner la meilleure solution, mais il faut donner des solutions raisonnables.