TravelingSalesman¶
Purpose¶
The module TravelingSalesman tries to find the shortest path that visits all spatial positions of the XMarkers in the input XMarkerList.
In the output XMarkerList, the XMarkers are ordered according to the shortest path found. That is, the TravelingSalesman module can be used to order a set of points in a meaningful way, e.g., to reconstruct a curve from an unordered set of points.
NOTE: The algorithm takes a long time when more than 30 points are connected. Therefore, there is currently a limit of 30 input XMarkers.
Details¶
An exhaustive search is employed to find the shortest path. The search is pruned connecting only neighboring points. The number of neighbors to consider is given as a parameter by the user. With fewer neighbors to consider, the search is faster. However, a shorter path may be found if more neighbors are considered. Moreover, in some situations it is not possible to find a path at all when too few neighbors are considered.
Windows¶
Default Panel¶
Input Fields¶
inputXMarkerList¶
- name: inputXMarkerList, type: MLBase¶
An XMarkerList containing 1 to 30 XMarkers. If there are more than 30 input XMarkers, only the first 30 will be considered.
Output Fields¶
outputXMarkerList¶
- name: outputXMarkerList, type: MLBase¶
An XMarkerList with the same XMarkers as in the input XMarkerList (max 30), but ordered according to the shortest path.
If no path could be found, the output is empty.
Parameter Fields¶
Visible Fields¶
Update¶
- name: updateButton, type: Trigger¶
If pressed, the module computes anew.
Auto update¶
- name: autoUpdateToggle, type: Bool, default: TRUE¶
If checked, the module computes anew on any parameter or input change.
Number of Neighbors¶
- name: nbrNeighbors, type: Integer, default: 2¶
Sets the number of neighbors to consider when searching for the optimal path.
A lower value (2-3) makes the search significantly faster. With a larger number, a better path can in some situations be found. Moreover, with a low number of neighbors values there are situations where there is no path that visits all points. In this case, the output is empty.
Path Length¶
- name: pathLength, type: Double, default: 0¶
Shows the path length if a shortest path was found.