凸包工作集TSP算法

TSP问题是一个NP完全问题,在现实生活中许多领域得到充分应用。通过对＂S计算几何＂中凸包算法分析,提出了一种最大凸包工作集规划TSP路径算法,能快速解决二维TSP问题。首先运用凸包算法构造城市的最大凸包工作集,将剩余城市节点根据隶属度大小加入到相应的凸包子工作集中。再应用最大凸包算法逐个划分凸包子工作集,直至子工作集中的尺度为2。最后依次访问每个子工作集头,得到TSP最短路径。实验结果表明,该算法能更快速地得到问题的近似最优解。     

R^1上β凸集的形状

从讨论R^1上的R^1上β凸包出发，归纳了R^1上所有β凸集的形状，并进一步得到R^1上的β凸集与β凸包相等的关系。     

正态分布点集的凸包加速算法及加速因子分析

研究了怎样对于服从正态分布的平面点集进行的凸包算法加速,理论上计算了最适合的加速因子,同时通过相应的加速因子得到正态点集分布的凸包算法最优复杂度O（n）。     

正态分布点集的凸包加速算法及加速因子分析

研究了怎样对于服从正态分布的平面点集进行的凸包算法加速,理论上计算了最适合的加速因子,同时通过相应的加速因子得到正态点集分布的凸包算法最优复杂度O(n)。     

一种求解对称TSP的简单候选集方法

TSP（旅行商问题）作为一种解决组合优化问题的有效方法,在近几十年来受到了广泛的研究。理论证明它是一个典型的NP难问题,为了更快捷地求解,候选集方法在多种求解算法比如LKH算法中都有用到,一般是用于产生一个接近局部最优的初始解,较少用于寻路过程中。本文提出了一种新的简单的候选集方法,它采用一种新的距离度量,更好地符合了对称TSP的寻路规则。将其应用于最大最小蚁群算法（MMAS）的寻路过程中,实验结果表明针对对称TSP问题,该方法能比基本的MMAS取得更好的性能。这种候选集方法也可以用于其他求解对称TSP问题的进化计算。     

基于夹角的凸包算法改进

针对基于夹角的二维凸包算法提出一种利用四边形初始凸包方法进行优化的思路。其基本思想是利用平面点集中4个极值点构成的四边形,摒弃掉平面点集中位于四边内部的内点,再利用夹角凸包算法对剩余点集进行凸包计算。实验结果表明,该凸包算法有效提升了原有算法的运行效率,但两个算法同样存在着无法应用于数量庞大的数据中的问题。     

E凸集及其性质

通过引入E凸集的概念,进一步探讨了E凸集的性质;定义了E凸组合,E凸包和E锥,利用E凸集的概念和性质对它们进行了探讨,获得了一些较好的结果,并证明了E凸集及E凸锥的充分必要条件.     

基于分治法和分支限界法的大规模TSP算法

利用分治法能够处理大规模问题但精度较低,分支限界法能够得到精确解但时间复杂度很高的优点,设计一种有效的基于分治法和分支限界法的大规模TSP求解方法.该算法利用聚类和凸包技术将大规模问题逐层进行有效划分,直到适合分支限界法求解的最佳规模;然后用分支限界法求出每个子问题和每层子问题间的最优解,合并而得到整个问题的解.比较实验表明:该算法在求解质量、稳定性和时间效率上有明显优势.     

快速更新挖掘最大频繁项集

更新挖掘最大频繁项目集是多种数据挖掘应用中的重要问题，其发现过程的高花费要求对高效更新挖掘算法进行研究，提出了一种快速的更新挖掘最大频繁项目集算法，其能够在原有挖掘结果的基础上，有效地挖掘出更新后的数据库中隐含的新最大频繁项目集．     

集值优化问题的最优性条件:基于广义C-子凸和伪相对内部的择一性定理的一个应用

该文首先通过伪相对内部的概念定义了广义C-子凸集值映射.其次刻画了一些伪相对内部的性质,然后利用广义C-子凸和伪相对内部的分离定理,建立了择一性定理.最后利用所得到的择一性定理,建立了一些有关广义C-子凸集值最优化问题的最优性条件.本文对参考文献中的一些结论进行了推广和改进.     

基于黄金工作集多维数值函数极小值算法

提出一种黄金工作集的多维数值函数极值优化算法。根据工作集元素的贡献度不同并结合黄金分割法将工作集划分为黄金工作集和非黄金工作集。通过保留黄金工作集元素和置换非黄金工作集元素方法,保障工作集中的元素都是最优解,从而达到加速收敛实现算法的优化。通过与人工蜂群算法的进行比较,结果证明该算法在极值收敛上具有明显优势。     

凸集的性质及其应用

(本讲适合高中) 如果对于点集M中任意两点以A,B,线段AB上的每一点都属于M,那么就称M为凸集。显然,线段、直线、圆、半平面、球和四面体等都是凸集。为了方便起见,我们将空集和单点集均算为凸集。容易证明:两个凸集的交一定是凸集,而两个凸集的并不一定是凸集。与凸集密切相关的还有两个概念:凸形和凸包。一个凸集,如果是有界闭集,则可称为凸形。包含点集M的最小凸集称为M的凸包。易见,     

软件开发中调试死锁问题的研究

为提高关联规则中频繁集挖掘的效率,将频繁集的挖掘转化为TSP问题中最短路径的求解。应用蚁群算法的思想,结合频繁项集的特点对算法进行改进,进而挖掘满足最小支持度的项的组合。实验表明,与传统的Apriori算法相比,改进后的蚁群算法能够在较短的时间里挖掘出大部分的频繁项集,可以有效地进行频繁项集的挖掘。     

块图中的团横贯集和团独立集

图的一个极大完全子图称为图的一个团．若图G的每一个块为图G的一个团,则称图G为块图．求图的一个最小团横贯集问题和最大团独立集问题分别称为MCTS问题和MCIS问题．文中给出了块图中求解最小团横贯集和最大团独立集的一个线性时间算法,并证明了块图G中的团横贯数等于团独立数,即τc（G）=αc（G）．     

基于K-均值聚类的TSP演化算法

提出一种基于K-均值聚类的TSP演化算法。该算法利用K-均值聚类技术,将TSP分为一些简单的TSP问题。在寻求最短路径时,首先所有结点用其聚类中心去代替,以聚类中心为结点构造TSP演化算法;其次,对于每一聚类,可寻求其距前面的聚类和后面的聚类最近的两结点之间的最短距离,若其中的结点较多,则再次演化得到其最短路径,若结点较少,则可用warshall算法可得到最短路径;最后对获得的最短路径进行剪接操作,可得到其更优解。     

改进免疫算法在旅行商问题中的应用

免疫算法是基于人工免疫的基本理论发展而来,它是对人工免疫理论研究和应用的扩充与发展。本文提出了一种改进的提取疫苗和注射疫苗的免疫算法,给出了该算法疫苗的形成方式,并将该算法应用在典型的组合优化问题TSP的求解中。通过50个城市TSP问题的仿真实验,表明该算法较原算法有更快的收敛速度,是一种较理想的解决TSP问题的智能优化算法。     

内部锥类凸集值优化的Henig有效性

在实赋范线性空间中考虑约束集值优化问题(vp)的Henig有效性.在内部锥类凸假设下,利用凸集分离定理,得到了Kuhn-Tucker必要条件.     

?_p范数正则化的稀疏子空间估计与聚类

稀疏子空间聚类是把子空间聚类问题松弛为凸优化问题,但这种凸近似需要满足较强的非相干性条件,且用观测数据本身作为字典进行子空间表示时,观测数据中所含的噪声、缺损、奇异样本等会增加子空间表示的误差.为解决上述问题,提出一种基于?_p范数(0相似文献   

基于遗传算法的旅行商问题的研究

巡回旅行商问题(TSP)是一个组合优化方面的问题,已经成为测试组合优化新算法的标准问题。应用遗传算法解决TSP问题,首先对访问城市序列进行排列组合的方法编码,这保证了每个城市经过且只经过一次。接着生成初始种群,并计算适应度函数,即计算遍历所有城市的距离。然后用最优保存法确定选择算子,以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。最后用MATLAB来实现算法,仿真后,观察路径,得出最终结果。     

一种新的频繁闭项目集挖掘算法

为了解决频繁闭项目集挖掘中时间和存储开销大的问题,提出了一种基于FC-tree（频繁闭模式树）的频繁闭项目集挖掘算法max-FCIA（最大频繁闭项目集挖掘算法）.该算法利用哈希表映射事务数据库,通过对哈希表进行操作从而得到所有频繁项目集的支持度,进而生成包含所有频繁项目的有序树.经过剪枝处理的有序树就是包含所有最小频繁闭项目集的FC-tree,最后用最小频繁闭项目集生成频繁闭项目集.实验结果表明,该算法通过映射事务数据库,减少了扫描数据库所浪费的时间,提高程序执行效率.另外,运用有效的剪枝策略,避免了不必要候选项目集的生成,节省了存储空间,实验证明该算法是有效的.