Хороший алгоритм минимизации пути 2D в Java и VTK

Question

Я хотел бы найти алгоритм минимизации пути с некоторыми ограничениями в Java с VTK. В качестве входных данных я собираюсь дать площадь для многоугольника, которая является постоянной, центр масс многоугольника и изображение стоимости. В качестве результата я хотел бы получить список точек, которые составляют путь в 2D, который представляет собой минимальную длину пути на стоимостном изображении, удовлетворяющую двум ограничениям конкретной области и центра масс. Кто-нибудь знает способ сделать это с Java и VTK? Я смотрел на сборку vtkDijkstraImageGeodesicPath, но я не уверен даже, с чего начать. Честно говоря, моя математика в этой области ржавая.

Спасибо

Answer 1

Как уже упоминалось, это звучит как проблема путешествующего продавца. Один из способов найти разумные ответы - начать с трех узлов (только одно возможное решение), а затем для каждого последующего узла определить, где дешевле всего вставить узел в существующий путь. Он работает в n^2 раз и, конечно, не даст вам лучшего решения, но он должен дать разумные решения.