15
第4-2课：装配线与工作站问题
source link: https://blog.csdn.net/orbit/article/details/108729360
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
第4-2课：装配线与工作站问题
在前面的内容中，我们介绍过用穷举法设计“装配线与工作站问题”的算法实现，这一课我们将介绍如何用动态规划法设计这个问题的算法实现。两种不同的设计思想它们的算法实现肯定也是相差千里，穷举法中的遍历过程需要算法代码显式控制，而动态规划法的遍历过程则是算法本身隐含的，说具体一点，就是隐含在状态递推的过程中。在开始本课的内容之前，请大家再回忆一下第4-1课的内容，用动态规划思想设计算法实现，需要明确的三个问题：子问题与决策阶段状态的定义、状态递推关系式、边界条件。
为了便于理解本课的内容，在开始算法分析之前，再回顾一下这个题目：Colonel 汽车公司在有两条装配线的工厂内生产汽车，一个汽车底盘在进入每一条装配线后，在每个工作站会在汽车底盘上安装不同的部件，最后完成的汽车从装配线的末端离开，如图（1）所示：
图（1）装配线与工作站问题的图示例
每一条装配线上有 n 个工作站，编号为 j=1,2,…,n，将装配线 i（i 为 1 或 2）的第 j 个工作站表示为 S(i,j)。装配线 1 的第 j 个工作站 S(1,j) 和装配线 2 的第 j 个工作站 S(2,j) 执行相同的功能。然而这些工作站是在不同的时间建造的，并且采用了不同的技术
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK