计数型二次序贯网图检验

序贯概率比检验(SPRT)是应用非常广泛的抽样检验方法, 序贯网图检验在控制最大样本量方面很好地改进了SPRT, 但其结果还有进一步改进的余地, 为此, 我们建立了二次序贯网图检验, 计算结果表明, 它比原先的计数序贯网图检验有更好的效果.     

同顺序流水作业排序问题的一个启发式算法

本文主要给出了同顺序m×n排序问题初始序的选取方法以及通过计算可避免出现高重循环的初始序的排序算法,然后又给出了利用矩阵可行线性质将初始序调试成较优序的可行方法.利用该文方法对n=15,m=3～14的144个例题计算,得出平均相对误差为3.145%的结果,对于m=3与m=4的128个例题计算,得出平均相对误差为0.6306%.统计结果表明该方法可在实际中进行应用.     

利用分片贪婪算法求解分片稀疏恢复问题

在实际应用中,有一些信号是具有分片的结构的.本文我们提出一种分片正交匹配追踪算法(P\_OMP)来求解分片稀疏恢复问题,旨在保护分片信号中的分片结构(或者小尺度非零元).P\_OMP算法是基于CoSaMP和OMMP算法的思想上延伸出的一种针对分片稀疏问题的贪婪算法. P\_OMP算法不仅仅具有OMP算法的优势,还能够在比CoSaMP方法更松弛的条件下得到同样的误差下降速率.进一步,P\_OMP~算法在保护分片稀疏信号的尺度细节信息上表现的更好.数值实验表明相比于CoSaMP, OMP, OMMP和BP算法, P\_OMP算法在分片稀疏恢复上更有效更稳定.     

半序集的碰撞数与分层深度贪婪算法

设Ｐ＝（Ｘ，≤）是一个半序集，本文在关于碰撞数的深度贪婪算法的基础上，直接证明了对任意的Ｐ存在一个最优的ＤＬＧ扩张，给出了ＤＬＧ半序集的定义，并证明了半序集Ｐ是ＤＬＧ半序集的一个充分条件，最后给出了ＤＬＧ扩张算法。     

序约束下正态总体均值和方差极大似然估计的数值解法

本文讨论了k个独立正态总体的均值和方差同时在简单半序约束下的极大似然估计的求解问题，给出了计算极大估计的迭代算法，且证明该算法收敛。     

求解图着色问题的量子蚁群算法

针对经典的图着色问题,在蚁群算法的基础上结合量子计算提出一种求解图着色问题的量子蚁群算法. 将量子比特和量子逻辑门引入到蚁群算法中,较好地避免了蚁群算法搜索易陷入局部极小的缺陷,并显著加快了算法的运算速度. 通过图着色实例的大量仿真实验,表明算法对图着色问题的求解是可行的、有效的,且具有通用性.     

Max—min神经网络的一种有效学习算法

本文在Ａ．Ｂｌａｎｃｏ等人的算法的基础上，提出了ｍａｘ－ｍｉｎ神经网络的一种改进了的反馈学习算法，严格证明了该算法的迭代收敛性，理论分析及实例计算结果均表明，本文算法具有算法简单，收敛速度快，输出误差小等显著特点。     

正态总体均值与标准差比在简单半序约束下的最大似然估计

本文考虑两个正态总体均值和方差是未知参数,均值与标准差的比在简单半序约束下,且样本个数不同时,计算均值和标准差的最大似然估计的问题.给出了计算均值和标准差的最大似然估计的方法.同时还给出了三个总体均值与标准差的比在简单半序约束下求均值和标准差的最大似然估计的计算方法,并给出了迭代算法的模拟结果.     

分位点随机配序抽样

该文针对统计计算中的某些随机模拟问题提出了分位点随机配序抽样法.该方法是由抽样分布的分位点和伪随机序复合构成的,适用于固定区域上多重积分的计算及随机变量的抽样.该文通过几个典型实例说明该方法在具体问题中的应用,并验证了该方法的计算精度.     

求解大规模Hamilton矩阵特征问题的辛Lanczos算法的误差分析

对求解大规模稀疏Hamilton矩阵特征问题的辛Lanczos算法给出了舍入误差分析.分析表明辛Lanczos算法在无中断时,保Hamilton结构的限制没有破坏非对称Lanczos算法的本质特性.本文还讨论了辛Lanczos算法计算出的辛Lanczos向量的J一正交性的损失与Ritz值收敛的关系.结论正如所料,当某些Ritz值开始收敛时.计算出的辛Lanczos向量的J-正交性损失是必然的.以上结果对辛Lanczos算法的改进具有理论指导意义.     

负权最短路问题的新算法

Bellman-Ford算法自1958年以来一直是负权最短路问题的公认的最好算法之一．1970年,Yen对其进行了改进,理论上可以节省一半的计算量．本文得到了一种比Bellman-Ford算法更加优越的算法．尽管在理论上新算法无法保证完全超越于Yen的改进算法,但在许多情况下需要更少的计算量．     

稀疏数据非线性降维的CN-Isomap算法

针对经典的流形学习算法Isomap在非线性数据稀疏时降维效果下降甚至失效的问题,提出改进的切近邻等距特征映射算法(Cut-Neighbors Isometric feature mapping,CN-Isomap).该算法在数据稀疏的情况下首先通过有效识别样本点的"流形邻居"来剔除近邻图上的"短路"边,然后再通过最短路径算法拟合测地线距离,使得拟合的测地线距离不会偏离流形区域,从而低维嵌入映射能够正确地反映高维输入空间样本点间的内在拓扑特征,很好地发现蕴含在高维空间里的低维流形,有效地对非线性稀疏数据进行降维.通过对Benchmark数据集的实验表明了算法的有效性.CN-Isomap算法是Isomap算法的推广,不仅能有效地对非线性稀疏数据进行降维,同样也适用于数据非稀疏的情况.     

A perfect matching algorithm for sparse bipartite graphs

This paper considers an algorithm for finding a perfect matching, if there is one, in a bipartite graph G. It is shown that the search for a perfect matching in G may be carried on separately in the strongly connected components of appropriate directed graphs. The algorithm may be particularly useful for block triangularization of very large, sparse, nonsingular matrices.     

Reformulations and solution algorithms for the maximum leaf spanning tree problem

Given a graph G = (V, E), the maximum leaf spanning tree problem (MLSTP) is to find a spanning tree of G with as many leaves as possible. The problem is easy to solve when G is complete. However, for the general case, when the graph is sparse, it is proven to be NP-hard. In this paper, two reformulations are proposed for the problem. The first one is a reinforced directed graph version of a formulation found in the literature. The second recasts the problem as a Steiner arborescence problem over an associated directed graph. Branch-and-Cut algorithms are implemented for these two reformulations. Additionally, we also implemented an improved version of a MLSTP Branch-and-Bound algorithm, suggested in the literature. All of these algorithms benefit from pre-processing tests and a heuristic suggested in this paper. Computational comparisons between the three algorithms indicate that the one associated with the first reformulation is the overall best. It was shown to be faster than the other two algorithms and is capable of solving much larger MLSTP instances than previously attempted in the literature.     

Discretization algorithm for fractional order integral by Haar wavelet approximation

A discretization algorithm is proposed by Haar wavelet approximation theory for the fractional order integral. In this paper, the integration time is divided into two parts, one presents the effect of the past sampled data, calculated by the iterative method, and the other presents the effect of the recent sampled data at a fixed time interval, calculated by the Haar wavelet. This method can reduce the amount of the stored data effectively and be applied to the design of discrete-time fractional order PID controllers. Finally, several numerical examples and simulation results are given to illustrate the validity of this discretization algorithm.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

A recognition algorithm for the intersection graphs of directed paths in directed trees

Consider a finite family of non-empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of directed paths in a directed tree is called a directed path graph. In this paper we present an efficient algorithm which constructs to a given graph a representation by a family of directed paths on a directed tree, if one exists. Also, we prove that a graph is a proper directed path graph if and only if it is a directed path graph.     

A multicast routing algorithm based on searching in directed graph

Aiming at constructing a delay and delay variation bounded Steiner tree in the real-time streaming media communication, in this paper, we discuss a multicast routing algorithm based on searching a directed graph (MRASDH). During the process of the construction of the multicast tree, some nodes and links in the network topology do not affect the outcome of the constructed tree. Therefore, based on the thought of shrinking the search space through deleting these non-relative nodes and edges to the utmost, the ant algorithm is utilized to generate a directed sub-graph of the network topology for each destination node, in which each node owns a bounded out-degree. And all these sub-graphs can be merged into a new directed graph that serves as the new search space. In the new space, the simulated annealing algorithm is applied to obtain a multicast tree that satisfies the condition for the optimization. The performance analysis and simulation results demonstrate that this algorithm can effectively construct a delay and delay variation bounded multicast tree. They also show that the algorithm have lower time complexity than the current ones, which means a much better result would be achieved when the system scale rises greatly.     

图的可达性矩阵的一种新求法

图的可达性矩阵在判断图的强连通性以及求强连通分图中具有重要作用.根据传统求解图的可达性矩阵的特点,在定义链长的基础上,寻求了一种新的计算方法,采用逐次求平方的方法进一步降低计算量.     

Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times

This paper presents a variant of the asymmetric traveling salesman problem (ATSP) in which the traveling time between each pair of cities is represented by an interval of values (wherein the actual travel time is expected to lie) instead of a fixed (deterministic) value as in the classical ATSP. Here the ATSP (with interval objective) is formulated using the usual interval arithmetic. To solve the interval ATSP (I-ATSP), a genetic algorithm with interval valued fitness function is proposed. For this purpose, the existing revised definition of order relations between interval numbers for the case of pessimistic decision making is used. The proposed algorithm is based on a previously published work and includes some new features of the basic genetic operators. To analyze the performance and effectiveness of the proposed algorithm and different genetic operators, computational studies of the proposed algorithm on some randomly generated test problems are reported.