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

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

Спасибо


java path vtk minimization
person Jon    schedule 03.12.2010    source источник
comment
Я глубоко подозреваю, что это близкий родственник коммивояжера и, таким образом, NP-полный.   -  person Adam Norberg    schedule 03.12.2010
comment
Что ж, это было бы бесполезно, можете ли вы придумать способ переформулировать задачу, чтобы она не была NP-полной?   -  person Jon    schedule 03.12.2010

Ответы (1)


arrow_upward
0
arrow_downward

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

person aronp    schedule 03.12.2010