Kruskal算法的研究与改进

在用Kruskal算法求解最小生成树时,选择边的次数至少为n-1次;当边数m和顶点数n满足关系m≤2n-2时,可以对Kruskal算法进行改进.本文用改进的算法求解,选择边的次数最多为n-1次.改进算法的思想为删除图中权值最大,且删除后不影响图的连通性的边,直到只剩下n-1条边.改进了的算法在理论上减少了求解时间.     

基于图聚类的脱机手写文档图像文本行分割

提出了一种基于自适应游程平滑算法和基于改进的最小张树聚类的文本行分割算法,该算法基于图的集成聚类的框架用以进一步解决文本行分割的问题,该框架可以很容易地推广到对更多的单一算法进行融合.在该融合框架中,由对应于连通部件的顶点以及顶点对之间的边构成文档图,边上的权值由两个单一文本行分割算法的结果决定.于是,文本行分割的任务就转化为如何以最小代价对文档图进行划分的问题.该融合算法在哈尔滨工业大学多人手写数据库上取得了较好的效果,召回率为99.31%,错误率为0.94%.     

基于改进Otsu算法的生菜叶片图像分割方法

针对传统的Otsu算法计算量大、实时性差等缺点,提出了一种新的PSO+Otsu(S)分割方法.将RGB颜色空间转换成HSV颜色空间,并提取S分量图像.针对基本粒子群优化算法提出一种新的惯性权重系数w更新策略,并利用改进的粒子群优化算法搜索最优阈值,将搜索到的最优阈值作为Otsu算法的分割阈值,并对S分量图像进行分割,最终得到生菜叶片分割图.结果表明:提出的生菜叶片图像分割方法不但适合单叶片图像分割,而且适合冠层叶片图像分割;运用本算法分割单个生菜叶片图像以及生菜冠层图像时程序运行时间分别为118,126 ms,迭代次数分别为6,5次,相比于Otsu算法以及标准PSO+Otsu算法,本算法不仅有效缩短了程序运行时间,而且提高了图像分割的准确率,具有较好的实时性.     

一种基于改进FCM的自动图像分割算法

针对FCM进行图像分割时需要人为确定聚类数的问题,提出一种改进的基于FCM的图像分割算法.该算法先对图像进行4叉树结构的子图分解(即原图等分为2×2的4幅子图,子图再等分为2×2的4幅子图),待子图满足一定条件时进行聚类数为2的FCM聚类分割;然后将分割好的区域根据其大小及相邻区域直方图的巴氏距离进行合并,得到最终的分割结果,从而避免了聚类数目的直接确定.实验结果表明:该算法能够获得很好的分割效果;对子图进行聚类分割减少了每次参与聚类的对象数,从而在一定程度上降低了算法的计算量.     

基于最优家族遗传算法的改进二维熵图像分割

分析了最大二维熵图像分割算法的基本原理,提出了一种改进的二维熵图像分割算法.该算法同时考虑了孤立像素点的灰度信息和像素点的空间相关性,并对目标的边缘进行检测,因此保留了更多的图像边缘信息.引入搜索区域、群体规模可变的最优家族遗传算法对阈值进行搜索,不仅提高了算法的搜索速度,而且避免了早熟现象.实验结果表明,分割256×256的Lena图100次,平均时间为1 5937s,平均进化代数为2 5037,且边缘信息得到了很好保留.改进算法在分割速度和分割精度上比普通二维熵的分割算法有显著的提高,说明了算法的有效性.     

改进的快速模糊C均值聚类图像分割算法

为了提高图像分割的运算速度,该文在将传统模糊C均值(FCM)聚类算法应用于图像自动分割的基础上,提出一种改进的快速图像分割算法。将图像从像素空间映射至其对应的灰度直方图特征空间,实现在特征空间进行数据聚类分析以减少聚类样本数量。依据灰度直方图特性,通过曲线拟合方法获得图像的聚类数及初始聚类中心。实验结果表明,在有效分割图像的基础上,该算法的运算迭代次数减少了约10%,运行时间减小了约6%。     

一种改进的并行蚁群优化求解算法

为了提高并行蚁群优化算法的求解性能,对ACO算法进行了改进.针对有明显聚类特征的大规模TSP问题,充分利用问题本身所具有的特征,提出了一种带聚类处理的蚁群算法,该算法比较ACS算法可以在更短的时间内找到相同质量的解,而且在相同的运行时间内,该改进算法总能找到最好的解.在VC++环境下进行仿真实验,求解了TSP库中的实例pr136、pr107,分别得到了其最短距离,结果表明了编程思路的正确性及高效性.     

基于改进Dijkstra算法的最短路径搜索仿真

提出基于Dijkstra算法的最短路径搜索改进算法,通过设置高效的优先目标搜索区域,减少大量无意义运算,达到提高搜索效率的目的.以淄博市交通道路图(局部)为例建立系统仿真模型,分别以两点间距离系数和拥堵系数作为权值进行系统仿真,得出了基于不同权值的最短路径求解结果,并对算法改进前后测试数据进行对比分析.结果表明,基于改进Dijkstra算法实际运行时间均值仅占Dijkstra算法运行时间均值的23%以下.     

一种大规模稀疏中国邮递员问题快速求解方法

针对现有中国邮递员问题求解方法在大规模稀疏路网图上求解效率的瓶颈,提出一种在可接受时间范围内求得可行解的基于蚁群优化的快速求解方法.该方法针对Euler回路求解的奇偶点图上作业法的第二阶段,采用蚁群算法进行求解,同时根据大规模稀疏路网图的特性基于密度峰值聚类算法对方法进行改进：首先在蚁群算法求解前对大规模稀疏路网图进行聚类分割;其次根据邻近节点覆盖率对分割后的节点群进行合并;最后通过改变部分节点所属聚类使各节点群内部节点个数均为偶数.实验结果表明：在奇偶点图上作业法所能支持的节点规模下,该方法可求得与确定性算法相同的最优解,并在运算时间上达到约10倍的效率优化;且该方法在大规模稀疏路网图下可有效提高计算效率,并在可控时间范围内得到优化的可行解,针对5 000个节点规模的路网图最快可在60 s内完成求解.     

利用视觉显著性的前景目标分割

针对图像中的前景目标分割问题,提出一种视觉显著性引导的前景目标分割算法.对原始图像进行预处理后分解为互不重叠的超像素区域.将这些区域构成一个无向图,相邻两个区域间存在边,通过计算相邻区域间的特征差异得到边的权值.提取图像边缘的超像素区域作为背景区域,利用无向图计算各超像素区域相对于背景区域的视觉显著性,得到初始显著图.对初始显著图进行改进和优化,根据视觉显著性计算结果采用自适应阈值进行前景目标分割.在公开的图像数据集MASR-1000、ECSSD、Pascal-S和SOD上进行实验验证,并和目前流行的算法进行对比.结果表明,本研究算法在查准率、召回率、平均绝对误差及F-Measure等方面优于目前流行的几种算法,用于图像和视频的前景目标检测与分割是正确有效的.     

3－W_n图的优美性

证明了在齿轮图ｎ个齿的顶端各加上三条长度为１的边所得的图是优美的，从而对齿轮图的优美性作了推广．     

关于Km，n并图的优美性

对于自然数k，m，n，本文给出一类非连通图↑k∪↓i=1Kmi.ni；通过构造标号函数的方法，证明了当max{mi，ni}≥3，min{mi，ni}≥2(i=1，2，…，k)时这类图既是优美图，也是交错图；从而给出构造一类任意个图的并图是优美图的一种方法，拓宽了优美图及其应用的道路。     

图U∧C_(4,m_i)from i=1 to n的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了一类任意n个二分图∧C4,m的并图4,1inmiC=U∧是优美图,且是交错图.     

再论图Pn^3的优美性

给出图Pn3的另一种优美标号,证明其图是优美图且是交错图.另外指出文献[1]中的一个错误和给出了相应正确的结果,同时证明了严谦泰,张忠辅给出的标号以及我们改正的标号都是交错的.     

任意n个完备二分图的并图的优美性

优美图是图论中的一个重要分支,至今对非连通优美性的研究并不多,特别是对n个图的并图的优美性研究就更少.本文证明了任意n个完备二分图的并图是优美图,且是交错图.     

一类串图的优美性

给出了一些图的优美标号,特别给出了串图ωm1,m2,mn,mn＋1当m1,m2,…,mn≡0（mod4）,mn＋1≡3（mod4）的优美标号,以及串图ωm1,m2,,m2n当mi≡2（mod4）（i=1,2,…,2n）,m2k-1＜m2k,（k=1,2,…,n）时的优美标号.     

Hamilton图的代数刻划

运用矩阵方法,给出了连通图是Ｈａｍｉｌｔｏｎ图的一个代数刻划     

图∪ from i=1 to n(F_(mi,4))的优美性

给出图∪ni=1Fmi,4 的一类非连通图 ,并证明这类图是优美图 ,且也是交错图 .     

几类7点7边图的图设计与最优填充

设λKv是λ重ν点完全图，G是无孤立点的有限简单图。将G－设计（G－填充）记作（ν，G，λ）－GD（（ν，G，λ）－PD）是指一个序偶（X，B），其中X是完全图Kν的顶点集，B是Kν中间构于G的子图（区组）的集合，使得Kν中每条边恰好（至多）出现在B的λ个区组中。讨论了3类7点7边图Gi(i=1,2,3)的图设计及最优填充问题，并给出了（ν，Gi,1)-GD及（ν，Gi,1)-OPD(i=1,2,3)存在的谱。     

图C4∪St(m)的k优美性及算术性

给出一类非连通图C4∪St(m). 论证当k>1(k∈N)时, 该图是k优美图; 当k>d+1(d>1, d∈N)时, 图C4∪St(m)是(k,d)算术图.