CODEWITHSUNDEEP
algorithmdynamic-programmingminimization
aa1
aa1

Reputation: 803

Minimizing cost of pipeline by finding optimal locations for stations using dynamic programming

I have a question about dynamic programming that I am trying to describe an algorithm for.

Question: A pipeline is to be built and you have to decide on the optimal location of the stations along the path that has already been decided. The pipeline connects points x1 and xn and goes through locations x2,x3...x(n-1). There are stations at x1 and xn but part of the problem is to decide whether to build a station at point xi for i = 2,3...n-1.If a station is built the associated cost is bi and if a pipeline is built between stations xi and xj, the corresponding cost is cij. The total cost is the sum of the costs of the station and the corresponding pipeline section costs. The goal is to decide the optimal location of stations so that the total cost is minimized.

We have to describe a general algorithm for this using dynamic programming. My approach was to treat this like a rod cutting problem and try to make a matrix and minimize the cost but I am not sure how to deal with the extra variable of the cost of the stations being built as well. How should I approach this problem given the many variables? And how would I develop a recursive formula? Any help would be appreciated!

EDIT: Yes I agree that the question is a bit unclear and also confused me at first, but that is all that was given in the question. I believe since the stations and pipelines all have different costs, there should be an optimal way of doing it.

Upvotes: 0

Views: 713

Answers (1)

Prune
Prune

Reputation: 77837

The critical insight in this is that the minimum cost to connect any two points, xi and xj (call it mij) is independent of the configurations outside of that segment (i.e. x*1* to xi and xj to xn).

Your dynamic programming problem is to index and store each cost as it's found, and the to float partial solutions back up the call tree.

The base case is that the cost to connect two adjacent nodes, xi and xj (where j=i+1), is simply cij (you can't build a new station there).

The simplest case is when j=i+2; Is it profitable to build a station at i+1. In algebraic terms, is c(i)(i+2) < b(i+1) + c(i)(i+1) + c(i+1)(i+2) ?

In general, you need to recur on a find_first_station(i, j) function. This should find the location of the lowest-index station to build between stations already at i and j. For each point 'k, i<k<j, build a station atk, run a pipeik, and then recur withfind_first_station(k, j). Return the solution (all station locations) with the minimum cost for anyk`, or the null list if cij is the minimum cost.

Can you take it from there?

Upvotes: 1

Related Questions