Search code examples
algorithmdynamic-programminggreedy

Minimum length routing path - Dynamic Programing

There are 2*N pins on a line, N of them are input pins, N of them are output pins. Every input pin must be connected to a single output pin and vice-versa, like in this image:

enter image description here

The connection lines can be made only vertically and horizontally in the upper half plane and the connection lines can no overlap.

The question is what is the minimum length of all lines that can be achieved when connecting all pins.

In the example above, the length is 31.

A greedy approach using a stack, similar to matching parenthesis problem is not the optimal solution.

Solution

  • If you look at the outermost line between 1 and 8, then it splits the pins into two groups. One between 2 and 7, and the other between 9 and 10.

    Each of these groups has a constraint on the maximum line height it can have without extending past the outer line. 2 for the first, and some default like 5 for the second.

    This gives a function lineLength(leftPin, rightPin, maxHeight) that can get its value by finding a height h and pin i so that h <= maxHeight and pin[i] is between leftPin+1 and rightPin and the opposite type of pin[leftPin].

    Then the line length would be rightPin-leftPin+2*h + lineLength(leftPin+1, i-1, h-1) + lineLength(i+1, rightPin-1, 5)

    There are O(n^3) possible values for this function and calculating each value, with memoization, would require O(n^2) time because of the iterations of h and i. So the total time is O(n^5).

    It should be possible to improve this with a binary search on the maximum height.