On 2026-01-02 00:57, matt.egyhazy--- via Boost wrote:
done. Nearby Neighbors runs faster than the metric_tsp_approx but has more erratic solution (tour) performance. It also has some different characteristics as a local greedy solution vs. metric_tsp which creates an MST across the whole graph.
MST based solutions guarantee maximal factor of 2 as stated: https://www.boost.org/doc/libs/latest/libs/graph/doc/metric_tsp_approx.html BGL contains "10. Maximum Flow and Matching Algorithms" https://www.boost.org/doc/libs/latest/libs/graph/doc/table_of_contents.html Solution based on MST and a minimal matching guarantees maximal factor of 1.5, so would be interesting.
Is there any interest from the group in taking this heuristic as well as the LK? The LK will perform more slowly than metric_tsp_approx and much more slowly than Nearby Neighbors but also (on average) generate better tours.
Would be good to have that option. I moved a simple X11 graphics lib that stopped being updated back in 2007 to github. It contains an interactive LK TSP demo from the original author: https://github.com/Hermann-SW/ezxdisp/blob/main/samples/tsp_LK.c After start pi@raspberrypi5:~/ezxdisp/src/x11 $ ./tsp_LK clicking creates cities of the TSP. With more than 8 cities left click continues input of new cities, right click completes and starts animated LK solution. Perhaps that LK implementation can be helpful to inspect. What BGL functionality would be needed to create similar TSP (X11) graphics demo? Regards, Hermann.