共查询到19条相似文献,搜索用时 78 毫秒
1.
超平面覆盖问题是计算几何领域中一类典型的NP难问题,在实际生活中有着广泛的应用.针对NP难问题的难解性,人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性,不能满足实际应用中的各种需求,人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,并利用深度有界搜索树的方法,提出了一个时间复杂度为O(k3(0.736k)k+nlogk)的确定性参数算法,极大地改进了当前最好的结果O((k/2.2)2k+nlogk).通过对上述算法在高维空间中的进一步扩展,提出了关于超平面覆盖问题时间复杂度为O(dkd+1(dk)!/((d!)kk!)+nd+1)确定性参数算法,对当前的最好结果O(kd(k+1)+nd+1)有较大改进. 相似文献
2.
3.
4.
一种借助邻接矩阵求任意图最大团的方法 总被引:1,自引:0,他引:1
最大团问题是图论中重要的NPC问题。文章以一种新的方法,通过矩阵运算选择图上可能存在最大团的分支,进而实现求解最大团的问题。算法的每一个步骤都可以用成熟的并行方法替代。 相似文献
5.
针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题,提出一种新的基于匹配交叉的Memetic算法.该算法提出交叉匹配度的概念,用来估计两个体交叉所能获得的最佳适应值.通过匹配度的计算对交叉方向的选择进行控制,保证了交叉操作以较大的概率生成新的优良模式.在40个最大团问题标准算例上的测试结果表明,新算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法. 相似文献
6.
7.
基于蚁群算法求解最大团问题 总被引:2,自引:0,他引:2
最大团问题是一种典型的NP完全问题, 是图论中一个经典的组合优化问题.研究将蚁群算法应用于求解最大团问题,提出一种求解最大团问题蚁群算法.通过定义最大团问题蚁群算法中的各元素,并改进了蚂蚁搜索解的方法,有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷.仿真实验表明,图中的顶点数较多时,也取得了较好的结果. 相似文献
8.
讨论标号树的Neville编码的编解码算法.文献中常见的第2种Neville编解码算法需要O(n log n)时间.近期研究文献指出至今尚未找到第2种Neville编解码的线性时间算法.本文对第2种Neville编解码问题的本质特征进行较深入的分析,从简单算法出发,逐步简化,得到一个非常简单实用的O(n)时间Neville编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴. 相似文献
9.
一种基于分划思想的Hilbert曲线快速编码算法 总被引:1,自引:0,他引:1
Hilbert曲线是多维结构降维的重要手段,在多维索引结构和图像处理等方面有着广泛的应用。传统的Hilbert编码是通过复制部分Hilbert曲线,运用旋转等操作完成整体结构,时间复杂度为O(n^2)。通过对Hilbert曲线基本特征的研究,本文提出了一种新的基于分划的Hilbert编码方法,新算法的时间复杂度为O(nlogn),本文最后通过实例 对算法进行了分析。 相似文献
10.
11.
最大团问题是一个经典的组合优化问题,在蛋白质功能推测、竞胜标确定、视频对象分割等领域有广泛的应用。随着图例规模的增大,最大团问题求解难度增加,常规图例最大团求解算法已逐渐被大规模图例最大团求解算法取代。介绍求解大规模图例最大团问题的技术支撑点,重点总结基于大规模图例的最大团问题算法,并在大数据计算背景下对融合单层图划分方法和多层图划分方法的MapReduce框架和Spark框架进行优缺点分析。此外,比较k-core方法与k-community方法的应用场景,从算法分类的角度总结不同类型算法的优缺点,对求解大规模图例最大团问题的确定型算法进行梳理,并对代表性的求解算法在公开数据集中的表现进行对比分析。基于分析结果,指出不同算法在求解大规模图例最大团问题时需要重点关注的方面,并展望了智能优化算法、分层式深度强化学习方法、图结构相变分析技术的未来研究方向。 相似文献
12.
13.
和声搜索(HS)是一种已广泛应用于连续优化问题的元启发式方法。针对典型的组合优化问题——多维背包问题(MKP),提出一种改进二进制和声搜索(IBHS)算法。算法通过伯努利随机过程生成二进制群体,在候选和声生成算子中,引入动态自适应参数,通过算法参数的自适应调整来协调算法的全局搜索和局部搜索,并提出一种新的更有效的衡量商品多维加权价值密度的方法用于二进制个体修正和优化;引入精英局部搜索机制进行协同寻优,提高IBHS的收敛速度。通过求解10组不同规模的典型多维背包算例和与贪心二进制狮群优化(GBLSO)算法、改进的差分演化(MBDE)算法以及二进制修正和声(BMHS)算法的对比分析,实验结果表明,所提算法在求解MKP时有具有良好的收敛效率、较高的寻优精度和很好的鲁棒性。 相似文献
14.
针对城市物流配送系统中的两级定位.路径问题,采用人工蜂群算法对其进行求解,并扩展算法中的选择策略,即在基于适应度选择策略和锦标赛选择策略2种常用策略基础上,提出一种带参数控制的锦标赛选择策略。通过对大、中、小规模算例进行仿真实验,证明人工蜂群算法能在合理的计算时间内有效求解两级定位一路径问题。其中,采用基于适应度选择策略的人工蜂群算法求解速度较快,采用锦标赛选择策略的人工蜂群算法求解到的最好解质量较高,采用带参数控制的锦标赛选择策略的人工蜂群算法求解得到最差解的质量及解的稳定性较好。 相似文献
15.
支持向量回归机(Support Vector Regression,SVR)是建立在统计学习理论上的一种机器学习方法,主要用来处理回归问题。选取到合适的参数是实现支持向量回归机算法优势的前提,但在实践中仍然存在模型参数选择困难的问题。群智能算法主要是模仿自然界生物种群社会行为规律的元启发式算法,具有简单性、自适应性、灵活性等特点,现已成为非线性参数寻优方法的研究热点。系统综述了利用群智能算法优化支持向量回归机参数的研究进展。在介绍支持向量回归机基础理论之后,系统分析了常见群智能算法及其改进方法实现支持向量回归机参数优化选择的优点与不足,并对未来的研究方向及挑战做出展望。 相似文献
16.
17.
并行机间歇过程生产调度的遗传局部搜索算法 总被引:5,自引:0,他引:5
研究了一类集成分批的并行机间歇过程调度问题(parallel machine batch process scheduling problem,简称PBPSP),将此问题转化为固定费用运输问题(6xed charge transportation problem,简称FCTP)后,提出了具有集中邻域搜索机制和局部最优逃逸机制的遗传局部搜索算法(genetic local search algorithm,简称GLSA).GLSA算法用先根遍历边排列模式编码生成树解,具有高效的子树补充式单点交叉操作.将基于网络单纯型方法的邻域搜索作为变异算子,并提出了连续随机节点邻域搜索的集中邻域搜索策略以及随机旋转变异与全局邻域搜索相结合的局部最优逃逸策略,极大地强化了遗传局部搜索算法的全局寻优能力.实验表明:GLSA算法获得的解质量优于基于排列编码的遗传算法和基于矩阵编码的遗传算法,得到了所有Benchmark问题的最优解,且具有高鲁棒性.针对一定规模的FCTP问题,GLSA算法比Tabu启发式搜索算法具有更高的获得最优解几率. 相似文献
18.
为有效解决复杂的柔性作业车间调度问题,以最小化最大完成时间为目标,提出了一种结合了变邻域搜索算法的新型改进Jaya算法来求解。为不断挖掘和优化探索最优解,提高算法求解的结果质量,通过Jaya算法的原理重新提出一种解的更新机制,此外在Jaya算法原理的基础上嵌入一种变邻域搜索策略,并在传统邻域结构的基础上重新设计了两种新型邻域结构,扩大了邻域搜索范围,增强了Jaya算法的局部搜索能力,避免算法因失去解的多样性从而陷入局部最优。运用基准算例对该算法的求解性能进行了验证,并与其他算法的仿真结果进行对比,结果表明该改进算法的求解效率更高。 相似文献