首页
登录
从业资格
某汽车加工工厂有两条装配线L1和L2;每条装配线的工位数均为n(Sij,i=1或
某汽车加工工厂有两条装配线L1和L2;每条装配线的工位数均为n(Sij,i=1或
考试题库
2022-08-02
58
问题
某汽车加工工厂有两条装配线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.O(lgn)B.O(n)C.O(n2)D.O(nlgn)
选项
A.O(lgn)
B.O(n)
C.O(n2)
D.O(nlgn)
答案
B
解析
动态规划算法与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。本题中的时间复杂度为O(n) 。
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
求最短的装配时间与装配路线只需要将选项按照公式带入计算(将图上每条路径上的所有数字相加)可得最短路线为S11→S22→S13 ,时间为21。
转载请注明原文地址:https://tihaiku.com/congyezige/2407918.html
本试题收录于:
中级 软件设计师题库软件水平考试初中高级分类
中级 软件设计师
软件水平考试初中高级
相关试题推荐
某嵌入式刹车控制软件,应用于汽车刹车控制器,该软件需求如下: 1.模式选择
颜色深度是表达单个像素的颜色或灰度所占的位数(bit),若每个像素具人有8位的颜
某企业的生产流水线上有2名工人P1和P2,1名检验员P3.P1将初步加工的半成
数据字典是结构化分析的一个重要输出。数据字典的条目不包括()。A.基本加工
以下关于数据流图的叙述中,不正确的是______。A.从数据传递和加工的角度,刻
银行系统数据流图中,某个加工根据客户的多个不同属性的值来执行不同的操作,则对该加
某嵌入式刹车控制软件,应用于汽车刹车控制器,该软件需求如下: 1.模式选择:采
某嵌入式刹车控制软件,应用于汽车刹车控制器,该软件需求如下: 1.模式选择:采
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码
某汽车维修公司有部门、员工和顾客等实体,各实体对应的关系模式如下:部门(部门代码
随机试题
OnSaturday,BexarCountyDigitalLibrary—a$2.4million,4,000-square-foot
Playingvideogames,includingviolentshootergames,may【C1】________childre
AmericanEnglishisanothervarietyoftheEnglishlanguagespokenintheUn
已知三个整数a,b,c成等差数列,且a+b,b+c,c+a成等比数列,a,b,c
反射中枢位于脊髓的是()。A.屈肌反射 B.对侧伸肌反射 C.两者均是
补体促进吞噬细胞的吞噬作用被称为补体的A.炎症介质作用B.调理作用C.免疫黏附作
土地面积量算在( )的基础上进行。A.室内测量 B.产权调查 C.行政调
商业银行衡量目标区域盈利性的指标有()。A.净息差 B.增量存贷比率
(2018年真题)个人外汇业务按照交易性质区分为()。A.境外个人外汇业务
女性,32岁,进行性膀胱刺激症状,经抗生素治疗不见好转,且伴有右侧腰部胀痛及午后
最新回复
(
0
)