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

Question

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

Спасибо

Answer 1

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