某汽车加工工厂有两条装配线L1和L2;每条装配线工位数均为n(Sij，i=1或2，j=1，2,..n)，两条装配线对应工位完成同样加工工作，但是所需要时间可能不同
(aij，i=1或2，j=1，2，... n)。汽车底盘开始到进入两条装配线时间(e1，e2)以及装配后到结束时间(X1X2)也可能不相同。从一个工位加工后流到下一个工位需要迁移时间
(tij,i=1或2，j=2,n)。现在要以最快时间完成一辆汽车装配，求最优装配路线。
分析该问题，发现问题具有最优子结构。以L1为例，除了第一个工位之外，经过第j
个工位最短时间包含了经过L1第j-1个工位最短时间或者经过L2第j-1个工位最
短时间,如式(1)。装配后到结束最短时间包含离开L1最短时间或者离开L2最短时间
如式(2)。
由于在求解经过L1和L2第j个工位最短时间均包含了经过L1第j-1个工位最
短时间或者经过L2第j-1个工位最短时间，该问题具有重复子问题性质，故采用迭代
方法求解。该问题采用算法设计策略是(62) ，算法时间复杂度为(63) 。
以下是一个装配调度实例，其最短装配时间为(64) ，装配路线为(65) 。
- A.21
- B.23
- C.20
- D.26
正确答案及解析
正确答案
解析
动态规划算法与分治法不同是，适合于用动态规划求解问题，经分解得到子问题往往不是互相独立。若用分治法来解这类问题，则分解得到子问题数目太多，有些子问题被重复计算了很多次。如果能够保存已解决子问题答案，而在需要时再找出已求得答案，这样就可以避免大量重复计算，节省时间。可以用一个表来记录所有已解子问题答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法基本思路。本题中时间复杂度为O(n) 。
贪心选择是指所求问题整体最优解可以通过一系列局部最优选择，即贪心选择来达到。这是贪心算法可行第一个基本要素，也是贪心算法与动态规划算法主要区别。
回溯算法实际上一个类似枚举搜索尝试过程，主要是在搜索尝试过程中寻找问题解，当发现已不满足求解条件时，就“回溯”返回，尝试别路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走技术为回溯法，而满足回溯条件某个状态点称为“回溯点”。
求最短装配时间与装配路线只需要将选项按照公式带入计算（将图上每条路径上所有数字相加）可得最短路线为S11→S22→S13 ，时间为21。
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案