I want to find the minimum number of tree trims so that each tree pair in a tree sequence alternates between a strict decrease and a strict increase. Example: In (2, 3, 5, 7) the minimum number of tree sections is 2 – a possible final solution is (2, 1, 5, 4).
My search model is a graph in which each node is a possible configuration of all tree heights and each edge is a tree cut (= a reduction in the height of a tree). In this model, one possible path from the starting node to the destination node in the above example would be (2,3,5,7) – (2,1,5,7) – (2,1,5,4). , I used a breadth first to find the destination node. Since BFS does not cross traversed nodes, the part of the diagram I traverse during the search is actually a tree data structure.
The only improvement to this algorithm that I was able to think about was the use of a priority queue that lists the possible nodes in ascending order one by number of cuts (as the conventional BFS already does) and two by the number of strikes increasing / decreasing knot orders triplets. This increases the likelihood that a target node with the minimum number N of slices will be within the first node of all nodes with N slices to be evaluated and the search can be completed somewhat faster.
The time required to execute this algorithm grows exponentially with the number of trees and the height of the trees. Is there any other algorithm / idea that could be used to speed this up?