Comparison among Classical,Probabilistic and Quantum Algorithms for Hamiltonian Cycle Problem

The Hamiltonian cycle problem(HCP),which is an NP-complete problem,consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.In this paper we compare some algorithms to solve a Hamiltonian cycle problem,using different models of computations and especially the probabilistic and quantum ones.Starting from the classical probabilistic approach of random walks,we take a step to the quantum direction by involving an ad hoc designed Quantum Turing Machine(QTM),which can be a useful conceptual project tool for quantum algorithms.Introducing several constraints to the graphs,our analysis leads to not-exponential speedup improvements to the best-known algorithms.In particular,the results are based on bounded degree graphs(graphs with nodes having a maximum number of edges)and graphs with the right limited number of nodes and edges to allow them to outperform the other algorithms.

Test sequencing problem arising at the design stage for reducing life cycle cost

Previous test sequencing algorithms only consider the execution cost of a test at the application stage. Due to the fact that the placement cost of some tests at the design stage is considerably high compared with the execution cost, the sequential diagnosis strategy obtained by previous methods is actually not optimal from the view of life cycle. In this paper, the test sequencing problem based on life cycle cost is presented. It is formulated as an optimization problem, which is non-deterministic polynomial-time hard （NP-hard）. An algorithm and a strategy to improve its computational efficiency are proposed. The formulation and algorithms are tested on various simulated systems and comparisons are made with the extant test sequencing methods. Application on a pump rotational speed control （PRSC） system of a spacecraft is studied in detail. Both the simulation results and the real-world case application results suggest that the solution proposed in this paper can significantly reduce the life cycle cost of a sequential fault diagnosis strategy.

Geometry-preserving full-waveform tomography and its application in the Longmen Shan area

Classic L2-norm-based waveform tomography is often plagued by insurmountable cycle skipping problems;as a result,the iterative inversion falls into local minima,yielding erroneous images.According to the optimal transportation theory,we adopt a novel geometry-preserving misfit function based on the quadratic Wasserstein metric(W2-norm),which improves the stability and convexity of the inverse problem.Numerical experiments illustrate that W2-norm-based full-waveform tomography has a larger convergence radius and a faster convergence rate than the L2-norm and can effectively mitigate cycle skipping issues.We apply this method to the Longmen Shan area and obtain a reliable lithospheric velocity model.Our tomographic results indicate that the crystalline crust underlying the Sichuan Basin wedges into the crustal interior of the Tibetan Plateau,and the mid-lower crust of the eastern Tibetan Plateau is characterized by low shear-wave velocities,indicating that ductile crustal flow and strong interactions between terranes jointly dominate the uplift behavior of the Longmen Shan.Furthermore,we find that large earthquakes(e.g.,the Wenchuan and Lushan events)occur not only at the junction between high-and low-velocity regions but also in the transition zone from positive to negative radial anisotropy.These findings improve our understanding of the mechanism responsible for large earthquakes in this region.