A software package for finding an optimal piecewise rectilinear route with n turns

Abstract

Context and relevance. There are practically significant problems requiring connecting two given points in a plane with a piecewise rectilinear polyline. Various constraints on the desired polyline are possible, including a limit on the number of links n and on the absolute value of the rotation angles at the breakpoints. In the simplest discrete case, the turning points belong to a finite set containing N elements. A complete enumeration of all possible solutions is an NP-hard problem and may require searching through variants. However, approaches are possible that significantly narrow the set of feasible solutions. One such approach is to use an exact formula describing the set of all polylines (described as a sequence of n turning points) that satisfy a given constraint on the absolute value of the rotation angles. In this case, the feasible domain is successively significantly narrowed for each subsequent rotation. As a result, an algorithm for enumerating the elements of precisely such a set will perform many times faster than an exhaustive search algorithm. Objective. Implement an algorithm for enumerating a set of feasible solutions according to a precise formula. Hypothesis. To implement an algorithm that enumerates the set of feasible solutions according to the exact formula. Methods and materials. The software package that implements the search algorithm was developed to work with images representing a route complexity map. After setting the angle constraint and specifying the required number of turns, the package applies an enumeration algorithm over the set of feasible solutions using the exact formula obtained by dynamic programming. Results. Experiments were conducted on four maps with the number of turns equal to 2, 3, and 4. The algorithm enumerating the set of feasible routes showed a significant advantage over simple -fold enumeration of the elements of . A cubic dependence of the algorithm’s running time on the maximum turning angle was experimentally established. Conclusions. The developed algorithm is many times faster than simple enumeration and allows solving a large number of problems in an acceptable time.