A gardener considers aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is:
| | | | | | | | | |
On the other hand, the following configurations would be invalid:
| | | | | |
reason: 3rd tree should be higher than the 2nd one
| | | | | |
reason: consecutive trees cannot have the same height
Given a sequence of physical trees in a garden, what is the minimum number of physical trees which must be cropped/cut in order to achieve the pattern desired by that gardener?
First, the heights of the physical trees in the garden can be represented by a sequence of integers. For instance, the three examples above can be represented as (3 1 2 1 3), (3 2 1), and (3 3).
Mathematically speaking, the problem maps to find the minimum number of negative sums which must be applied to a sequence of integers (a0, a1, ..., aN) so that each pair of consecutive integers (ai, ai+1) in this sequence alternates between strictly decreasing (ai < ai+1) and strictly increasing (ai > ai+1) . Example: In (2, 3, 5, 7), the minimum number of negative sums is 2. A possible solution is to add -2 to the 2nd element and then add -3 to the last element, resulting in (2, 1, 5, 4).
My search model is a graph where each node represents a sequence of physical tree heights and each edge represents a decrease of the height of a tree (from now on called "cut"). In this model, a possible path from the initial node to the goal node in the above example would be
- initial node: (2,3,5,7)
- action: sum -2 to a1
- intermediate node: (2,1,5,7)
- action: sum -3 to a3
- goal node: (2,1,5,4).
I have used a breadth-first search to find the shortest path from the initial node to the goal node. The length of this shortest patch is equal to the minimum number of trees that must be cut.
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 "errors" in the sequence of integers in the node: triplets which do not match the required up/down pattern, ie. (ai < ai+1 and ai+1 < ai+2) OR (ai > ai+1 and ai+1 > ai+2), plus the number of consecutive equal numbers pairs (ai == ai+1) . This increases the probability that the goal node will be reachable from the first nodes with N-1 cuts in the queue when the times come to evaluate them. However, it is only useful to reduce the search space of nodes with N-1 cuts and not the complexity of the whole search.
The time required to execute this algorithm grows exponentially with the number of trees and with the height of the trees. Is there any algorithm/idea which could be used to speed it up?