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

Question

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

Благодаря

Answer 1

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