一种混合化学反应优化算法求解最小顶点覆盖问题

最小顶点覆盖问题是组合最优化问题,在实际应用中有较广泛的应用,是一个NP难问题。论文针对最小顶点覆盖问题给出了一种混合化学反应优化求解算法。首先根据无向图的邻接矩阵表示法,设计了参与化学化反应的分子编码和目标函数;同时把贪心算法思想创造性地融入到化学反应优化算法的四个重要反应算子中,以加快局部较优解的搜索过程;最后通过模拟化学反应中分子势能趋于稳定的过程,在问题的解空间中搜索其最优解。模拟实验结果表明,该算法对于求解无向图的最小顶点覆盖问题是有效的,并且在求解效率等方面有一定的改善。     

带权无向图中反馈顶点集的固定参数枚举算法

反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).     

最小顶点覆盖快速降阶算法

通过定义判别函数来判别顶点覆盖作用的优劣,得出一个把顶点加入到最小顶点覆盖集的一般化规则,并得出该规则在多种具体情况下的应用定理,在此基础上给出了一个快速降阶算法,该算法能确定某些顶点应该在最小顶点覆盖中,某些顶点不应该在最小顶点覆盖中,达到降低原问题的规模和求解难度的目的.该算法既可以单独使用,又可以与算法结合来达到更好的结果,文中还给出了应用实例及其分析.     

基于CHI值特征选取和覆盖的文本分类方法

利用CHI值特征选取和前向神经网络的覆盖算法,通过对文本进行分词的预处理后,实现文本的自动分类.该方法利用CHI值进行特征选取即特征降维,应用覆盖算法进行文本分类.该方法将CHI值特征选取和覆盖算法充分结合,在提高了分类速度的同时还保证了分类的准确度.应用该方法对标准数据集中的文本进行实验,并在不同的维数上与SVM算法、朴素贝叶斯方法的实验结果进行了比较.结果表明,与SVM算法和朴素贝叶斯方法相比较,覆盖算法在准确度上更好.并且,维数的选择对分类的精确度影响很大.