【摘 要】
：
树上的最小-最大k旅行商问题是多旅行商问题在树形结构中的推广问题.研究了树上的最小-最大k旅行商问题、树上的多仓库最小-最大k旅行商问题以及树上的最小-最大k路覆盖问题,提出了基于自下而上的动态规划的拟多项式时间精确算法.将树上的多仓库最小-最大k旅行商问题的算法推广到树上的多仓库最小-最大k路覆盖问题和树上的多仓库最小-最大k中国邮递员问题,分别给出了首个拟多项式时间精确算法.
【机 构】
：
华东理工大学数学学院,上海 200237
论文部分内容阅读
树上的最小-最大k旅行商问题是多旅行商问题在树形结构中的推广问题.研究了树上的最小-最大k旅行商问题、树上的多仓库最小-最大k旅行商问题以及树上的最小-最大k路覆盖问题,提出了基于自下而上的动态规划的拟多项式时间精确算法.将树上的多仓库最小-最大k旅行商问题的算法推广到树上的多仓库最小-最大k路覆盖问题和树上的多仓库最小-最大k中国邮递员问题,分别给出了首个拟多项式时间精确算法.
其他文献
基于网络药理学分析绿茶中的主要多酚物质表没食子儿茶素没食子酸酯(Epigallocatechin Gallate,EGCG)对三阴性乳腺癌细胞MDA-MB-231的潜在作用靶点及其分子机理.使用数据库检索EGCG和MDA-MB-231的潜在靶点,两者的靶点基因相互映射取交集,获得共同作用靶点;借助软件Cytoscape 3.8.0绘制“靶点-通路”网络互作图、String数据库构建靶点蛋白的互作网络关系(Protein-Protein Interaction,PPI),基于Metascape平台对靶点进行
建立了页岩气化学链重整制甲醇联合固体燃料电池发电过程模型,并通过原料消耗、产品产出、过程能耗和?效率等指标对新流程进行技术分析.通过化学链重整制合成气和氢气来优化甲醇合成和实现页岩气的高效利用,通过将剩余氢气用于固体燃料电池发电和弛放气化学链燃烧供热实现电能自给并有盈余.还探讨了不同甲烷转化率对新过程技术性能的影响,甲烷转化率为60.0％的过程?效率仅为57％,而甲烷转化率为80.0％～99.3％的过程?效率高达71％～74％.
在自主搭建的工业级管径(内径50 mm)气力输送实验平台上开展了密相气力输送实验,对气固两相通过弯管的流动特性进行了研究.借助电容层析成像技术分析弯管出口截面流型特征,发现煤粉流经弯管时管道截面浓度存在明显的径向分布,外壁浓度相对较高.采用附加压降法,并结合对实验数据的回归分析,建立了精度±10％以内弯管压降模型.并基于微元分析和弯管压降分布的基本规律,获得了煤粉浓度沿弯管流动方向的分布特征.
利用毕赤酵母GS115表达系统,成功表达并纯化获得了两种Kex2蛋白酶突变体Kex2-K291L和Kex2-K291H.对比研究了天然Kex2蛋白酶和这两种突变体的酶学性质和稳定性.实验结果表明,与天然Kex2蛋白酶相比,Kex2-K291H和Kex2-K291L两种突变体的稳定性得到了明显的改善.两种突变体的最适pH和最适温度与天然Kex2蛋白酶保持一致,均为pH 9.0和37℃,两种突变体的温度稳定性也与天然Kex2蛋白酶基本一致.与天然Kex2蛋白酶相比,突变体Kex2-K291H的pH值稳定性范围
采用粗细粒度优化、参数定点化与重排序等多种硬件加速方法,基于FPGA+SOC异构平台提出了一种低功耗目标检测加速器架构.针对现有研究的设计局限性,在Zynq 7000系列FPGA上对YOLOv2算法进行新型多维度硬件加速,并对加速器性能和资源耗费进行深入分析建模,验证架构的合理性;为充分利用片上硬件资源,对各个模块进行特定优化设计,针对被忽视的底层繁琐数据访问,改进加速器数据访存机制,有效减少了系统传输时延.实验结果表明,该架构在PYNQ-Z2平台上获得了26.98 GOPs的性能,比现有的基于FPGA的
在聚乙烯管道电熔焊接接头的超声成像中,特征线、电阻丝线和管材内壁回波这3条信号线的检测是实现焊接缺陷自动化识别的关键技术.针对超声图像纵向分层显著、全局干扰较多的特点,提出了一种自适应聚乙烯管道超声信号线检测算法.首先,为了识别分层区域,基于形态学运算对灰度图进行自适应模糊,再进行水平均值投影;然后,基于目标特征和空间信息改进了自适应阈值分割算法,用于检测特征线,并提出了Otsu-CRF算法用于检测电阻丝并解决电阻丝粘连问题;最后,基于色彩空间和阈值分割实现管材内壁回波的检测.实验结果显示,本文的自适应算
针对多变量动态过程的故障诊断,采用局部提取、全局整合的特征提取策略,提出了一种多块卷积变分信息瓶颈(Multi-Block Convolutional Variational Information Bottleneck,MBCVIB)模型.首先,根据过程机理,对所有变量分块,将同一操作单元的变量划分为同一子块,再利用一维卷积神经网络(One-Dimensional Convolutional Neural Network,1-D CNN)提取过程中每个子块的局部特征,从而考虑样本间的时序相关性;然后,整
为改善多相电机转矩控制策略性能,以对称六相永磁同步电机为研究对象,结合其结构和绕组分布特点建立自然坐标系下数学模型.由于多相电磁耦合下计算复杂,推导出旋转坐标系下的矢量变换模型.针对多相电机启动转矩波动较大现象,提出一种新的基于空间矢量脉宽调制(SVPWM)技术的直接转矩控制(DTC)策略.在MATLAB/Simulink环境下,对电机的矢量解耦变换下的数学模型进行仿真研究.结果表明,相比于传统直接转矩控制,所设计的新算法对电机电磁转矩、磁链等方面具有更好的抗扰动性和调控性能,验证了所开发控制算法的有效性
采用高温热台显微镜原位研究了铁精粉单颗粒在高温及CO气氛下还原过程的演化特征.通过原位实验记录了铁精粉单颗粒的高温还原过程,并利用拉曼光谱仪验证了还原反应产物(单质铁).结果表明,颗粒表面出现单质铁的时间受温度影响显著,受气体流量影响小.其中,当温度从1100℃升至1300℃时,单质铁的生成时间缩短约75％;当温度从1300℃升至1400℃时,单质铁的生成时间基本不变.当温度为1100～1350℃时,铁精粉颗粒在还原过程中表面会产生瘤状物,且瘤状物尺寸随着温度升高而增大.引入瘤状物长宽和的平均值为特征尺度
由于传统的目标检测算法较为复杂,在算力、存储空间有限的场景下无法实时检测,因此本文提出了一种轻量级入侵检测算法.首先采用自适应更新率的混合高斯前景提取算法提取初筛目标,然后基于改进的残差压缩网络(R-SqueezeNet)对初筛目标进行识别分类.实验结果表明,该算法在不降低检测精度的前提下,比传统算法的检测速度平均提升了30倍,模型体积缩减至YOLOv3-tiny算法的1/40.