2
$\begingroup$

A gardener consider 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 the trees and with the height of the trees. Is there any algorithm/idea which could be used to speed it up ?

$\endgroup$
  • $\begingroup$ @D.W. I have edited the question. This problem is about a sequence of physical trees (eg palm trees). The previous descriptions was ambiguous because both the physical plant and the Computer Science data structure have the same name. I hope it is clearer now. $\endgroup$ – Alan Evangelista Nov 8 at 20:54
1
$\begingroup$

I'll describe two ways you could solve this problem. Either works. In some sense they are basically the same algorithm, just viewed from two different perspectives.

Dynamic programming algorithm

This can be solved in linear time with dynamic programming. Let $d_i$ denote minimum number of $a_i,\dots,a_n$ that must be cut to produce an alternating sequence if you start in the downwards direction for the first pair (the pair $a_i,a_{i+1}$) and don't cut $a_i$, and $u_i$ the minimum number to produce an alternating sequence starting in the upwards direction if you don't cut $a_i$, and $u'_i$ the minimum number to produce an alternating sequence starting in the upwards direction if you do cut $a_i$. Then you can write down a recurrence relation that expresses $d_i,u_i,u'_{i+1}$ in terms of $d_{i+1},u_{i+1},u'_{i+1}$, and you can evaluate it in $O(n)$ time using dynamic programming.

In particular, the recurrence relation is $u'_i = 1 + d_{i+1}$ and

$$d_i = \begin{cases} \min(u_{i+1},u'_{i+1}) &\text{if }a_i>a_{i+1}\\ +\infty &\text{otherwise.} \end{cases}$$

$$u_i = \begin{cases} d_{i+1} &\text{if }a_i<a_{i+1}\\ +\infty &\text{otherwise.} \end{cases}$$

Once you've computed all these values, the final answer for the minimum number of cuts needed for the sequence $a_1,\dots,a_n$ is $\min(d_1,u_1,u'_1)$.

Graph search

Alternatively, we can solve this by building up a suitable graph and then finding the shortest path in this graph.

Label a tree as a "peak" if in it is higher than its neighbors in the final sequence, and a "valley" if it is lower than its neighbors in the final sequence. The final sequence will alternate between peaks and valleys. Here is the two key observations:

  • The optimal solution will never cut any tree that ends up as a peak. (Any solution that involves cutting a peak will remain valid if you don't cut the peak, and that reduces the number of cuts by 1.)

  • In the optimal solution, you can assume without loss of generality that every tree that ends up a valley is cut down to the ground, i.e., to the minimum height. (Any solution that involves cutting a valley only partway will remain valid if you cut it down to the ground.)

Since we want to find an optimal solution, we will consider only solutions that follow both rules.

Let $a_1,\dots,a_n$ be the sequence. We will build a graph with $3n$ vertices. Each vertex has the form $\langle i,t,c \rangle$ where $i \in \{1,2,\dots,n\}$ is an index that identifies a tree, $t$ indicates whether tree $i$ will be a peak or a valley in the final solution, and $c$ indicates whether tree $i$ is cut to the ground or uncut in the final solution. We'll have an edge from one vertex to the next if they can be adjacent in a final solution. Thus, we have the following edges:

  • $\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{no} \rangle$, with length 0, for those $i$ where $a_i>a_{i+1}$

  • $\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{yes} \rangle$, with length 1, for all $i$

  • $\langle i, \text{valley}, \text{no}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$, with length 0, for those $i$ where $a_i<a_{i+1}$

  • $\langle i, \text{valley}, \text{yes}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$, with length 0, for all $i$

Finally, find the shortest path in this graph from a start vertext to an end vertex, where the start vertices are those of the form $\langle 1, *, *\rangle$ and the end vertices are those of the form $\langle n, *, *\rangle$. The length of this path will correspond to the minimum number of cuts needed in the optimal solution, and the path itself can be used to reconstruct the final solution. This shortest path can be found in $O(n)$ time using breadth-first search (BFS) on the graph defined above.

$\endgroup$
  • $\begingroup$ Does "if you start in the downwards direction for the first pair" refer to the initial tree sequence (before any cuts) or the final tree sequence (after minimum cuts) ? If it is the former, in the example sequence (3,2,1) of size 3, d[2] = d[1] = 0, d[0] = 1 and u[0] and u[1] are not defined . If it is the latter, a downward direction is impossible to achieve when a[i-1] < a[i] and a[i-1] == 1; how could I calculate d[i-1] ? I also cannot find the recurrent relation to express d(i) and u(i) in terms of d(i+1) and u(i+1). $\endgroup$ – Alan Evangelista Nov 9 at 13:48
  • 1
    $\begingroup$ @AlanEvangelista, in the final sequence (after cuts). If it is impossible to achieve, then set $d_i$ to $+\infty$. $\endgroup$ – D.W. Nov 10 at 2:54
  • $\begingroup$ @AlanEvangelista, see edited answer for a detailed elaboration on how to construct the recurrence relation and the algorithm. $\endgroup$ – D.W. Nov 10 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.