检索结果-内蒙古大学图书馆

计算机工程 2022年第6期48卷 182-192,199页

作者：王晓峰于卓赵健曹泽轩北方民族大学计算机科学与工程学院银川750021 北方民族大学图像图形智能处理国家民委重点实验室银川750021 西北大学信息科学与技术学院西安710127

最大团问题是一个经典的组合优化问题,在蛋白质功能推测、竞胜标确定、视频对象分割等领域有广泛的应用。随着图例规模的增大,最大团问题求解难度增加,常规图例最大团求解算法已逐渐被大规模图例最大团求解算法取代。介绍求解大规模图... 详细信息

最大团问题是一个经典的组合优化问题,在蛋白质功能推测、竞胜标确定、视频对象分割等领域有广泛的应用。随着图例规模的增大,最大团问题求解难度增加,常规图例最大团求解算法已逐渐被大规模图例最大团求解算法取代。介绍求解大规模图例最大团问题的技术支撑点,重点总结基于大规模图例的最大团问题算法,并在大数据计算背景下对融合单层图划分方法和多层图划分方法的MapReduce框架和Spark框架进行优缺点分析。此外,比较k-core方法与k-community方法的应用场景,从算法分类的角度总结不同类型算法的优缺点,对求解大规模图例最大团问题的确定型算法进行梳理,并对代表性的求解算法在公开数据集中的表现进行对比分析。基于分析结果,指出不同算法在求解大规模图例最大团问题时需要重点关注的方面,并展望了智能优化算法、分层式深度强化学习方法、图结构相变分析技术的未来研究方向。

关键词：最大团问题大规模图例图划分确定型算法 core结构

来源：评论

学校读者我要写书评

暂无评论

装箱问题的算法及最新进展

引用

计算数学 2016年第3期38卷 257-280页

作者：刘明明童小娇戴彧虹湘潭大学数学与计算科学学院湖南湘潭411105 湖南第一师范学院数学与计算科学学院长沙410000 中国科学院数学与系统科学研究院北京100190

装箱问题在经济社会发展中扮演着重要的角色,该问题研究的是寻找较好的布局方式,尽可能实现利益的最大化.装箱问题具有NP-难性质,其理论和应用研究存在一定的挑战,但因其有广泛的应用背景而受到研究者高度的关注.本文主要总结近几十年... 详细信息

装箱问题在经济社会发展中扮演着重要的角色,该问题研究的是寻找较好的布局方式,尽可能实现利益的最大化.装箱问题具有NP-难性质,其理论和应用研究存在一定的挑战,但因其有广泛的应用背景而受到研究者高度的关注.本文主要总结近几十年来装箱问题的研究成果,特别针对一维、二维和三维单目标装箱问题和算法,以及多目标装箱问题的算法进行概括和总结,并提出装箱问题算法上有待进一步的研究工作.

关键词：装箱问题确定型算法一般启发式算法现代启发式算法

来源：评论

学校读者我要写书评

暂无评论

切平面在混合整数非线性规划中的应用

切平面在混合整数非线性规划中的应用

引用

作者：达林北京交通大学

学位级别：博士

混合整数非线性规划(Mixed Integer Nonlinear Programming,MINLP)是一类包含连续和整数变量的非线性规划问题。MINLP是整数规划的一个重要分支,近几十年来MINLP的应用有了快速的发展,其应用领域包括流程工业、金融、工程、管理科学和... 详细信息

混合整数非线性规划(Mixed Integer Nonlinear Programming,MINLP)是一类包含连续和整数变量的非线性规划问题。MINLP是整数规划的一个重要分支,近几十年来MINLP的应用有了快速的发展,其应用领域包括流程工业、金融、工程、管理科学和运筹学等各个领域。MINLP问题的求解算法包括确定型算法和启发式算法,确定型算法是将难于求解的MINLP问题分解为相对容易求解的混合整数线性规划问题(Mixed Integer Linear Programming,MILP),其中一类分解方法是通过投影及对偶等方法将MINLP问题分解为MILP问题,另外一类是利用迭代构造切平面的方法将原问题分解为简单问题。本文的目标是通过对求解凸MINLP问题的各种确定型算法的研究,明确切平面在确定型算法中的重要作用,利用切平面的构造方法对已知算法进行改进,并争取构造出新的算法。本文首先给出了切平面在确定型算法中的作用,给出了切平面构造的位置和方法与各种算法收敛速度的关系,得出结论:切平面的构造影响算法的收敛速度,一般来说在非线性可行域边界上构造切平面的算法具有快的收敛速度,非线性可行域边界上构造的切平面称为支撑超平面;又MINLP问题的性质要求最优解为整数点,因此如果可以给出在整数点处快速生成支撑超平面的方法,就得到了一个简洁且收敛速度快的确定型算法。基于此我们给出了求解MINLP问题的支撑超平面算法的一般形式,并证明了其收敛性,同时提出了三个具体支撑超平面算法,分别为平行下降支撑超平面算法,基于内点的支撑超平面算法和不基于内点的支撑超平面算法。外逼近(Outer Approximation,OA)算法是求解MINLP问题的一个重要算法,有着很广泛的应用,该算法的缺点是需要利用两个NLP问题的求解。我们将SHP算法的思想引入到OA算法中,给出改进的OA算法,我们称新的算法为EOA(Extended Outer Approximation,EOA)算法。在EOA算法中,当第一个非线性规划问题无解时,利用Vinott's SHP算法生成一个支撑超平面,替换OA算法中通过求解第二个NLP问题生成的切平面。新算法继承了OA算法在非线性可行域边界整数点生成切平面的优势,同时减少了NLP问题的求解次数。启发式算法和确定型算法是求解MINLP问题的两个不同类型的算法,确定型算法在求解MINLP问题时可以保证解的全局最优性,但对大规模问题的求解需要很长的计算时间,启发式方法不能保证解的全局最优,但求解问题时具有快速、简单的特点。本文我们给出了一种将启发式算法转化为确定型算法的切平面方法,新的算法继承了切平面方法全局收敛和启发式算法效率高的特点,并保证了算法的收敛速度和全局最优性,我们称这种算法为启发式切平面算法。

关键词：混合整数非线性规划切平面支撑超平面算法确定型算法

来源：评论

学校读者我要写书评

暂无评论

面向移动终端的指纹定位技术研究

面向移动终端的指纹定位技术研究

引用

作者：朱建勇北京邮电大学

学位级别：硕士

移动互联网和移动智能终端的不断发展使得基于位置的服务的需求越来越多,而获取用户的位置信息是实现基于位置服务的基础。由于定位准确度的不足和部署成本较高,当前的定位技术,特别是室内定位技术,还难以满足大规模应用的需要。而基于... 详细信息

移动互联网和移动智能终端的不断发展使得基于位置的服务的需求越来越多,而获取用户的位置信息是实现基于位置服务的基础。由于定位准确度的不足和部署成本较高,当前的定位技术,特别是室内定位技术,还难以满足大规模应用的需要。而基于位置指纹的定位技术,由于部署简单,定位准确度较高称为室内定位领域研究热点。本文借助于低功耗蓝牙4.0这一新的通信技术标准,对而向移动终端的指纹定位技术进行了深入的研究。针对现阶段基于位置指纹的定位技术中的关键环节和不足之处,对定位的离线训练阶段和在线定位阶段设计了一系列优化算法和解决方案。首先,通过移动终端开发的采样器采集大量RSSI数据集,分析了蓝牙4.0在室内环境的分布特征以及影响其传播的关键因素。在该实验的基础上,结合蓝牙4.0本身特征,我们提出了基于可变功率的蓝牙AP特征值提取方案。根据是否利用RSSI实数值构建指纹数据库,我们将当前室内定位算法分为两类,确定型指纹定位算法和相对性指纹定位算法。对于确定型定位算法,我们在传统KNN的定位算法基础,首先进行K-Mean算法进行指纹数据的聚类,然后采用了改进的加权KNN定位算法,提高了算法的实时性和准确性；对于相对性定位算法,我们给出了算法的实现方案,并分析了与确定型定位算法的异同。为了解决RSSI的时间迁移性问题,我们自主设计了蓝牙4.0侦测节点,通过合理的部署,实现了特殊位置节点的指纹数据的动态更新。此外,结合当前基于WiFi的指纹定位技术研究,我们采用了一种WiFi和蓝牙融合的定位解决方案,并对此进行了简要描述。本文的主要贡献在针对蓝牙4.0,提出了一套完整的基于位置指纹的定位算法。第一,根据蓝牙4.0特征,提出一种基于可变功率的特征值提取方案；第二,根据构建指纹数据库方法不同,将定位算法分为确定型定位算法和相对性定位算法两类,并进行了算法优化以及性能分析对比；最后,提出一种RSSI时问迁移性解决方案和WiFi与蓝牙融合定位方案,以供后续研究。

关键词：蓝牙4.0位置指纹可变功率确定型算法相对型算法

来源：评论

学校读者我要写书评

暂无评论

非线性全局优化的填充函数法

非线性全局优化的填充函数法

引用

作者：张杰上海大学

学位级别：硕士

最优化是一门应用相当广泛的学科，它讨论决策问题的最优选择，构造寻求最优解的计算方法并研究这些方法的理论性质及实际计算表现。最优化理论和方法的出现可以追溯到十分古老的极值问题，然而它成为一门独立的学科还是在上个世纪的40... 详细信息

最优化是一门应用相当广泛的学科，它讨论决策问题的最优选择，构造寻求最优解的计算方法并研究这些方法的理论性质及实际计算表现。最优化理论和方法的出现可以追溯到十分古老的极值问题，然而它成为一门独立的学科还是在上个世纪的40年代末，是在1947年Dantzing提出求解一般线性规划问题的单纯形算法之后。如今，最优化问题已经在经济计划，工程设计，生产管理，交通运输，国防军事等重要领域得到广泛应用，成为一门相当活跃的学科。　　全局最优化是最优化问题的一个重要分支，全局最优化问题有两个困难需要解决：一是如何从一个局部极小解出发找到更好的局部极小解，另一个是如何判定当前局部最小点已经是全局最优解的问题。全局最优化算法，从算法的构造上大体可以分为两类，即：确定型算法和随机型算法。　　填充函数法就是求解全局最优解的一种确定型算法，它的主要思想是：如果已经找到了一个局部极小x*，但它不是全局最小，可以在x*处构造一个填充函数使迭代点列离开x*所在的谷域，找到更好的点x′(即x′处的目标函数值比x*处的目标函数值更小)。然后以x′为初始点极小化原问题找到更优的局部极小点。　　本论文的主要工作是：在已有填充函数算法的基础上，力图在算法效果方面有所提高，在理论方面有所深化。其内容详细叙述如下：　　在第一章中，介绍了目前国内外主要几种常见的全局最优化算法，以及他们的特点。(这包括：D.C.规划、打洞函数法、分支定界法等、填充函数法和积分水平集算法。)对填充函数法，从算法的思想到相关理论给出了一些深入浅出的说明。　　在第二章中，对一般无约束连续全局最优化问题，提出了一个新的简单单参数填充函数。针对这个单参数填充函数设计了算法并进行了有效的数值实验，将该算法的结果与文献[81]作了对比，证明了算法的可行性和有效性。　　在第三章中，把无约束全局最优化问题的思想方法推广到求解带有约束的非线性规划问题的全局最优化问题。在较弱的条件下，在Rn空间中，对有非线性不等式约束的全局优化问题给出了一个单参数填充函数，针对这个填充函数设计了新算法并且进行了数值实验，数值试验显示，该算法是有效和可靠的。

关键词：非线性规划全局最优解填充函数法全局极小点确定型算法

来源：评论

学校读者我要写书评

暂无评论

一种无约束全局优化算法及其应用

一种无约束全局优化算法及其应用

引用

作者：褚晓勇西安电子科技大学

学位级别：硕士

该文对文献[45]中提出的一种解无约束全局优化问题的算法给出了严格的理论证明,修改了其中存在的问题,并对该算法给出了详细的几何说明.此算法适用于解决具有二阶连续可微性质的光滑目标函数的全局极值的问题.理论分析后,作者进行了大... 详细信息

该文对文献[45]中提出的一种解无约束全局优化问题的算法给出了严格的理论证明,修改了其中存在的问题,并对该算法给出了详细的几何说明.此算法适用于解决具有二阶连续可微性质的光滑目标函数的全局极值的问题.理论分析后,作者进行了大量的数值试验,结果相当满意,说明该算法是相当有效的.最后,在上述算法的基础上,将之加以改造,应用于解非线性方程和方程组,收到明显效果.

关键词：全局优化算法连续可微确定型算法非线性方程

来源：评论

学校读者我要写书评

暂无评论

NP完全性理论介绍

引用

计算机工程与应用 1984年第5期 1-33页

作者：张立昂北京化纤工学院

NP完全性理论不仅是计算机科学的重大研究课题,而且也是每个软件工作者必备的知识。M. R. Garey和D. S. Johnson合著的“COMPUTERS AND INTRACTABILITY”一书是介绍NP完全性理论的权威性著作。本刊1981年第7期已将该书附录中三百多个NP... 详细信息

NP完全性理论不仅是计算机科学的重大研究课题,而且也是每个软件工作者必备的知识。M. R. Garey和D. S. Johnson合著的“COMPUTERS AND INTRACTABILITY”一书是介绍NP完全性理论的权威性著作。本刊1981年第7期已将该书附录中三百多个NP完全问题全文刊登,现将根据该书编译的详细摘要刊出以飨读者。

关键词：多项式变换 DTM 近似算法判定问题最优化问题伪多项式时间算法确定型算法图灵归约回路长度算法设计 NP 形式定义自由变量自由变项哈密顿程序当且仅当真值赋值完全性完备性

来源：评论

学校读者我要写书评

暂无评论

理论计算机科学中的一些问题

引用

自然杂志 1985年第2期 83-87+160页

作者：洪加威北京市计算中心北京计算机学院中国科学技术大学

本期发表了两篇关于计算机方面的文章。一篇是关于计算机理论方面的,《理论计算机科学中的一些问题》一文,介绍了作者洪加威同志近年来在这领域中一些根本性的问题上所获得的成果。作者还对计算机科学的发展提出了自己的看法,颇具见地,... 详细信息

本期发表了两篇关于计算机方面的文章。一篇是关于计算机理论方面的,《理论计算机科学中的一些问题》一文,介绍了作者洪加威同志近年来在这领域中一些根本性的问题上所获得的成果。作者还对计算机科学的发展提出了自己的看法,颇具见地,值得一读。

关键词：理论计算机科学洪加威运算量复杂度多项式并行时间确定型算法数学家指数函数初等函数串行时间下界时间和空间定理快速算法

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：