Locally Optimal Solutions in the Shortest Unclosed Path Search Problem
Egor E. Surkov, Oleg Seredin, Andrey Kopylov · 2023
The paper proposes methods for improving solutions of the shortest unclosed path (SUP) search problem by applying a brute force algorithm to parts of the path obtained by the greedy algorithms proposed in the previous work. This idea is basis for locally optimal solution applying. The auxiliary method is also described for the expanding the feasible domain of these algorithms. The work also proposes the selection of the several paths by the dissimilarity function for the further local optimization. This dissimilarity function defines a distance between two paths. The aim of the paths selecting is to search the paths which a more promising to improve. The paper compares the solutions obtained by several described algorithms for locally optimal solution applying. These algorithms allow to raise the results estimated in the previous work. This work also demonstrates multidimensional data visualization based on the shortest unclosed path by column chart of object distribution along the path and projection onto the path.