公路交通网络可靠度的割集算法

提出了一种适合大型公路交通网络的割集搜索算法CSA-CJ.该算法利用二进制数分割无向图的顶点集,通过对子图各顶点的关联集的运算产生相应的割集.     

市内集送货问题的混合禁忌搜索算法

针对单程多次装卸的市内集送货问题的数学模型,结合Clarke-Wright节约算法和2-opt邻域搜索算法设计混合禁忌搜索算法,给出算法初始可行解的生成策略,设计相应的候选集构造方法,并阐述了基于均衡原理的特赦准则和动态的禁忌长度选取策略.通过计算实例,说明了混合禁忌搜索算法求解市内集送货问题的有效性.     

树的二分全优美标号

一个有q边的连通图G的一个标号是一个映射f,使得图G顶点分配给不同的整数,如果图G的所有边标号集等于{1,2,…,q},则称f是图G的一个优美标号,称G是优美图.图的优美标号可用于解决Rosa分解猜想,这就需要证明每一棵树是优美的,然而它又成为一个未解决的难题.已知树的二分全优美标号可得到一些逼近优美树猜想的结果,因此可考虑一个弱于优美树猜想的猜想:一棵被删除所有叶子后余图恰是一棵毛毛虫树的树T是二分全优美的.树T的一个二分标号是一个双射f,且存在一个正整数k,使得f(u)≤k≤f(v),则顶点u和v属于树T的顶点集的二部分划分的不同部集.定义了全优美标号空间和k?二分全优美树,证明了一类二分全优美树,给出一些大型二分全优美树的构造方法.     

图的增广支配数

增广ｐ一中心是在原有的服务设施基础上增加ｐ个设施为网络中的顶点提供紧急服务,因此增广ｐ一中心问题比经典的ｐ一中心问题更具有实际意义。本文提出了图的增广支配集、增广支配数的概念,这些概念与增广ｐ一中心问题密切相关,给出了求任意图全部极小增广支配集的布尔方法,提出了一个线性时间的算法求树的增广支配数。     

列流线偏移描绘自动化

基于图论理论分析了列流图的组成特性,以解决列流线折点自动搜索问题.提出列流线折点搜索算法和列流线偏移描绘算法.采用基于节点信息表绘制列流图.开发了列流图自动生成数据库系统.用实例表明了算法及软件有效性和可行性.     

交通网络连通可靠性评价方法研究

本文从连通可靠性角度出发,分析了连通可靠度的评价方法,给出了利用交点法评价起终点连通度的路径集和割集确定方法,即将路径集和割集分别转化为原网络和对偶网络里寻找n条最短路径问题.交点法仅利用起终点间的部分路径集合和割集,降低了计算复杂性,并用示例网络对交点法进行了数值检验.本文对考虑路段相关性下的连通可靠度评价方法进行了探讨,最后对连通可靠度研究进行了总结和展望.     

结合概率搜索定界的入度统计最短路径算法

Dijkstra 经典最短路径算法包括大量的排序运算,且需要对图中所有顶点进行计算,效率较低.本文针对有向网络,提出了与概率搜索定界结合的入度统计最短路径算法.该算法通过按概率搜索得到一条较短路径,依据路径长度和有向网络结构特征确定和顶点序号相关的节点阻抗最大值;采用入度统计算法代替经典的标号算法,在计算过程中根据节点阻抗最大值,采取一定方式剔除无效顶点(不在最短路径内的顶点),简化网络结构.本文提出的算法不需要进行排序运算,简化了运算过程,并且可以剔除大量的无效顶点,降低了网络复杂度.算例分析表明,相对于Dijkstra算法,结合概率搜索定界的入度统计算法大幅度提高了运算效率,具有实用性.     

单圈图的Steiner(n-1)-Wiener指标

令G是一个连通图.当2≤k≤n-1时,图G的Steiner k-Wiener指标表示V(G)中所有k子集S的Steiner距离之和.如果一个连通图具有相同的顶点数和边数,则称为单圈图.通过对单圈图做变换,给出了单圈图Steiner (n-1)-Wiener指标的计算式,确定了单圈图Steiner (n-1)-Wiener指标的上、下界,并刻画了达到上、下界时的极图.     

含邻域交的Hamilton及Hamilton连通图

对任意一对不相邻的顶点u和v,α(u,v)表示图G中含u,v的最大独立集的顶立数.通过讨论邻域交|N(u)∩N(v)|与α(u,v)的关系,本文得到了关于Hamilton及Hamilton连通图的新的充分条件,这些结果推广了现有的有关结果.     

图的邻接树图是哈密尔顿的

图G的邻接树图就是这样的图,以图G的生成树为顶点的图,两个顶点之间相邻,当且位当相应的两个生成树是相邻的.1986年蔡茂诚提出猜想:任何简单图的邻接树图都是哈密尔顿图.本文证明了这一猜想,所得的结论比猜想本身还要强.     

大规模训练集的快速缩减

为了进一步减少支持向量机的训练时间,提出了一种基于类别质心的训练集缩减算法.该算法根据样本的几何分布去除训练集中大部分非支持向量.对样本规模在104数量级的数据集进行了训练实验,结果显示,在基本不损失分类精度的情况下,训练时间比直接用SMO(序贯最小优化)算法减少30%,说明该算法能有效地提高支持向量机的训练速度.     

多目标最短路径模型及算法

为获得满足决策者需要的多目标最短路径问题的有效路径,建立了多目标最短路径模型,并提出了综合k-最短路径算法和多目标格序决策方法的多项式算法.该算法根据决策者可以接受的各单目标的上限,用k-最短路径算法,分别确定各单目标的可行路径集及其交集.再用多目标格序决策方法,比较交集中的有效路径,最终获得决策者满意的路径.     

Network Decomposition and Maximum Independent Set Part Ⅱ：Application Research

According to the researches on theoretic basis in part I of the paper，the spanning tree algorithms solving the maximum independent set both in even network and in odd network have been developed in this part，part Ⅱ of the paper．The algorithms trans form first the general network into the pair sets network，and then decompose the pair sets network into a series of pair subsets by use of the characteristic of maximum flow passing through the pair sets network．As for the even network，the algorithm requires only one time of trans formation and decomposition，the maximum independent set can be gained without any iteration processes，and the time complexity of the algorithm is within the bound of O(｜V｜^3)．However，as for the odd network，the algorithm consists of two stages．In the first stage，the general odd network is transformed and decomposed into the pseudo-negative envelope graphs and generalized reverse pseudo-negative envelope graphs alternately distributed at first；then the algorithm turns to the second stage，searching for the negative envelope graphs within the pseudo-negative envelope graphs only．Each time as a negative envelope graphhas been found．renew the pair sets network by iteration at once．and then tum back to the first stage．So both stages form a circulation process up to the optimum．Two available methods，the adjusting search and the picking-off search are specially developed to deal with the problems resulted from the odd network．Both of them link up with each other harmoniously and are embedded together in the algorithm．Analysis and study indicate that the time complexity of this algorithm is within the bound of O(｜V｜^5)．     

对APriori算法的一个改进

介绍了关联规则挖掘的研究情况，并在分析关联规则的数据挖掘算法的基础上，针对Apriori算法进行深入研究，提出了Apriori—1算法，新算法在计算候选大项集支持度所涉及的记录数目将小于事务数据库中原始的记录数目，提高了原算法的效率，具有一定的实用性．     

SVM入侵检测系统中数据预处理方法改进

由于网络数据的复杂性和不规范性制约着SVM分类器的精度,当前被广泛使用的数据预处理方法显得过于单一。因此,提出一种改进的数据预处理方法。首先,利用异构数据集上的奇异距离函数HVDM对数据进行归一化处理;然后,使用最近邻法对数据集修剪得到最后的训练样本,并且通过实验证明该方法可以提高SVM分类器的精度。     

Application of Auction Algorithm for Shortest Paths to Traffic Assignment

Auction algorithm is a new and simple algorithm for finding shortest paths in a directed graph proposed by Prof. Bertsekas, whose application has been extended to solve a variety of linear network flow problems. In this paper, auction algorithm for shortest paths is introduced and its characteristics are analyzed. The paper compares the auction algorithm with other algorithms widely used such as label-setting algorithm and label-correcting algorithm. The auction algorithm is particularly applicable to parallel computation and to the solution of a large-scale sparse network, which precisely meets the requirements of the traffic assignment. The algorithm is easy to program. Through a variety of measures the basic algorithm can be improved and speeded up and the computation speed can be increased by several times. The auction algorithm can be adopted in various traffic assignment methods. It can be used efficiently in the case of multiple origins and a single destination, and a single origin and multiple destinations. Different origin sets and destination sets are determined in accordance with the requirement of the traffic assignment. It is not required any more to find the shortest paths connecting any node pairs, so a lot of computation can be avoided and the computing time can be reduced by the use of the auction algorithm in the traffic assignment. Auction algorithms can thus be broadly applied in the transportation fields.     

Feature Selection for SVM Classifiers Based on Discretization

The rough sets and Boolean reasoning based discretization approach （RSBRA） is not suitable for feature selection for machine learning algorithms such as neural network or SVM because the information loss due to discretization is large. A modified RSBRA for feature selection was proposed and evaluated with SVM classifiers. In the presented algorithm, the level of consistency, coined from the rough sets theory, is introduced to substitute the stop criterion of circulation of the RSBRA, which maintains the fidelity of the training set after discretization. The experimental results show the modified algorithm has better predictive accuracy and less training time than the original RSBRA.     

道路网络容量的多端最大流算法

道路网络作为无向网络,其容量分析必须考虑其起始点和终止点的随机开放特性.采用图论的多端最大流算法和衍生割集算法,研究了道路网络容量的计算方法.分析结果表明,新方法能提高计算效率,它不仅适应大规模道路网络复杂性,而且适应路网起、终点开放的特性.     

策略性库存路线的PPSA算法

总结了Larson的SIRSA(Strategic Inventory and Routing Saving Algorithm)启发式解法,针对其补充周期短的缺陷,提出了以库存补充周期和补充阶段为变量的PPSA(Period and Phase Saving Algorithm)启发式解法。计算结果表明,当车辆每作业一次能补充的客户数较多,且客户间最大的可能补充时间间隔差别较大时,PPSA算法对车辆的需求明显少于SIRSA算法。     

基于矩阵的多段支持度关联规则挖掘算法

为有效提高关联规则挖掘算法效率,提出了一种基于矩阵的多段支持度关联规则挖掘算法,该算法通过一次数据库扫描将事务数据存放在矩阵中,利用矩阵进行支持度的计算和频繁集的寻找,同时将项集支持度分段计算的思想应用其中,减少候选集生成,实验表明,算法效率得到了较大提高。