装配线调度 - 数据结构

Question

我想努力去理解如何在Corian的算法书Intorduction to Algorithms的第15章'动态编程'中的'装配线调度'问题中计算表。

任何人都可以给我一个关于&两个表是怎么计算的提示吗？在谷歌搜索过去2小时。

Answer 1

该第一表包含通过站的Si，j中的最快的方法：

• F1 [j]为通过流水线的站Ĵ1个
• F2 [j]的是最快的方法以最快的方式通过装配线2

例如，f2的站Ĵ（3）= ，由于2 + 7 + 2 + 5 + 6 = ，这是最快的方法（j）显示在步骤j-1中使用的流水线编号（1或2）作为达到li的最快途径的一部分（1或2） j）的。

例如，L 1（2）= 因为在装配线1到达基站2的最快方式是通过站1上装配线。 （2 + 7 < 4 + 8 + 2）

L2（2）=因为在装配线2到达台2的最快方式是通过站1上装配线。 （2 + 7 + 2 < 4 + 8）。

Answer 2

f(2) = 22，因为它是最短的方式（时间）来传递站2,3 :)
你必须看所有的方法，并找到最短f(1)j是站1,j
我知道，因为我把这个教训太:)

Answer 3

对不起挖掘一个4岁的问题，但这是谷歌的第一个结果。

Lior提供的答案不正确。 f1（j）不适用于从装配线1开始的通过站。如果是这样，为什么f1（2）= 18？当最佳路径是2 + 7 + 2 + 5 = 16。

另外，对于F2（3）= 22，4 + 8 + 5 + 1 + 3不等于22这21.

fi（j）实际上是到达第i个线路上第j个站点的最快方式的功能（由Kubra回答）。 f2（3）= 22，因为2 + 7 + 2 + 5 + 6。这是到达该特定站的最有效途径。

我希望我的回答能够节省人们的时间，因为我花了一个小时对双重，三重检查，如果我对理解问题和答案有所误解。

谢谢。