I want to find the minimum number of tree cuts so that each pair of trees in a sequence of tree alternates between strictly decreasing and strictly increasing. Example: In (2, 3, 5, 7) , the minimum number of tree cuts is 2 – a possible final solution is (2, 1, 5, 4).

My search model is a graph where each node is a possible configuration of all tree heights and each edge is a tree cut (= a decrease of the height of a tree). In this model, a possible path from the initial node to the goal node in the above example would be (2,3,5,7) – (2,1,5,7) – (2,1,5,4). I have used a breadth-first search in it to find the goal node. As BFS don’t traverse already traversed nodes, the part of the graph that I traverse during the search is in fact a tree data structure.

The only improvement to this algorithm that I was able to think was using a priority queue that orders the possible nodes to be explored in increasing order 1st by number of cuts (as traditional BFS already does) and 2nd by the number of strictly increasing/decreasing triplets. This increases the probability that a goal node with the minimum number N of cuts will be within the first nodes of all nodes with N cuts to be evaluated and the search can finish a little faster.

The time required to execute this algorithm grows exponentially with the number of the trees and the height of the trees. Is there any other algorithm/idea which could be used to speed it up ?