Saving Space by Fully Exploiting Invisible Transitions

Checking that a given finite state program satisfies a linear temporal logic property suffers from the state explosion problem. Often the resulting lack of available memory is more significant than any time limitations. One way to cope with this is to reduce the state graph used for model checking. We present an algorithm for constructing a state graph that is a projection of the program's state graph. The algorithm maintains the transitions and states that affect the truth of the property to be checked. Especially in conjunction with known partial order reduction algorithms, we show a substantial reduction in memory over using partial order methods alone, both in the precomputation stage, and in the result presented to a model checker. The price of the space reduction is a single additional traversal of the graph obtained with partial order reduction. As part of our space-saving methods, we present a new way to exploit Holzmann's Bit Hash Table, which assists us in solving the revisiting problem.     

A voronoi diagram‐visibility graph‐potential field compound algorithm for robot path planning

Numerous methods have been developed to solve the motion planning problem, among which the Voronoi diagram, visibility graph, and potential fields are well‐known techniques. In this paper, a new path planning algorithm is presented where these three methods are integrated for the first time in a single architecture. After constructing the generalized Voronoi diagram of C‐space, we introduce a novel procedure for its abstraction, producing a pruned generalized Voronoi diagram. A broad freeway net is then developed through a new α‐MID (maximal inscribed discs) concept. A potential function is assigned to the net to form an obstacle‐free network of valleys. Afterwards we take advantage of a bidirectional search, where the visibility graph and potential field modules execute alternately from both start and goal configurations. A steepest descent mildest ascent search technique is used for local planning and avoiding local minima. The algorithm provides a parametric tradeoff between safest and shortest paths and generally yields shorter paths than the Voronoi and potential field methods, and faster than the visibility graph. It also performs well in complicated environments. © 2004 Wiley Periodicals, Inc.     

A Markov Decision Problem Approach to Goal Attainment

A new Markov decision problem (MDP)-based method for managing goal attainment (GA), which is the process of planning and controlling actions that are related to the achievement of a set of defined goals in the presence of resource and time constraints, is proposed. Specifically, we address the problem as one of optimally selecting a sequence of actions to transform the system and/or its environment from an initial state to a desired state. We begin with a method of explicitly mapping an action-GA graph to an MDP graph and developing a dynamic programming (DP) recursion to solve the MDP problem. For larger problems having exponential complexity with respect to the number of goals, we propose guided search algorithms such as AO*, AO_epsiv*, and greedy search techniques, whose search power rests on the efficiency of their heuristic evaluation functions (HEFs). Our contribution in this part stems from the introduction of a new problem-specific HEF to aid the search process. We demonstrate reductions in the computational costs of the proposed techniques through performance comparison with standard DP techniques. We conclude this paper with a method to address situations in which alternative strategies (e.g., second best) are required. The new extended AO* algorithm identifies alternative control sequences for attaining the organizational goals.     

Quantum Mechanical Search and Harmonic Perturbation

Perturbation theory in quantum mechanics studies how quantum systems interact with their environmental perturbations. Harmonic perturbation is a rare special case of time-dependent perturbations in which exact analysis exists. Some important technology advances, such as masers, lasers, nuclear magnetic resonance, etc., originated from it. Here we add quantum computation to this list with a theoretical demonstration. Based on harmonic perturbation, a quantum mechanical algorithm is devised to search the ground state of a given Hamiltonian. The intrinsic complexity of the algorithm is continuous and parametric in both time T and energy E. More precisely, the probability of locating a search target of a Hamiltonian in N-dimensional vector space is shown to be 1/(1 + c N E⁻²T⁻²) for some constant c. This result is optimal. As harmonic perturbation provides a different computation mechanism, the algorithm may suggest new directions in realizing quantum computers.      

On the graph traversal and linear binary-chain programs

Grahne et al. have presented a graph algorithm for evaluating a subset of recursive queries. This method consists of two phases. In the first phase, the method transforms a linear binary-chain program into a set of equations over expressions containing predicate symbols. In the second phase, a graph is constructed from the equations and the answers are produced by traversing the relevant paths. In this paper, we describe a new algorithm which requires less time than Grahne's. The key idea of the improvement is to reduce the search space that will be traversed when a query is invoked. Furthermore, we speed up the evaluation of cyclic data by generating most answers directly in terms of the answers already found and the associated "path information" instead of traversing the corresponding paths as usual. In this way, our algorithm achieves a linear time complexity for both acyclic and cyclic data.     

An efficient path computation model for hierarchically structured topographical road maps

In this paper, we have developed a HiTi (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiTi graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SPAH, which utilizes HiTi graph model of a topographical road map for its computation. We give the proof for the optimality of SPAH. Our performance analysis of SPAH on grid graphs showed that it significantly reduces the search space over existing methods. We also present an in-depth experimental analysis of HiTi graph method by comparing it with other similar works on grid graphs. Within the HiTi graph framework, we also propose a parallel shortest path algorithm named ISPAH. Experimental results show that inter query shortest path problem provides more opportunity for scalable parallelism than the intra query shortest path problem.     

From orthogonal projections to a generalized quantum search

A quantum algorithm with certainty is introduced in order to find a marked pre-image of an element which is known to be in the image domain of an orthogonal projection operator. The analysis of our algorithm is made by using properties of the Moebius transformations acting on the complex projective line. This new algorithm closely resembles the quantum amplitude amplification algorithm, however it is proven that our algorithm is a proper generalization of the latter (with generalized phases), in such a way that the quantum search engine of the main operator of quantum amplification is included as a particular case. In order to show that there exist search problems that can be solved by our proposal but cannot be by applying the quantum amplitude amplification algorithm, we modify our algorithm as a cryptographic authentification protocol. This protocol results to be robust enough against attacks based on the quantum amplitude amplification algorithm. As a byproduct, we show a condition where it is impossible to find exactly a pre-image of an orthoghonal projection. This result generalizes the fact that, it is impossible to find a target state exactly by using quantum amplification on a three dimensional invariant subspace.     

Bi-directional graph search strategies for speech recognition

We describe a new search algorithm for speech recognition which applies the monotone graph search procedure to the problem of building a word graph. A first backward pass provides a method for estimating the word boundary times and phone segment boundary times needed to build the word graph using either the 1-phone or 2-phone lookahead assumptions. It also provides a heuristic for the search which satisfies the monotonicity condition. A second backward pass applies forward–backward pruning to the word graph. We show how the search can be made to run very quickly if the 1-phone lookahead assumption holds. We present the results of experiments performed on the 5000-word speaker-independentWall Street Journaltask under both the 1-phone and 2-phone lookahead assumptions. These results show that the 1-phone lookahead assumption leads to unacceptably large error rates for speaker-independent recognition using current acoustic phonetic modelling techniques. Finally, we give an account of the methods we have developed to process speech data in successive blocks so as to address the real-time issue and to control the memory requirements of the search.     

基于3D角度编码的量子遗传算法

为了充分利用量子态在算法中的量子特性,提高算法的搜索效率,减少存储空间,提出了一种基于3D角度编码的量子遗传算法。该算法将量子位描述为3D球面坐标下的一对相位角,充分利用了量子的空间运动特性,并引入一种自适应旋转角大小和方向的确定方案,从而进一步简化了染色体的更新和变异过程,而且使算法的量子特性、存储性能、时间性能都得到很大的提高。仿真结果表明,其在算法优化效率和搜索能力上都优于简单遗传算法和普通量子遗传算法。     

Laplacian versus adjacency matrix in quantum walk search

A quantum particle evolving by Schrödinger’s equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace’s operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.     

非布尔问题系统求解算法的一种新思路

非布尔变量的约束可满足性问题有两种较为普遍的求解方法,系统求解算法就是其中的一种。该算法的基本思想是对变量的值域空间逐个进行搜索,其优点是只要问题有解,算法就一定能给出正确答案。在最不理想的情况下,该算法时间复杂度为变量数目的指数级。该文给出一种新策略,虽然在本质上仍然是在值域空间中进行搜索,但在实现过程中根据启发式思想,有针对性地设置搜索的优先次序。它的目的是尽可能的缩小搜索空间的范围,因为实践证明算法计算过程中许多状态不需要搜索。几个实例证明该策略在许多情况下有较为令人满意的性能。同时该文还给出相应的理论分析。     

基于最大Code码的极大完全子图算法

本文通过引入极大code码,提出了一种寻找图的极大完全子图的算法FMCSG,该算法用邻接矩阵表示图。在寻找极大完全子图时根据得到的code码及时剪掉非极大code码的子矩阵,从而减少对矩阵的遍历次数,提高了算法的效率。     

Optimization of rule-based systems using state space graphs

Embedded rule-based expert systems must satisfy stringent timing constraints when applied to real-time environments. The paper describes a novel approach to reduce the response time of rule-based expert systems. The optimization method is based on a construction of the reduced cycle-free finite state space graph. In contrast with traditional state space graph derivation, the optimization algorithm starts from the final states (fixed points) and gradually expands the state space graph until all of the states with a reachable fixed point are found. The new and optimized system is then synthesized from the constructed state space graph. The authors present several algorithms implementing the optimization method. They vary in complexity as well as in the usage of concurrency and state-equivalency-both targeted toward minimizing the size of the optimized state space graph. Though depending on the algorithm used, optimized rule-based systems: (1) in general have better response time in that they require fewer rule firings to reach the fixed point; (2) are stable, i.e., have no cycles that would result in the instability of execution; and (3) have no redundant rules. They also address the issue of deterministic execution and propose optimization algorithms that generate the rule-bases with single corresponding fixed points for every initial state. The synthesis method also determines the tight response time bound of the new system and can identify unstable states in the original rule-base     

gBoost: a mathematical programming approach to graph classification and regression

Graph mining methods enumerate frequently appearing subgraph patterns, which can be used as features for subsequent classification or regression. However, frequent patterns are not necessarily informative for the given learning problem. We propose a mathematical programming boosting method (gBoost) that progressively collects informative patterns. Compared to AdaBoost, gBoost can build the prediction rule with fewer iterations. To apply the boosting method to graph data, a branch-and-bound pattern search algorithm is developed based on the DFS code tree. The constructed search space is reused in later iterations to minimize the computation time. Our method can learn more efficiently than the simpler method based on frequent substructure mining, because the output labels are used as an extra information source for pruning the search space. Furthermore, by engineering the mathematical program, a wide range of machine learning problems can be solved without modifying the pattern search algorithm.     

基于边映射表连接的匹配算法

针对面向语义网络图匹配的特殊性, 在基于状态回溯搜索算法的基础上提出一种新的称为基于边映射表连接的匹配算法, 利用语义网络图的有向性, 将图匹配问题转换为对搜索路径的规划, 并采用深度优先算法形成搜索步, 同时对目标图的所有边建立索引, 加快以边匹配为中心形成边映射表的过程, 最后对边映射表进行连接形成结果集。在真实数据集上的实验结果表明, 该算法具有较高的执行效率。     

基于重启型随机游走模型的图上关键字搜索

基于重启型随机游走模型和个人化PageRank算法,提出一种新的图上关键字搜索算法。该算法将向量空间模型和随机游走模型进行有效的结合,使查询搜索得到的结果可以匹配查询关键字,通过充分挖掘利用图中隐含的结构信息,更好地提供搜索结果。实验结果证明了该算法的有效性。     

Interactive visual analysis of time-series microarray data

Estimating dynamic regulatory pathways using DNA microarray time-series can provide invaluable information about the dynamic interactions among genes and result in new methods of rational drug design. Even though several purely computational methods have been introduced for DNA pathway analysis, most of these techniques do not provide a fully interactive method to explore and analyze these dynamic interactions in detail, which is necessary to obtain a full understanding. In this paper, we present a unified modeling and visual approach focusing on visual analysis of gene regulatory pathways over time. As a preliminary step in analyzing the gene interactions, the method applies two different techniques, a clustering algorithm and an auto regressive (AR) model. This approach provides a successful prediction of the dynamic pathways involved in the biological process under study. At this level, these pure computational techniques lack the transparency required for analysis and understanding of the gene interactions. To overcome the limitations, we have designed a visual analysis method that applies several visualization techniques, including pixel-based gene representation, animation, and multi-dimensional scaling (MDS), in a new way. This visual analysis framework allows the user to quickly and thoroughly search for and find the dynamic interactions among genes, highlight interesting gene information, show the detailed annotations of the selected genes, compare regulatory behaviors for different genes, and support gene sequence analysis for the interesting genes. In order to enhance these analysis capabilities, several methods are enabled, providing a simple graph display, a pixel-based gene visualization technique, and a relation-displaying technique among gene expressions and gene regulatory pathways.     

HARD: A hypercube embedding algorithm for state assignment of finite state machines

To minimize the area of the combinational circuit, required to realize a finite state machine (FSM), an efficient assignment of states of the FSM to a set of binary codes is required. As to find an optimal state assignment is NP-hard, therefore heuristic approaches have been taken. One approach generates an adjacency graph from the FSM model and then tries to embed the adjacency graph onto a hypercube with an objective to minimize the cost of mapping. However, hypercube embedding itself is an NP-complete problem. In this paper we present a solution to the hypercube embedding problem by designing a new technique, designated as HARD, that is a hybrid combination of non-linear programming method and a local search. We have transformed our problem from discrete space to continuous space and have applied logarithmic barrier function method, that in turn uses gradient projection approach to minimize the objective function. Each iteration of the gradient projection method produces a valid solution. Local search is performed around solution to improve its quality by using a Kernighan-Lin style algorithm. Two distributed algorithms for the HARD, have also been designed and implemented on network of workstations under message passing interface, to speed up the search. We have carried out a large number of experiments to determine the efficiency of the HARD in terms of solution quality over many other techniques, and have obtained very promising results.     

面向图相似性搜索的高效图编辑距离算法

在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。     

大图上跳数受限的可达查询算法研究与优化

判断有向图上两个顶点之间是否存在一条路径是一个经典问题,而对于一些路由规划和图分析等实际应用,要求查找是否存在跳数受限的可达路径,这是一个变种的图可达查询问题.对于大图上跳数受限的查询算法,不仅仅要对大图查询的时间效率和空间效率进行权衡,而且还要利用跳数受限的特性进行优化.普通的可达查询算法存在小度数顶点索引项占用空间过多的问题,造成空间浪费严重.为此我们提出了一种面向跳数受限的2-hop部分索引方法,采用改进的索引方法并结合局部搜索,实现跳数受限的有效可达性查询.实验结果表明,在Orkut社交网络数据集上与已有算法相比,该算法索引空间节省了32％,同时查询时间略微增加,使得我们算法可以计算更大规模图的跳数受限可达问题.