Guter Weg Minimierungsalgorithmus 2D in Java und VTK

Question

Ich möchte einen Algorithmus zur Pfad Minimierung mit einigen Einschränkungen in Java mit VTK finden. Als Eingabe werde ich einen Bereich für das Polygon geben, die konstant ist, der Schwerpunkt des Polygons und eine Kosten Bild. Als Ausgabe würde ich eine Liste von Punkten wie die einen Weg in 2D komponieren, die die minimale Pfadlänge auf die Kosten Bild Erfüllung der beiden Bedingungen von bestimmten Gegend und das Zentrum der Masse ist. Kennt jemand eine Möglichkeit, dies mit Java und VTK zu tun? Ich war auf der Suche auf der vtkDijkstraImageGeodesicPath Gebäude aus, aber ich bin nicht sicher, auch wo ich anfangen soll. Ehrlich gesagt, meine Mathe in diesem Bereich ist rostig.

Danke

Answer 1

Wie bereits erwähnt es, wie der Wander Verkäufer Problem klingt. Eine Möglichkeit, die ich gefunden habe vernünftige Antworten zu bekommen, ist mit drei Knoten zu starten (nur eine mögliche Lösung) und dann für jeden nachfolgenden Knoten arbeiten, wo es am billigsten ist der Knoten in dem vorhandenen Pfad einzufügen. Es funktioniert in n ^ 2 Zeit und geht mit Sicherheit nicht, dass Sie die beste Lösung zu geben, aber es sollte vernünftige Lösungen geben.