The Pipeline

The Pipeline

by Juan Pablo Vega

 

Problem Statement 

The Pipeline is searching problem. It is quite conventional. There is a grid map filled with cost values. There is a start and a goal. Nothing really complicated huh? Well, there are some particularities. First, the map is a square grid. Second, there is no one start nor one goal. The search can start from any row of the first column and finish at any row of the last column. Furthermore, one cannot move to the left, only up-down-right steps are allowed. Oh, did I mention that the map can get really huge and that you have limited time to find the optimal path? Fortunately, we are only asked for the cost of the optimal solution. 

 

 Think Twice Before You Start 

One might jump in and try to solve it with all the conventional tools one might have. BFS, DFS, A*, Dijkstra, and many more, are possible methods that could cross your mind. But implementing any of them would be in vain. Simply take a step back and think about the map. It has a known structure: it's a square. It has known dynamics: one can't go left. And most importantly, all the content (cost and constraints) are defined in a descriptive manner, and are not subject to any kind of variation in any way. 

 

Turn It Upside Down 

So, where do I start? From the beginning right? Wrong! Starting from there has many disadvantages. First, you don't know which row is the correct start point and you are going to pay the price of additional, useless computing. Second, and most important you are going to repeat many steps of your search. Ok, what if I start from some sort of optimal internal point? Well, for any internal point there will be a portion of the map that remains on the right, for which it will act as a starting point. And we are back to the disadvantages I mentioned above. Ok, ok, from the last column then. Exactly, but why? Well, if you start from the leaves, you might eliminated once and for all a dead branch. At every level (column) you choose to discard dead ending paths. And this process is incremental, meaning that your only use past pre-processed plus new non-processed information. 

 

 Compute Only Once: Dynamic Programming

That seems interesting right? It is called dynamic programming. It is a method for solving complex problems by first solving simpler sub-problems only once, and then combining all optimal sub-solutions to give the optimal global solution. For those who have never heard of it, stay put and appreciate the magic of it. 

 

 Let's Get Started

Let's assume that the grid map can be found in city and that cost is a copy of the grid map without any content. We will use cost as a structure containing the backward-incremental costs, i.e. the optimal sub-solutions. Let's cut the problem in half. The first sub-problem only permits us to move down-right, while the second, up-right. With these two new problems, the problem gets much easier. Finally, it's important to recognize that the last column of city already states the optimal sub-solutions. Indeed, for every column of the map we have reach the end, and there is no use of going up or down. Thus the last column of city can be copied to the last column of cost.

 

Solving down-right Upside Down

Let's say that we are at a given column j and that we have already found all sub-solutions for n-1, n, ..., j+1. This means that all the information we need to find the sub-solution at j can be found in the j+1th column of cost and in the jth column of city. What are the possible moves from the last row, n? Only right. We then update cost with this sub-solutions. When we analyse row n-1, we find that cost[n][j] and cost[n-1][j+1] are both optimal sub-solutions for the down-right problem. It is easy then to find the sub-solution for row n-1. Similarly, we can find the solutions for any row of column j up to the first.

 

Solving up-right Upside Down

We could follow the same procedure for this sub-problem. But we would soon find that there is a certain degree of overlap. Well, in down-right, we already considered the case where going down and going right were the optimal sub-solution. And the result was saved in cost. Now, in up-right we are considering going right again. It is of no use if the values of cost are shared among the sub-problems. That way, we should do as follows. From row 1 sequentially until row n-1 we would compare the possibility of going up against the optimal sub-solutions of the previous sub-problem.

 

From Right To Left

Repeating down-right and then up-right for every column, starting from column n-1 up until column 0 represents the process of combining optimal sub-solutions to fin the optimal global solution. The last step, once the first column have been processed, is to find the minimum accumulated cost, located somewhere in the first column of cost. 

 

 Sample Code

Here is a snippet of the search block of the program:

# The Pipeline, by Juan Pablo Vega | IEEEXtreme 8.0 (2014)

for j in range(n-2,-1,-1):
    for i in (range(n-1,-1,-1)):
        if i < (n-1):
            cost[i][j] = min(city[i][j]+cost[i][j+1], city[i][j]+cost[i+1][j])
        else:
            cost[i][j] = city[i][j]+cost[i][j+1]
    for i in range(n):
        if i > 0:
            cost[i][j] = min(cost[i][j], cost[i-1][j]+city[i][j])

 

Files

The solution is available at this drive folder.