1

I have an algorithmic problem in which I have a highway that is a straight line of length n and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am trying to use dynamic programming to find a way to minimize the cost of ensuring that each point in the highway is covered by at least one tower. I am given a length n for the highway, an array of costs of length n + 1, and must assume that the towers all will have a 5 mile range (eg a tower built at point i will have range [i-5,i+5] inclusive).

I believe that my subproblem is OPT(i) where i is the minimum cost to cover the first i miles of highway, however am having trouble constructing my recursive formula or algorithm. I know that a greedy approach would not be optimal in this case. I think that perhaps the shortest path problem could be harnessed however am having trouble creating an answer that follows the steps of dynamic programming. So far this is my algorithm:

  1. Initialize an array C of length n+1, where C[i] represents the minimum cost to cover the first i miles of the highway.
  2. Set C[0] = 0 and C[1] = cost[1].
  3. For i = 2 to n, calculate C[i] using the recurrence relation: C[i] = min(cost[i] + C[i-5], C[i-1])
  4. Return C[n], which represents the minimum cost to cover the entire highway. Any advice would be appreciated!
Improve this question
2
  • You should post this to Coputer Science Stack exchange network. This is not the place where you do it. Commented Nov 29, 2023 at 23:02
  • 1
    @NeerajRoy we like these questions just fine under the algorithm tag. Commented Nov 30, 2023 at 3:27

2 Answers 2

Reset to default
3

Let's say the placement of a tower in cell i is valid if it, together with all previously placed towers, covers all cells <= i+5. Since the range within 5 is covered by the tower at i, we can place a tower there if every cell from 0 up to i-6 is covered.

In your DP array, the value in cell i is the min total cost a valid placement of a tower in cell i.

Then, DP[i] = C[i] + min(DP[j]) for all j that cover i - range - 1 (the closest tower to the left not covered by tower i).

At the end, the answer is the minimum value of DP[i] for all the i that cover the last cell.

The tower that covers cell i can be placed in any of the 11 spots between i-5 and i+5.

I'll give a smaller example -- same concept, but each tower covers cells within 2.

input: [16, 4, 8, 12, 7, 5, 11, 12, 14, 3]

We fill out the DP array as follows:

index: value & reasoning
0: 16 (no previous towers not covered by this)
1:  4 (no previous towers not covered by this)
2:  8 (no previous towers not covered by this)
3: 12 + min(16,  4,  8)         = 12 + 4 = 16
4:  7 + min(16,  4,  8, 16)     =  7 + 4 = 11
5:  5 + min(16,  4,  8, 16, 11) =  5 + 4 =  9    
6: 11 + min( 4,  8, 16, 11,  9) = 11 + 4 = 15
7: 12 + min( 8, 16, 11,  9, 15) = 12 + 8 = 20
8: 14 + min(16, 11,  9, 15, 20) = 14 + 9 = 23
9:  3 + min(11,  9, 15, 20, 23) =  3 + 9 = 12

Any of the last 3 cover the last spot, so the answer is min(20, 23, 12) = 12.

By tracking which mins are selected each time, we can find the selection of towers that gives us the min.

index 9: min comes from index 5
index 5: min comes from index 1
index 1: min comes from a negative index so we're done

12 comes from indices 1, 5, 9

[16, (4), 8, 12, 7, (5), 11, 12, 14, (3)]

Ruby code (read as pseudocode if you don't know Ruby)

def f(costs, range)
  # the first range elements of dp are identical to costs since they don't depend on a prior tower
  dp = costs[0, range + 1]
  
  # now, for each new index, we need to add the smallest previous dp sum 
  # associated with a tower that covers the spot range-1 to the left.
  (range + 1).upto(costs.length - 1) do |i|
    left_indx_of_subrange = [0, i - (2*range + 1)].max
    right_indx_of_subrange = i-1
    length_of_subrange = right_indx_of_subrange - left_indx_of_subrange + 1
    dp[i] = costs[i] + dp[left_indx_of_subrange, length_of_subrange].min
  end
  puts dp.to_s
  return dp[-(range + 1), range + 1].min
end

> f([16, 4, 8, 12, 7, 5, 11, 12, 14, 3], 2)
=> 12

This code doesn't track which indices were used.

Range 5 example:

cost = [47, 30, 38, 18, 10, 26, 16, 33, 42, 13, 29, 34, 25, 35, 30, 38, 15, 15, 45, 18, 28, 19, 37, 20, 20, 12, 29, 40, 13, 30, 24, 35, 44, 38, 24, 26, 22, 46, 39, 10, 27, 40, 36, 25, 36, 40, 26, 42, 49, 12]
range = 5
optimal = 73
optimal selections in parens: [47, 30, 38, 18, (10), 26, 16, 33, 42, (13), 29, 34, 25, 35, 30, 38, 15, (15), 45, 18, 28, 19, 37, 20, 20, 12, 29, 40, (13), 30, 24, 35, 44, 38, 24, 26, 22,  46, 39, (10), 27,  40,  36, 25,  36, 40,  26,  42,  49, (12)]
DP array: [47, 30, 38, 18, 10, 26, 26, 43, 52, 23, 39, 44, 35, 45, 40, 48, 38, 38, 68, 41, 51, 54, 72, 55, 58, 50, 67, 78, 51, 71, 65, 85, 94, 88, 74, 76, 72, 97, 90, 61, 88, 101, 97, 86, 97, 101, 87, 103, 110, 73]
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

I will explain the needed dynamic programming formulation in terms of an example. I believe the algorithm is essentially the same as @Dave's.

Data for example problem

Suppose

n = 10
r = 3 
c = [2, 4, 6, 5, 4, 3, 5, 4, 3, 2, 4]

where r equals the radius of tower coverage, in miles, and c[d] equals the cost of building a tower at location d miles from the origin, d = 0, 1,..., n.

Assumptions and definitions

A tower built at distance d from the origin covers an area from distance max {0, d-r} to distance min { d+r, n}.

A collection of towers built at intregal-valued locations between 0 and d, d <= n, is considered feasible relative to d if all points between 0 and d are covered by at least one tower.

At location d, d = 0,1,...,n let x(d) equal the minimum cost among all feasible tower construction projects relative to d when the last tower is built at distance d. These are the model's state variables.

Work forward to determine optimal costs of partial solutions

When d = 0, 1, 2, 3, x(d) is simply the cost of constructing the tower since a tower at any of those locations will cover the area between 0 and 3. Therefore,

x(0)  = c[0] = 2, save p = nil
x(1)  = c[1] = 4, save p = nil 
x(2)  = c[2] = 6, save p = nil
x(3)  = c[3] = 5, save p = nil

For the moment, disregard the references save p = nil.

At d = 4 things change, because building a tower at d = 4 does not cover the area between d = 0 and d = 1. A tower therefore must be built at d equal to 1, 2, or 3. We therefore compute

x(4) = c[4] + min {x(0), x(1), x(2), x(3)} =
     =   4  + min {2, 4, 6, 5}
     =   6
save p = 0

We set p = 1 to indicate that distance at which the previous tower would be built. This information is used later to reconstruct the optimal solution.

The calculations for d = 5,..., 10 are similar.

x(5) = c[5] + min {x(0), x(1), x(2), x(3), x(4)} =
         3  + min {  2,    4,    6,    5,    6}
     = 5
save p = 0

x(6) = c[6] + min {x(0), x(1), x(2), x(3), x(4), x(5)}
     =   5 + min {   2,    4,    6,    5,    6,    5}
     = 7
save p = 0

x(7) = c[7] + min {X(1), x(2), x(3), x(4), x(5), x(6)}
     =   4  + min {  4,    6,    5,    6,    5,    7 }
     =   8
save p = 1

x(8) = c[8] + min {x(2), x(3), x(4), x(5), x(6), x(7)}
     =   3  + min {  6,    5,    6,    5,    7,    8 }
     =   8
save p = 3 (or could save p = 5)

x(9) = c[9] + min {x(3), x(4), x(5), x(6), x(7), x(8)}
     =   2  + min {  5,    6,    5,    7,    8,    8 }
     =   7
save p = 3

Lastly, for the endpoint at distance n (10),

x(10) = c[10] + min {x(4), x(5), x(6), x(7), x(8), x(9)}
      =   4   + min {  6,    5,    7,    8,    8,    7 }
      =   9
save p = 5

Compute the optimal value

The given radius implies that the last project must be at distance 7, 8, 9 or 10. We therefore compute:

min {x(7), x(8), x(9), x(10)} = min {8, 8, 7, 9} = 7

Reconstruct the optimal solution

We will use the values of p that we saved to reconstruct the optimal solution. We just determined that the last tower built in the optimal solution was at d = 9.

If we examine the calculation of x(9) we see that we set p = 3, meaning that the previous tower would be built at distance 3.

In computing x(3) we saved p = nil, which signified the first tower was built at that distance (3).

We therefore have determined that in the optimal solution towers are built at distances of 3 and 9, and that the optimal value is 7, the total cost of building towers at those two locations. We can check that.

c[3] + c[9] = 5 + 2 = 7
Improve this answer

3 Comments

@user3386109, many thanks for demonstrating that my answer was incorrect. I believe that it is now correct but do let me know if you spot any more problems. Note that in reworking my answer I changed c[10] from 1 to 4. As a result none of the optimal solutions include a tower at distance 10.
@user3386109, recall that in my example the radius, r, equals 3, so a tower at 0 would cover from 0 to 3 on the highway and the tower at 7 would cover from 4 to 10 on the highway, leaving the area between 3 and 4 uncovered, so that is not a feasible solution.
@user3386109, it makes no difference which interpretation is correct as one can simply adjust the algorithm in an obvious way to fit the interpretation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.