Guter Weg Minimierung Algorithmus 2D in Java und VTK

Question

Ich würde gerne einen Algorithmus für die Pfadminimierung mit einigen Einschränkungen in Java mit VTK finden. Als Eingabe gebe ich einen Bereich für das Polygon, das konstant ist, den Massenschwerpunkt des Polygons und ein Kostenbild an. Als Ausgabe möchte ich eine Liste von Punkten, die einen Pfad in 2D bilden, das ist die minimale Pfadlänge auf dem Kostenbild, die die zwei Beschränkungen der spezifischen Fläche und des Schwerpunkts erfüllt. Kennt jemand eine Möglichkeit, dies mit Java und VTK zu tun? Ich habe versucht, vtkDijkstraImageGeodesicPath aufzubauen, bin mir aber nicht sicher, wo ich anfangen soll. Ehrlich gesagt, meine Mathematik in diesem Bereich ist rostig.

Dank

Answer 1

Wie erwähnt es wie das Reisen Verkäufer Problem klingt. Eine Möglichkeit, vernünftige Antworten zu erhalten, besteht darin, mit drei Knoten (nur eine mögliche Lösung) zu beginnen und dann für jeden nachfolgenden Knoten herauszufinden, wo es am billigsten ist, den Knoten in den bestehenden Pfad einzufügen. Es funktioniert in 2 Stunden und wird sicherlich nicht die beste Lösung, aber es sollte vernünftige Lösungen geben.