某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n(Sij，i=1或2，j=1，2，…，n)，两条装配线对应的工位完成同样的加工工作，但是所需要的时间可能不同(aij，i=1或2，j=1，2，…，n)。汽车底盘开始到进入两条装配线的时间(e1，

admin2019-07-12 54

问题某汽车加工工厂有两条装配线L1和L2，每条装配线的工位数均为n(S_ij，i=1或2，j=1，2，…，n)，两条装配线对应的工位完成同样的加工工作，但是所需要的时间可能不同(a_ij，i=1或2，j=1，2，…，n)。汽车底盘开始到进入两条装配线的时间(e₁，e₂)以及装配后到结束的时间(X₁X₂)也可能不相同。从一个工位加工后流到下一个工位需要迁移时间(t_ij，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)。

(65)

选项 A、S11→S12→S13
B、S11→S22→S13
C、S21→S12→S23
D、S21→S22→S23

答案B

解析动态规划算法与分治法不同的是，适合于用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果能够保存己解决的子问题的答案，而在需要时再找出己求得的答案，这样就可以避免大量的重复计算，节省时间。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。本题中的时间复杂度为O(n)。
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
求最短的装配时间与装配路线只需要将选项按照公式带入计算(将图上每条路径上的所有数字相加)可得最短路线为S11→S22→S13，时间为21。

转载请注明原文地址:https://kaotiyun.com/show/PICZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(2)

现有4级指令流水线，分别完成取指、取数、运算、传送结果4步操作。若完成上述操作的时间依次为9nss。10ns、6ns、8ns，则流水线的操作周期应设计为__________ns。

FTP提供了丰富的命令，用来更改本地计算机工作目录的命令是(36)。

建筑物综合布线系统中的工作区子系统是指()。

在地面上相隔2000km的两地之间通过卫星信道传送4000比特长的数据包，如果数据速率为64kb/s，则从丌始发送到接收完成需要的时间是______。

位于CPU与主存之间的高速缓冲存储器Cache用于存放部分主存数据的副本，主存地址与Cache地址之间的转换工作由__________完成。(2012年上半年试题)

在结构化分析方法中，数据字典是重要的文档。对加工的描述是数据字典的组成内容之一，常用的加工描述方法(14)。

下图是一个软件项目的活动图，其中顶点表示项目里程碑，边表示包含的活动，边上的权重表示活动的持续时间，则里程碑__________在关键路径上。(2011年上半年试题)

IEEE802．11标准采用的工作频段是___________。

A.乳酸 B.C02和H20 C.α-酮酸 D.乙酰CoAE.丙酮酸长链脂肪酸经β-氧化最终裂解为()。

国债按发行地域分类，可以分为(　　)。

按照我国的规定，()属于强制检定的管理范围。

下列关于微波的说法正确的是：

马、马匹

设A为三阶矩阵，其特征值为λ1=-2，λ2=λ3=1，其对应的线性无关的特征向量为α1，α2，α3令P=(4α1，α2一α3，α2+2α3)，则P-1(A*+3E)P为______．

Large,multinationalcorporationsmaybethecompanieswhoseupsanddownsseizeheadlines.Buttoafargreaterextentthanmos

IP地址块202．192．33．160／28的子网掩码可写为()。

在函数中，可以用auto、extern、register和static这四个关键字中的一个来说明变量的存储类型，如果不说明存储类型，则默认的存储类型是()。

AnswerquestionsbyreferringtothecommentsinamagazinearticleonfourfamousHollywoodactors.A=GeorgeClooney

软件设计师上午基础知识考试

软考中级

在进行进度安排时，PERT图不能清晰地描述(1)，但可以给出哪些任务完成后才能开始另一任务。某项目X包含任务A、B、…、J，其PERT如下图所示(A=1表示该任务A的持续时间是1天)，则项目X的关键路路径是(2)。(2013年上半年试题)(2)

现有4级指令流水线，分别完成取指、取数、运算、传送结果4步操作。若完成上述操作的时间依次为9nss。10ns、6ns、8ns，则流水线的操作周期应设计为__________ns。

FTP提供了丰富的命令，用来更改本地计算机工作目录的命令是(36)。

建筑物综合布线系统中的工作区子系统是指()。

在地面上相隔2000km的两地之间通过卫星信道传送4000比特长的数据包，如果数据速率为64kb/s，则从丌始发送到接收完成需要的时间是______。

位于CPU与主存之间的高速缓冲存储器Cache用于存放部分主存数据的副本，主存地址与Cache地址之间的转换工作由__________完成。(2012年上半年试题)

在结构化分析方法中，数据字典是重要的文档。对加工的描述是数据字典的组成内容之一，常用的加工描述方法(14)。

下图是一个软件项目的活动图，其中顶点表示项目里程碑，边表示包含的活动，边上的权重表示活动的持续时间，则里程碑__________在关键路径上。(2011年上半年试题)

IEEE802．11标准采用的工作频段是___________。

A.乳酸 B.C02和H20 C.α-酮酸 D.乙酰CoAE.丙酮酸长链脂肪酸经β-氧化最终裂解为()。

国债按发行地域分类，可以分为( )。

按照我国的规定，()属于强制检定的管理范围。

下列关于微波的说法正确的是：

马、马匹

设A为三阶矩阵，其特征值为λ1=-2，λ2=λ3=1，其对应的线性无关的特征向量为α1，α2，α3令P=(4α1，α2一α3，α2+2α3)，则P-1(A*+3E)P为______．

Large,multinationalcorporationsmaybethecompanieswhoseupsanddownsseizeheadlines.Buttoafargreaterextentthanmos

IP地址块202．192．33．160／28的子网掩码可写为()。

在函数中，可以用auto、extern、register和static这四个关键字中的一个来说明变量的存储类型，如果不说明存储类型，则默认的存储类型是()。

AnswerquestionsbyreferringtothecommentsinamagazinearticleonfourfamousHollywoodactors.A=GeorgeClooney

国债按发行地域分类，可以分为(　　)。