数据传输选择问题:算法设计和复杂性分析

数据和信息传输业务对网络的要求越来越高，在满足实时性、可靠性的同时，还要求充分利用网络资源，降低传输成本．文章首先建立了数据传输网络选择的最小成本模型，给出了有效支撑树代表集的概念，并给出了一个时间复杂性为O(mlogn)的算法产生代表集，其中m，n分别代表网络的边数和顶点数．然后对静态数据传输支撑树问题和动态数据传输支撑树问题，分别给出了一个时间复杂性为O(mlog n)和O(m^2 mlogn)的多项式时间的好算法．     

信息系统的属性约简

粗糙集理论是一种新的处理模糊和不确定知识的数学工具 .属性约简是粗糙集理论研究中的重要内容之一 ,现已证明寻找信息系统的最小约简是 NP-hard问题 .本文提出一个基于信息量的属性约简的启发式算法 ,该算法的时间复杂性为 $O( | A|^3 | U| ^2 )$ .通过例子分析 ,表明该算法是有效的.     

带有折扣因子的树型约束排序问题的最优算法

讨论优先约束条件为树型,目标函数为带有折扣的加权完工时间的单机排序问题l|outtree|∑wj(1-e-rCj),并给出了求解该问题的一个算法复杂性为O(n2)的最优算法.     

On the Star Chromatic Number of Graph Products

1　 IntroductionThroughout this paper,we only consider simple graphs.Letkanddbe natural numberssuch thatk 2 d.A ( k,d) -coloring of a graph G=( V,E) is a map c:V|→ Zk,such thatforeach edge( u,v)∈ E,|c( u) -c( v) |k d,where|x|k=min{|x|,k-|x|},and Zk={0 ,1 ,2 ,… ,k-1 }.Itis obvious thata( k,1 ) -coloring ofa graph is justan ordinaryk-coloringof G.The star-chromatic numberχ* ( G) of a graph G is defined by:χ* ( G) =inf{k/ d∶ G has a ( k,d) -coloring}.　　It is proved in[1 ,2 ] that th…     

求解含调整时间并行机排序问题的遗传算法

车间作业排序问题是生产管理和组合优化领域研究的重要课题,由于其内在的复杂性(NP-Hard),很难用经典方法求出其最优解.本文针对含非常数调整时间的并行机的作业排序问题(n|m|P,Sij|C max),设计了一种遗传算法的实现形式.算例计算分析表明,该算法具有良好的收敛特性和运算效率.     

VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS

H. Wang considered the minimum degrees condition that G has large vertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjoint cycles in bipartite graphs in this paper. We prove the following result: Let m > 3, n > 2 and k >1 be three integers. Let G = (V1,V2;E) be a bipartite graph with | V1| = | V2| =n > 2k 1. If the minimum degreefor any cycle C of G with length 2m, then G contains k vertex-disjoint cycles of length 4. Moreover, the degrees condition is sharp.     

完全赋权树的第n优场址问题

在实际中,有序地求出完全赋权图的第一优,第二优,第n优场址有时是非常必要的。本文对完全赋权树给出了这样的方法,称为n优场址法。并证明了第k优场址必与第一优,第二优,…,第(k-1)优场址相邻。     

加拿大旅行者问题

针对加拿大旅行者问题 ,分析其主要变形——确定型可恢复的加拿大旅行者问题。考虑堵塞边动态产生 ,一个遇到且堵塞边在时间 l( x,x)后可以自动恢复情况下的道路选择。通常对于在线算法可以从两个方面进行评价 :最坏情形分析和竞争比分析。本文先设计了求解最坏情形下旅行时间最短的标号算法并分析了其计算复杂性。而后在竞争比分析中 ,设计了基于贪婪原则的选路策略 ,并对其进行了竞争比分析 ,证明了该贪婪策略对于确定型可恢复加拿大旅行者问题的竞争比为 ( k+ 2 ) /2     

Equivalency and unbiasedness of grey prediction models

In order to deeply research the structure discrepancy and modeling mechanism among different grey prediction models, the equivalence and unbiasedness of grey prediction models are analyzed and verified. The results show that all the grey prediction models that are strictly derived from x(0)(k) +az(1)(k) = b have the identical model structure and simulation precision. Moreover, the unbiased simulation for the homogeneous exponential sequence can be accomplished. However, the models derived from dx(1)/dt + ax(1)= b are only close to those derived from x(0)(k) + az(1)(k) = b provided that |a| has to satisfy|a| < 0.1; neither could the unbiased simulation for the homogeneous exponential sequence be achieved. The above conclusions are proved and verified through some theorems and examples.     

CORRELATION PROPERTIES OF DE BRUIJN SEQUENCES

Several new bounds for the correlation functions of de Bruijn sequences are derived.It is shown that the set of all primitive de Bruijn sequences have the following two properties:1)for each sequence a in the set with large span n,the magnitude of its auto-correlation funct-ion|r_a(k)|is relatively small compared with the peak 2~n for all k≠0 mod 2~n;2)for each pair of sequences a,b in the set with large span n,the magnitude of their cross-correlation function |r_(ab)(k)| is relatively small compared with the peak 2~n for all k.Some generalizations of the result are also presented.     

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=be a network with the vertex set V,the edge set E and the length vector L, andlet T~* be a prior determined spanning tree of G. The inverse minimum spanning tree problem withminimum number of perturbed edges is to perturb the length vector L to L+δ, such that T~* is one ofminimum spanning trees under the length vector L+δ and the number of perturbed edges is minimum.This paper establishes a mathematical model for this problem and transforms it into a minimumvertex covering problem in a bipartite graph G_0, a path-graph. Thus a strongly polynomial algorithmwith time complexity O(mn~2) can be designed by using Hungarian method.     

赋权有向图最小生成树的表上作业法

每一赋权有向图可用一个赋权表来表示。本文在借助于赋权表而不是赋权有向图本身讨论圈和生成树的基础上,给出了一种求解赋权有向图最小生成树的新方法——表上作业法,证明了方法的最优性。该方法简单易行,借助于计算机Ｓｐｒｅａｄｓｈｅｅｔ软件,如ＭｉｃｒｏｓｏｆｔＥｘｃｅｌ,可很方便地进行大规模复杂问题的求解。     

网络中的最优控制树问题

众所周知,从通讯网络建设中提出著名的最优支撑树问题,即在一个赋权连通图中求一个包含所有顶点而权(费用)最小的连通子图(支撑树).进而,在交通、通讯、供销系统的干线设计中,考虑的连线(干线)不一定连接网络的所有顶点,但被连接的顶点必须构成一个控制集,即其余任一顶点都有一条边直接与此主干部分相连.这就提出了最优控制树问题.似乎此问题与最优支撑树问题十分类似,但我们将证明它是NP-困难的,并给出一个分枝定界算法及相关性质.     

小型无人机协同覆盖侦察路径规划

针对多架小型无人机对含有障碍的区域覆盖侦察最佳路径规划问题,首先用方形单元格将待侦察区域离散化,利用基于初始位置的划分方法划分出与无人机对应的子区域,把问题转化为单无人机优化问题以降低计算复杂度;然后在最小生成树的基础上提出节点交换法,对各子区域的形状和最小生成树进行调整优化;最后依据优化后的最小生成树为每个子区域构建侦察路径。仿真验证了该方法产生的规划路径能够完全覆盖指定区域且无重叠,路径长度和转弯数最小。     

无人飞行器Ad hoc网络中基于容错的中继节点配置

针对无人飞行器Ad hoc网络的容错设计需求,采用增加中继节点的方法实现。在二维平面同构网络中,将容错问题转化为边长受限条件下最少数量Steiner点的Steiner树问题。提出了两种基于最小成本子图的中继节点配置算法,以求解最少数量的中继节点及其位置,使改变后的网络拓扑图为顶点2-连通,实现容错。第一种为多项式时间的8-近似算法;第二种为随机近似算法,采用文化基因算法,搜索需要新增加的最小成本强化边组合。仿真结果表明了所提算法的有效性,当网络规模较小和中等时,随机近似算法得到的中继节点数量较少,平均情况下性能较优。     

Investigating the Disparities of China's Insurance Market Based on Minimum Spanning Tree from the Viewpoint of Geography and Enterprise

In this paper, we investigate the disparities of China's insurance market from the viewpoint of geography and enterprise by using the monthly data from January 2006 to December 2015. We divide the whole insurance market into two parts, namely property insurance and personal insurance.By constructing and analyzing minimum spanning trees of insurance market, we obtain the results as follows:(i) The connections between provinces are much closer than those of firms, and there are regional links between neighboring provinces in the minimum spanning tree(MST); and(ii) the domestic funded firms and foreign funded firms form two explicit clusters in the MSTs of property and personal insurance market.     

广义最小生成树的遗传算法求解及应用

介绍了最小生成树的概念,分析了最小生成树在实际应用中的局限性。引入了节点的度的定义,据此提出了广义最小生成树的概念。采用遗传算法来求解最小生成树,并针对普通遗传算法求解该问题的不足,提出了自调整的变异算子和限制父代个体数目的混合选择策略。通过一个有线电视网络的建模与仿真,表明了广义最小生成树模型的适用性。分别采用普通遗传算法和改进后的遗传算法进行求解,并将结果进行比较,证明了改进后的遗传算法的有效性。     

度限制最小树的蚂蚁算法①

针对度限制最小树问题,给出了一种基于蚂蚁系统思想的求解方法,经大量数据测试和验证,并与其它算法相比较,得到了较好的结果以及一系列有意义的结论.     

度限制最小树的蚂蚁算法

针对度限制最小树问题,给出了一种基于蚂蚁系统思想的求解方法,经大量数据测试和验证,并与其它算法相比较,得到了较好的结果以及一系列意义的结论。