最小长度路由路径 - 动态规划

Minimum length routing path - Dynamic Programing

一条线上有2*N个引脚,其中N个是输入引脚,N个是输出引脚。每个输入引脚必须连接到一个输出引脚,反之亦然,如下图所示:

连接线只能在上半平面垂直和水平制作,连接线不能重叠。

问题是所有管脚连接起来能达到的最小线长是多少

在上面的例子中,长度是31。

使用堆栈的贪婪方法,类似于匹配括号问题不是最优解。

如果您查看 1 和 8 之间最外层的线,则会将引脚分成两组。一个在2到7之间,一个在9到10之间。

这些组中的每一个都对其在不超过外线的情况下可以具有的最大行高有限制。第一个为 2,第二个默认为 5。

这给出了一个函数 lineLength(leftPin, rightPin, maxHeight) 可以通过找到高度 h 和引脚 i 来获取它的值,这样 h <= maxHeightpin[i] 介于leftPin+1rightPin 以及相反类型的 pin[leftPin].

那么行的长度就是rightPin-leftPin+2*h + lineLength(leftPin+1, i-1, h-1) + lineLength(i+1, rightPin-1, 5)

此函数有 O(n^3) 个可能的值,并且由于 hi 的迭代,使用记忆计算每个值将需要 O(n^2) 时间。所以总时间是O(n^5).

应该可以通过对最大高度进行二进制搜索来改进这一点。

分而治之可以减少到 n^2。

一般来说,第一个引脚必须与某些东西配对 - 其配对的唯一选择是当引脚串具有偶数个输入和输出位时。所以在示例中#1 可以与#8 或#10 配对。

对于这些配对中的每一个,您将该线的成本添加到线内的子问题和线外的子问题中。

例如:如果我们将 1 和 8 配对,则

cost = recursiveCost (2,7) + recursivecost(9,end) + wireCost(1,8)

您还需要跟踪内部函数调用的最大递归深度,因为您需要它来计算 wireCost(a,b)。