一个求无向图所有极大独立集的算法

图的极大独立集在计算机视觉、计算机网络、编码理论和资源配置等领域有着广泛的应用.本文利用图的分解方法给出了一个求简单无向图所有极大独立集的递归公式.定义了图的邻接矩阵的两个变换和点集合的一些运算.在此基础上,利用二分树给出了一个求无向图的所有极大独立集的有效算法.算法的时间复杂度是O(mn),其中m,n分别是图的所有极大独立集数和顶点个数.算法只需对网络的邻接矩阵进行处理,在计算机上实现起来非常方便.最后,通过实例验证了算法的有效性.     

基于蚁群算法的多邮车调度问题研究

采用动态规划决策思想,针对邮政运输网络,通过将邮车调度问题转化为在赋权连通图求最小权值回路的问题,构建了一个基于蚁群算法的邮路决策模型,并建立相应的算法体系。最后对该模型的理论性和有效性做出了证明。     

分子算法在公交网络问题中的应用

分子生物计算是一门很有潜力的发展中学科。首次尝试将其用于解决公交网络问题。通过对公交网络问题的分析,巧妙地将该出行优化问题转化成一个赋权图问题,综合考虑道路长度、拥堵系数、换乘等因素,并结合自组装的思想对其进行建模。在此基础之上,以西安市局部公共交通网络图为例,给出了该分子计算模型的详细生化操作步骤,显示了分子生物计算的可行性及巨大的优越性。该算法大大降低了公交网络计算的复杂性,同时扩展了分子生物计算的研究领域。     

传输子网选择:度数有界最大支撑子图逼近

研究了源于无线网状网络的度数有界最大支撑子图问题:给定连通图G=(V,E)和正整数d≥2,求G的一个最大支撑子图H,满足对V中每个顶点v,v在H中的度数dH(v)不超过d。这里,支撑子图指图G的一个连通而且包括G中所有顶点的子图。就输入图的边是否带权,分别设计了多项式时间近似算法。当输入图为无权图时,证明了近似算法的近似比为2;当输入图为赋权图时,证明了算法输出一个最大度数不超过d+1、权重不低于最优解权重1/(d+2)的支撑子图。算法输出的度数有界支撑子图可以用作无线网状网络的传输子网。     

不确定图上的kNN查询处理

在现实中的许多领域产生大量不确定的图结构的数据,例如分子化合物、蛋白质交互网络等.同时现实中有很多应用例如推荐系统中的推荐过滤、欺诈检测和社会网络的链接预测等,需要查询给定节点的k个最相似节点,针对这一问题,提出了用基于SimRank度量的方法来求解.由于图的动态演变和不确定性导致用现有的SimRank计算方法求k个最近邻的代价昂贵,因此提出一个有效算法,在保证一定准确性的前提下,通过引入路径阈值,算法只需考虑查询点的邻居区域无需考虑整个图从而达到明显的剪枝效果,该方法在确定图和不确定图上都可以适用.在此基础上为了进一步提高效率,算法在不确定图上引入采样技术.最后从理论、实验说明验证了算法的高效性和有效性.     

基于图的语义网络构造算法研究

在自然语言处理的基础上,将中医领域本体与图的基本性质相结合,提出了构造中医诊疗知识语义网络算法。给出了图的基本性质、语义网络的图定义,并为知识的网络表示建立了相应的数据结构。将算法用于中医领域语义网络和语义场构建。试验结果表明,该算法具有较好的实用性。提出的基于图的语义网络构造算法,对于文本挖掘、知识获取技术研究有重要意义,也是中医专家知识获取的有效方法。     

如何计算网络中两点间的最大流量

问题 给定一个网络任意一条边可通过的最大流量,请编一程序求出该网络中任意指定的两点间的最大流量。例如,对如图1所给出的网络,求出其中v_0点至v_5点的最大流量。 问题的应用背景 这是一个很有实际意义的问题,例如在计算机网络中求两节点间的最大流量,在城市公路网中求两地点间的最大运输能力,供水系     

无线传感网络覆盖中概率Voronoi模型及算法研究

覆盖是无线传感网络中最重要的问题之一,随机覆盖是目前研究的主流。基于Voronoi图的随机覆盖算法是无线传感网络领域的研究热点。目前研究中采用的Voronoi图,主要采用基于距离的Voronoi边赋权值模型,存在两个主要问题,即模型粗糙和监测节点不全。以实测的分段概率传感模型为基础,从多传感协同监测的角度构造一种概率Voronoi模型,试图解决以上问题。并且用基于概率Voronoi模型的最大突破路径算法验证了模型有效性。就掌握的文献来看,该模型是首次提出,具有较好的实用推广价值。     

基于完全子图的社区发现算法

根据复杂网络中同一社区内节点连接比较紧密,社区之间节点连接比较稀疏的特点,提出一种基于完全子图的社区发现算法,通过判别2个节点是否能在网络中与任意一个节点构成3个节点的完全子图来确认该2点是否属于同一社区。对于有些节点并不满足完全子图,或在不同社区同时满足完全子图的情况,采用节点社区归属度解决该节点的归属问题。该算法不需要任何参数设置,在计算机生成网络和真实网络上进行测试,结果验证了该算法的可行性和准确性。     

基于图的语义网络构造算法研究

在自然语言处理的基础上,将中医领域本体与图的基本性质相结合,提出了构造中医诊疗知识语义网络算法.给出了图的基本性质、语义网络的图定义,并为知识的网络表示建立了相应的数据结构.将算法用于中医领域语义网络和语义场构建.试验结果表明,该算法具有较好的实用性.提出的基于图的语义网络构造算法,对于文本挖掘、知识获取技术研究有重要意义,也是中医专家知识获取的有效方法.     

全景视频双环带映射算法

针对全景视频映射过程中局部区域变形过大、冗余数据量极高的问题,提出了一种双环带映射算法（DRP）。首先,根据球面视频的几何特点,结合人眼视度（HVS）这一视觉特性,用两个相互正交的环形区域,将球面视频分割成14个大小相近的区域;然后根据空域采样定理,采用兰索斯插值法,将这14个区域对应的球面视频内容映射为14个大小相等的矩形视频;最后,根据最新视频编码标准的特点,重新排列这14个矩形视频,得到符合编码器标准的紧凑的全景视频。实验结果表明,与经纬图映射算法（ERP）、八面体映射算法（OHP）、二十面体映射算法（ISP）相比,DRP算法在视频压缩性能方面有良好的表现;其中同最流行的ERP算法相比,码率平均降低8.61%,明显提升了视频编码效率。     

混合关系中的函数依赖及其相关规则

在实际应用中有这样一类关系数据库,其中数据项在某个属性上的取值本身又是一个关系。讨论这种混合关系中的函数依赖及其相应的相关规则具有一定的理论意义和实际应用价值。给出这种混合关系的形式定义、混合关系中4种类型的函数依赖关系以及相应的4种类型的相关规则;并给出混合关系到一般关系的转换,通过这个转换说明了混合关系与普通关系的联系及其差别。给出一个实际应用中的例子,来说明混合关系中的函数依赖和相关规则的形式多样性。     

Monotonic and nonmonotonic gentzen deduction systems for L3-valued propositional logic

A sequent is a pair (Γ, Δ), which is true under an assignment if either some formula in Γ is false, or some formula in Δ is true. In L₃-valued propositional logic, a multisequent is a triple Δ|Θ|Γ, which is true under an assignment if either some formula in Δ has truth-value t, or some formula in Θ has truth-value m, or some formula in Γ has truth-value f. Correspondingly there is a sound and complete Gentzen deduction system G for multisequents which is monotonic. Dually, a comultisequent is a triple Δ : Θ : Γ, which is valid if there is an assignment v in which each formula in Δ has truth-value≠t, each formula in Θ has truth-value≠m, and each formula in Γ has truth-value≠f. Correspondingly there is a sound and complete Gentzen deduction system G⁻ for co-multisequents which is nonmonotonic.     

基于角色和范围的通用管理系统的设计与实现

用户管理系统是Web应用系统及大型软件系统的重要组成部分。在目前已有的用户管理系统中,角色只是权限的集合,不涉及管辖范围,是一个一维空间上的概念。该文提出一种二维角色的概念,是由权限和范围组成的二元对集合,是一个二维空间上的概念。构建一个基于二维角色的通用用户管理模型,设计一个通用用户管理系统,能满足现代Web应用系统和大型软件系统对用户授权的多层次和多空间的要求。     

K(Knowledge)-net: building up and its dynamics

The essence of intelligence is to use certain abilities to obtain knowledge, to use that knowledge, and to operate with that knowledge. New knowledge learned by a human is often related to old existing knowledge, and sometimes we could have more conceptual knowledge based on old knowledge. So, the knowledge in the brain exists in a related structural form, and this structure is dynamic, and therefore is evolvable. Based on the understanding of the real process of learning by a human being, we discuss how to make a model to describe the dynamic structure of knowledge. This model is also a principle of artificial brain design. Most of the knowledge a child learns is from natural language and perception information, and we define this as semantic knowledge. The model to describe the process and structure of knowledge growing in a network form is called a K-net. It is a dynamic network with two main dynamics: one is new knowledge added, and the other is aggregating knowledge existing in the network with some probability. Under these very natural conditions, we found that the network is originally a simple random net, and then some characteristics of a complex network gradually appear when more new knowledge is added and aggregated. A more interesting phenomenon is the appearance of a random hierarchical structure. Does this mean emergence?     

A distributed event-triggered dynamic average consensus scheme with a time-varying threshold and its application in DC microgrid

We propose a distributed event-triggered dynamic average consensus (DAC) scheme with a time-varying threshold for a multi-agent system (MAS) in a directed graph. In this scheme, each agent is not required to monitor its neighbors in real time, and a threshold is chosen related to consensus performance directly in an MAS, where the threshold is adjusted adaptively according to average consensus performance. Also, we introduce a bounded and monotonically increasing function in a time-varying threshold, and this function is for guaranteeing the value of a threshold to locate in an appropriate range. Stability analysis shows that the tracking error is eventually bounded and the MAS achieves DAC without Zeno behaviors. Furthermore, the proposed event-triggered DAC scheme is applied to voltage restoration and adjustable current sharing in DC microgrid. The effectiveness of the proposed scheme is verified by two examples.     

Attribute reduction based on evidence theory in incomplete decision systems

Attribute reduction is a basic issue in knowledge representation and data mining. This paper deals with attribute reduction in incomplete information systems and incomplete decision systems based on Dempster-Shafer theory of evidence. The concepts of plausibility reduct and belief reduct in incomplete information systems as well as relative plausibility reduct and relative belief reduct in incomplete decision systems are introduced. It is shown that in an incomplete information system an attribute set is a belief reduct if and only if it is a classical reduct and a plausibility consistent set must be a classical consistent set. In a consistent incomplete decision system, the concepts of relative reduct, relative plausibility reduct, and relative belief reduct are all equivalent. In an inconsistent incomplete decision system, an attribute set is a relative plausibility reduct if and only if it is a relative reduct, a plausibility consistent set must be a belief consistent set, and a belief consistent set is not a plausibility consistent set in general.     

Generalized theory of uncertainty (GTU)—principal concepts and ideas

Uncertainty is an attribute of information. The path-breaking work of Shannon has led to a universal acceptance of the thesis that information is statistical in nature. Concomitantly, existing theories of uncertainty are based on probability theory. The generalized theory of uncertainty (GTU) departs from existing theories in essential ways. First, the thesis that information is statistical in nature is replaced by a much more general thesis that information is a generalized constraint, with statistical uncertainty being a special, albeit important case. Equating information to a generalized constraint is the fundamental thesis of GTU. Second, bivalence is abandoned throughout GTU, and the foundation of GTU is shifted from bivalent logic to fuzzy logic. As a consequence, in GTU everything is or is allowed to be a matter of degree or, equivalently, fuzzy. Concomitantly, all variables are, or are allowed to be granular, with a granule being a clump of values drawn together by a generalized constraint. And third, one of the principal objectives of GTU is achievement of NL-capability, that is, the capability to operate on information described in natural language. NL-capability has high importance because much of human knowledge, including knowledge about probabilities, is described in natural language. NL-capability is the focus of attention in the present paper. The centerpiece of GTU is the concept of a generalized constraint. The concept of a generalized constraint is motivated by the fact that most real-world constraints are elastic rather than rigid, and have a complex structure even when simple in appearance. The paper concludes with examples of computation with uncertain information described in natural language.     

Optimal number of minimal repairs with cumulative repair cost limit for a two-unit system with failure rate interactions

A discrete replacement model is presented that includes a cumulative repair cost limit for a two-unit system with failure rate interactions between the units. We assume a failure in unit 1 causes the failure rate in unit 2 to increase, whereas a failure in unit 2 causes a failure in unit 1, resulting in a total system failure. If unit 1 fails and the cumulative repair cost till to this failure is less than a limit L, then unit 1 is repaired. If there is a failure in unit 1 and the cumulative repair cost exceeds L or the number of failures equals n, the entire system is preventively replaced. The system is also replaced at a total failure, and such replacement cost is higher than the preventive replacement cost. The long-term expected cost per unit time is derived using the expected costs as the optimality criterion. The minimum-cost policy is derived, and existence and uniqueness are proved.     

Distributed multi-join query processing in data grids

Query processing in data grids is a difficult issue due to the heterogeneous, unpredictable and volatile behaviors of the grid resources. Applying join operations on remote relations in data grids is a unique and interesting problem. However, to the best of our knowledge, little is done to date on multi-join query processing in data grids. An approach for processing multi-join queries is proposed in this paper. Firstly, a relation-reduction algorithm for reducing the sizes of operand relations is presented in order to minimize data transmission cost among grid nodes. Then, a method for scheduling computer nodes in data grids is devised to parallel process multi-join queries. Thirdly, an innovative method is developed to efficiently execute join operations in a pipeline fashion. Finally, a complete algorithm for processing multi-join queries is given. Analytical and experimental results show the effectiveness and efficiency of the proposed approach.