网络最小生成树更新策略

求解最小生成树问题被广泛应用于求解现实中的搜索相关问题。然而现实瞬息万变,一个连通网络的节点常常发生变动。而一旦发生改变,传统算法必须要再次计算最小生成树。但是虽然节点发生了变动,最小生成树未必全部发生改变,这就造成了不必要的浪费。鉴于此提出一种基于Kruskal算法和Prim算法的最小树更新策略,对Kruskal算法和Prim算法做了改进,使其不必重新计算也能在连通图发生改变时更新最小生成树。     

基于Sollin算法的最小生成树求解

Prim算法、Kruskal算法和Sollin算法是最小生成树的典型构造算法。这三个算法均基于贪婪策略。Prim和Kruskal算法在本专科数据结构课程中有详细的介绍,而Sollin算法涉及较少。本文基于边集数组这一存储结构,详细说明了Sollin算法的步骤与实现。     

基于Prim算法的最小生成树优化研究

在图的最小生成树算法中,Prim和Kruskal算法分别适用于稠密图和稀疏图,但两种算法都不能根据图的顶点数、顶点的度数以及边的分布情况自适应地改变自身.由此,对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图,经实例验证,利用改进的Prim最小生成树算法,根据无向图的顶点数和顶点的度数动态确定求解最小生成树的时间,并将求解的时间复杂度最小化.     

基于Prim算法和Kruskal算法的最小生成树优化研究

文章从目前最常见的两种在图最小生成树算法,即Prim和Kruskal算法,展开了阐述和分析,运用了大量的数据和实例对这两种计算方法进行了分析和研究。通过试验并对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图。     

最小生成树的算法——减枝算法

最小生成树是数据结构中图的一种重要应用,对于具有n个顶点的带权连通图可以建立许多不同的生成树.Kruskal算法和Prim算法是求最小生成树的常用算法.本文讨论了一种新的算法.     

基于精英的量子粒子群优化的Ad hoc能耗研究

在Ad hoc网络中,随着多播应用领域的日益扩大,如何构造最小能耗多播树是一个重要问题。针对选择不同的中继节点对构造最小能耗多播树产生的影响,提出了一种优化最小能耗多播树构造的基于精英学习的量子粒子群算法(QPELSO)。为了避免粒子群算法早熟收敛,采用动态逼近学习策略对精英个体进行局部更新,使其跳出局部极值点,引导种群进行有效搜索;借鉴群体早熟判断机制对停滞状态下的精英个体空间进行变尺度混沌扰动,增大种群全局搜索空间,有效平衡了算法的局部和全局搜索能力。模拟实验结果表明,改进后的粒子群算法具有较强的优化能力,并且有效地优化了最小能耗多播树的构造。     

赋权有向图的最小生成树算法

针对赋权有向图最小生成树问题存在可行解的情况,根据树节点入度最大值为1的性质,提出赋权有向图最小生成树性质。采用反证法,调整生成树根节点到弧头的路径来证明赋权有向图MST性质的正确性。基于赋权有向图MST性质,给出改进的Prim和Kruskal算法及其时间复杂度分析。实验给出构造某赋权有向图实例最小生成树的具体步骤,表明这2种算法能正确有效地构造赋权有向图最小生成树。     

求解度约束最小生成树的新的快速算法

针对度约束最小生成树问题,提出了一种新的快速算法。新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树。第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顶点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中。通过大量的数值实验表明新的快速算法性能良好。     

利用立方图的线图构造量子纠错码

量子纠错码在量子通信和量子计算中起着非常重要的作用,之前的量子纠错码的构造大部分都是利用经典的纠错码来构造得到,如Hamming码,BCH码,RS码,Reed-Muller码等各种经典纠错码。目前,很少有人利用图生成的线性码方法来构造量子纠错码,提出了一个新的构造量子纠错码和非对称量子纠错码的方法,即利用[n]立方图的线图生成的二元线性码来构造量子纠错码和非对称量子纠错码,得到了一类新的量子纠错码和非对称量子纠错码,并且,当码字的长度较大时,对所构造的非对称量子纠错码,在非对称信道上有更大的纠错能力。     

基于Hash表的量子可逆逻辑电路综合的快速算法

量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路.而且运行速度远远超过其他算法·实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的49.15倍、365.13倍.     

Nearly Linear Time Minimum Spanning Tree Maintenance for Transient Node Failures

Given a 2-node connected, real weighted, and undirected graph $G=(V,E)$, with $n$ nodes and $m$ edges, and given a minimum spanning tree (MST) $T=(V,E_T)$ of $G$, we study the problem of finding, for every node $v \in V$, a set of replacement edges which can be used for constructing an MST of $G-v$ (i.e., the graph $G$ deprived of $v$ and all its incident edges). We show that this problem can be solved on a pointer machine in ${\cal O}(m \cdot \alpha(m,n))$ time and ${\cal O}(m)$ space, where $\alpha$ is the functional inverse of Ackermanns function. Our solution improves over the previously best known ${\cal O}(\min\{m \cdot \alpha(n,n), m + n \log n\})$ time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge $e \in E_T$, a replacement edge which can be used for constructing an MST of $G-e=(V,E \backslash \{e\})$). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST.     

Minimum-weight spanning tree algorithms A survey and empirical study

The minimum-weight spanning tree problem is one of the most typical and well-known problems of combinatorial optimisation. Efficient solution techniques had been known for many years. However, in the last two decades asymptotically faster algorithms have been invented. Each new algorithm brought the time bound one step closer to linearity and finally Karger, Klein and Tarjan proposed the only known expected linear-time method. Modern algorithms make use of more advanced data structures and appear to be more complicated to implement. Most authors and practitioners refer to these but still use the classical ones, which are considerably simpler but asymptotically slower. The paper first presents a survey of the classical methods and the more recent algorithmic developments. Modern algorithms are then compared with the classical ones and their relative performance is evaluated through extensive empirical tests, using reasonably large-size problem instances. Randomly generated problem instances used in the tests range from small networks having 512 nodes and 1024 edges to quite large ones with 16 384 nodes and 524 288 edges. The purpose of the comparative study is to investigate the conjecture that modern algorithms are also easy to apply and have constants of proportionality small enough to make them competitive in practice with the older ones.Scope and purposeThe minimum-weight spanning tree (MST) problem is a well-known combinatorial optimisation problem concerned with finding a spanning tree of an undirected, connected graph, such that the sum of the weights of the selected edges is minimum. The importance of this problem derives from its direct applications in the design of computer, communication, transportation, power and piping networks; from its appearance as part of solution methods to other problems to which it applies less directly such as network reliability, clustering and classification problems and from its occurrence as a subproblem in the solution of other problems like the travelling salesman problem, the multi-terminal flow problem, the matching problem and the capacitated MST problem. Although efficient solution techniques capable of solving large instances had existed, there has been sustained effort over the last two decades to invent asymptotically faster algorithms. With each new algorithm found the time bound approached linearity. Finally, an expected linear-time method has been proposed. The purpose of this work is to survey the classical and modern solution techniques and empirically compare the performance of the existing methods.     

Coherent quantum LQG control

Based on a recently developed notion of physical realizability for quantum linear stochastic systems, we formulate a quantum LQG optimal control problem for quantum linear stochastic systems where the controller itself may also be a quantum system and the plant output signal can be fully quantum. Such a control scheme is often referred to in the quantum control literature as “coherent feedback control”. It distinguishes the present work from previous works on the quantum LQG problem where measurement is performed on the plant and the measurement signals are used as the input to a fully classical controller with no quantum degrees of freedom. The difference in our formulation is the presence of additional non-linear and linear constraints on the coefficients of the sought after controller, rendering the problem as a type of constrained controller design problem. Due to the presence of these constraints, our problem is inherently computationally hard and this also distinguishes it in an important way from the standard LQG problem. We propose a numerical procedure for solving this problem based on an alternating projections algorithm and, as an initial demonstration of the feasibility of this approach, we provide fully quantum controller design examples in which numerical solutions to the problem were successfully obtained. For comparison, we also consider the case of classical linear controllers that use direct or indirect measurements, and show that there exists a fully quantum linear controller which offers an improvement in performance over the classical ones.     

Quantum Pattern Recognition

I review and expand the model of quantum associative memory that I have recently proposed. In this model binary patterns of n bits are stored in the quantum superposition of the appropriate subset of the computational basis of n qbits. Information can be retrieved by performing an input-dependent rotation of the memory quantum state within this subset and measuring the resulting state. The amplitudes of this rotated memory state are peaked on those stored patterns which are closest in Hamming distance to the input, resulting in a high probability of measuring a memory pattern very similar to it. The accuracy of pattern recall can be tuned by adjusting a parameter playing the role of an effective temperature. This model solves the well-known capacity shortage problem of classical associative memories, providing a large improvement in capacity. PACS: 03.67.-a     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Self-protected quantum algorithms based on quantum state tomography

Only a few classes of quantum algorithms are known which provide a speed-up over classical algorithms. However, these and any new quantum algorithms provide important motivation for the development of quantum computers. In this article new quantum algorithms are given which are based on quantum state tomography. These include an algorithm for the calculation of several quantum mechanical expectation values and an algorithm for the determination of polynomial factors. These quantum algorithms are important in their own right. However, it is remarkable that these quantum algorithms are immune to a large class of errors. We describe these algorithms and provide conditions for immunity.      

Sharp Quantum versus Classical Query Complexity Separations

Abstract. We obtain the strongest separation between quantum and classical query complexity known to date—specifically, we define a black-box problem that requires exponentially many queries in the classical bounded-error case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.     

The Quantum Setting with Randomized Queries for Continuous Problems

The standard setting of quantum computation for continuous problems uses deterministic queries and the only source of randomness for quantum algorithms is through measurement. Without loss of generality we may consider quantum algorithms which use only one measurement. This setting is related to the worst case setting on a classical computer in the sense that the number of qubits needed to solve a continuous problem must be at least equal to the logarithm of the worst case information complexity of this problem. Since the number of qubits must be finite, we cannot solve continuous problems on a quantum computer with infinite worst case information complexity. This can even happen for continuous problems with small randomized complexity on a classical computer. A simple example is integration of bounded continuous functions. To overcome this bad property that limits the power of quantum computation for continuous problems, we study the quantum setting in which randomized queries are allowed. This type of query is used in Shor’s algorithm. The quantum setting with randomized queries is related to the randomized classical setting in the sense that the number of qubits needed to solve a continuous problem must be at least equal to the logarithm of the randomized information complexity of this problem. Hence, there is also a limit to the power of the quantum setting with randomized queries since we cannot solve continuous problems with infinite randomized information complexity. An example is approximation of bounded continuous functions. We study the quantum setting with randomized queries for a number of problems in terms of the query and qubit complexities defined as the minimal number of queries/qubits needed to solve the problem to within ɛ by a quantum algorithm. We prove that for path integration we have an exponential improvement for the qubit complexity over the quantum setting with deterministic queries.     

Exponential Separation of Quantum and Classical Online Space Complexity

Although quantum algorithms realizing an exponential time speed-up over the best known classical algorithms exist, no quantum algorithm is known performing computation using less space resources than classical algorithms. In this paper, we study, for the first time explicitly, space-bounded quantum algorithms for computational problems where the input is given not as a whole, but bit by bit. We show that there exist such problems that a quantum computer can solve using exponentially less work space than a classical computer. More precisely, we introduce a very natural and simple model of a space-bounded quantum online machine and prove an exponential separation of classical and quantum online space complexity, in the bounded-error setting and for a total language. The language we consider is inspired by a communication problem (the disjointness function) that Buhrman, Cleve and Wigderson used to show an almost quadratic separation of quantum and classical bounded-error communication complexity. We prove that, in the framework of online space complexity, the separation becomes exponential.