CODEWITHSUNDEEP
algorithmdynamic-programming
Cuber
Cuber

Reputation: 713

Algorithm: Computing tower locations to minimize expected distance

I came across this question while studying for my graduate algorithms class:

Say you have p towers that you want to place along a line of n cities, where each city is an integer from 1 to n. The cost of placing the tower is the expected distance from the tower to the rest of the cities. The problem is to provide an efficient algorithm to place all the p towers while minimizing cost.

There is a greedy approach given here : https://www.mssanz.org.au/modsim2015/J11/dzator.pdf, but it doesn't seem too efficient.

So far, I've tried attacking the problem using dynamic programming. For example, if there is 1 tower and 5 cities, I go through each of the cities as a potential candidate for the tower and calculate the cost of placing the tower there. Then, I choose the city that minimizes the cost.

However, I am having trouble following up when there are 2 or more towers. I tried to divide the cities into distinct, continuous subsets, but I can't seem to progress from that - i.e. I can't seem to identify the subproblems.

Any pointers?

EDIT:

The cost of a tower is exactly as described in the question: it is the distance to the cities from the position of the tower. However, placing a tower will affect how other towers are placed, since people of a particular city will go to their closest tower.

Upvotes: 2

Views: 2338

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23945

Increment one tower at a time and iterate through all cities. Let g(i) be the cost of placing a tower at the ith location - according to your post, this function is soley dependent on the location of the tower and the cities, the latter of which are already fixed. I'll leave the details of that computation to the reader.

Let m(t,i) be the cost of placing t towers up to index i. Then the general case would be:

m(t, i) = min(
  // Place a tower at i
  g(i) + m(t - 1, i - 1),

  // Do not place a tower at i
  m(t, i - 1)
)

As we can see, in a bottom-up approach, both of our lookups in m would have already been recorded since we are iterating through an incrementing number of towers, each time from the first to last city location.

Update:

Since the question now has the added information, "placing a tower will affect how other towers are placed, since people of a particular city will go to their closest tower," here's an O(t * n^2) formulation. Let f(t, i) represent the tth tower placed at i, c[i] represent the ith city, and d(c, t) the distance/cost function from city c to a tower at t. Then, iterating from left to right:

f(t, i) =
  if t is the leftmost tower:
    // cities left of t
    sum d(c[0..i], i)

  otherwise:
    min(
      // cities right of and closer to (t - 1)
      sum d(c[l..m], l) +

      // cities left of and closer to t
      sum d(c[m+1..i], i)

      if t is the rightmost tower, also add:
        // cities right of t
        sum d(c[i..last c], i) +

      where l is the location of the neighbouring tower
      to the left and m is the middle city, closer to l
    )

    for all l

  for all i

Upvotes: 1

btilly
btilly

Reputation: 46435

Judging from your link, what you are trying to do is place p towers in n evenly spaced cities of different size, with the size of the ith city being, say, s(i). You want to minimize the average distance from each person to the nearest tower. Or, equivalently, minimize the sum of the distances from people to towers.

Am I correct?

If so, the subproblems are to place k towers between two marks i, and j (where these marks are between cities or off the end) such that the sum of distances from people to towers is a minimum. And as a further restriction, either k is a power of 2, or else the mark goes off the right edge of the map and k is a tail end of the binary representation of n.

For each sub problem, the information is the optimal place to split into smaller subproblems if 1 < k or else it is the placement of the tower if k = 1. (Remembering that we are splitting towers evenly if k is a power of 2, or else splitting into a power of 2 and the rest of the representation if our range goes off of the right edge and k is not a power of 2.)

There will be O(log(p) * n^2) subproblems to consider and this should be perfectly amenable to dynamic programming, which can either be implemented top-down or bottom up.

Upvotes: 1

Related Questions