首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
某汽车加工工厂有两条装配线L1和L2,每条装配线的工位数均为n(Sij,i=1或2,j=1,2,…,n),两条装配线对应的工位完成同样的加工工作,但是所需要的时间可能不同(aij,i=1或2,j=1,2,…,n)。汽车底盘开始到进入两条装配线的时间(e1,
某汽车加工工厂有两条装配线L1和L2,每条装配线的工位数均为n(Sij,i=1或2,j=1,2,…,n),两条装配线对应的工位完成同样的加工工作,但是所需要的时间可能不同(aij,i=1或2,j=1,2,…,n)。汽车底盘开始到进入两条装配线的时间(e1,
admin
2019-07-12
26
问题
某汽车加工工厂有两条装配线L1和L2,每条装配线的工位数均为n(S
ij
,i=1或2,j=1,2,…,n),两条装配线对应的工位完成同样的加工工作,但是所需要的时间可能不同(a
ij
,i=1或2,j=1,2,…,n)。汽车底盘开始到进入两条装配线的时间(e
1
,e
2
)以及装配后到结束的时间(X
1
X
2
)也可能不相同。从一个工位加工后流到下一个工位需要迁移时间(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
软件设计师上午基础知识考试
软考中级
相关试题推荐
VLAN中继协议(VTP)有不同的工作模式,其中能够对交换机的VLAN信息进行添加、删除、修改等操作,并把配置信息广播到其他交换机上的工作模式是()。
若一个项目由9个主要任务构成,其计划图(如下图所示)展示了任务之间的前后关系以及每个任务所需天数,该项目的关键路径是(1),完成项目所需的最短时间是(2)天。(2)
在地面上相隔2000km的两地之间通过卫星信道传送4000比特长的数据包,如果数据速率为64kb/s,则从丌始发送到接收完成需要的时间是______。
某项目主要由A~I任务构成,其计划图(如下图所示)展示了各任务之间的前后关系以及每个任务的工期(单位:天),该项目的关键路径是(1)。在不延误项目总工期的情况下,任务A最多可以推迟开始的时间是(2)天。(2009年上半年试题)(1)
在结构化分析方法中,数据字典是重要的文档。对加工的描述是数据字典的组成内容之一,常用的加工描述方法(14)。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,边表示包含的活动,边上的权重表示活动的持续时间,则里程碑__________在关键路径上。(2011年上半年试题)
IEEE802.11标准采用的工作频段是___________。
随机试题
有关痈的处理方法,不正确的是
地西泮片剂含量测定采用紫外分光光度法(吸收系数法),而其注射液的含量测定却采用高效液相色谱法,其原因为
背景资料:某施工单位承接了一座公路隧道的土建及交通工程施工项目,该隧道为单洞双向行驶的两车道浅埋隧道,设计净高5m,净宽12m,总长1600m,穿越的岩层主要由页岩和砂岩组成,裂隙发育,设计采用新奥法施工、分部开挖和复合式衬砌。进场后项目部与
下列项目中,不属于我国会计核算的一般原则的是( )。
大明有限责任公司(以下简称大明公司)为增值税一般纳税人,适用的增值税税率为16%。2×18年11且30日的科目余额(部分科目)如下表所示。假定坏账准备均为应收账款计提。大明公司12月份有关资料如下:(1)本月销售商品不含税售价25000元,增值税
以下关于注册会计师与管理层沟通要求的说法中,正确的有()。
Researchershavestudiedthepoorasindividuals,asfamiliesandhouseholds,asmembersofpoorcommunities,neighborhoodsand
Ittakesawholegalaxyofthingstomakeyouhappy.Happinessisastateyoufeelwhenyouhavenoproblems,worries,doubtsor
某项目经理在与项目干系人的沟通过程中运用了多种沟通方法,有项目日志、项目例会、甲方代表参与的项目会议等,但仍有些关键问题未能与用户达成一致。根据沟通原则,可建议承建单位采用(59)方法。
Oneoftheworstthingyoucandoasaspeakeristoholdyour【M1】______armsstifflyatyourside.Youneedtomoveyourarms
最新回复
(
0
)