首页
登录
从业资格
某汽车加工工厂有两条装配线L1和L2,每条装配线的工位数均为n(Sij,i=1或
某汽车加工工厂有两条装配线L1和L2,每条装配线的工位数均为n(Sij,i=1或
免费题库
2022-08-02
54
问题
某汽车加工工厂有两条装配线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)。
若j=1其他(1)
(2)由于在求解经过L1和L2的第j个工位的最短时间均包含了经过L1的第j-1个工位的最短时间或者经过L2的第j-1个工位的最短时间,该问题具有重复子问题的性质,故采用迭代方法求解。该问题采用的算法设计策略是( ),算法的时间复杂度为( )以下是一个装配调度实例,其最短的装配时间为( ),装配路线为( )
问题1选项A.分治B.动态规划C.贪心D.回溯问题2选项A.Θ(lgn)B.Θ(n)C.Θ(n2)D.Θ(nlgn)问题3选项A.21B.23C.20D.26问题4选项A.S11→S12→S13B.S11→S22→S13C.S21→S12→S23D.S21→S22→S23
选项
答案
BBAB
解析
本题考查算法基础。
题目看似是非常复杂的,涉及到复杂的公式,以及算法逻辑,但如果我们先从后面两个空来分析,问题就简单得多。
求最短装配时间与装配路线,其实是一个求最短路径的过程。此时我们可以把从起点到各个结点的最短路径逐步求出。经过分析得出最短装配路线为:S11→S22→S13,长度为21。
解决了一个实际问题后,再来看所谓的迭代公式,其做法与之前手动求最短路径一致,算法是用一个数组将起点到各个结点的最短路径逐个求出,用已求出的最短路径来分析后面的最短路径,所以这符合动态规划法的特征,算法策略应是动态规划法。而算法的复杂度为Θ(n),因为用一个单重循环就可以解决这个问题。
转载请注明原文地址:https://tihaiku.com/congyezige/2410399.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
在信息管理中,哪些是信息进行加工处理的最基本方式:__()__①变化、排序、核
某汽车租赁公司建立汽车租赁管理系统,其数据库的部分关系模式如下: 用户:US
某工厂的信息管理数据库的部分关系模式如下所示:职工(职工号,姓名,年龄,月工资,
某工厂的仓库管理数据库的部分关系模式如下所示:仓库(仓库号,面积,负责人,电话)
在异步通信中,每个字符包含1位起始位、7位数据位和2位终止位,若每秒钟传送500
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
进程PA不断地向管道写数据,进程PB从管道中读数据并加工处理,如下图所示。如果采
随机试题
[img]2020m5s/ct_ve01402002m_etoeicryd_0309_202005[/img][br]Whomostlikelywil
WhataretheyNOTtalkingabout?[originaltext]M:Howwouldyouliketopayfor
VeraWanghasbecomeasignificantfigureintheAmericanfashionindustryi
Manyprivateinstitutionsofhighereducationaroundthecountryareindan
[originaltext]Lastweek,yourecall,wediscussedtheearlydevelopmentof
CFG桩的加固原理是置换和挤密。
2012年,某省规模以上工业增加值10875亿元,比上年增长7.1%,月度增速从
下列可以授予专利权的是()。A:科学发现 B:疾病的诊断和治疗方法 C:治疗
奠定了四气五味学说的理论基础,开中药归经学说之先导指的是A.《山海经》 B.《
纤维组织代替正常骨,内含化生性骨小梁的变化见于()A.慢性骨髓炎伴增生性骨膜炎
最新回复
(
0
)