The complexity of the satisfiability problem for Krom formulas

We study the computational complexity of the satisfiability problem for Krom (CNF-2) formulas. Upper and lower bounds are obtained for several decidable classes of formulas determined by quantifier prefix and degree of predicate letters. For example, we show that determining satisfiability of Krom formulas with quantifier prefix of the form ……… is complete for deterministic exponential time, but that if the number of universal quantifiers is bounded then polynomial time suffices.     

A bidirectional shortest-path algorithm with good average-case behavior

The two-terminal shortest-path problem asks for the shortest directed path from a specified nodes to a specified noded in a complete directed graphG onn nodes, where each edge has a nonnegative length. We show that if the length of each edge is chosen independently from the exponential distribution, and adjacency lists at each node are sorted by length, then a priority-queue implementation of Dijkstra's unidirectional search algorithm has the expected running time (n logn). We present a bidirectional search algorithm that has expected running time (n logn). These results are generalized to apply to a wide class of edge-length distributions, and to sparse graphs. If adjacency lists are not sorted, bidirectional search has the expected running time (an) on graphs of average degreea, as compared with (an) for unidirectional search.     

A bidirectional shortest-path algorithm with good average-case behavior

The two-terminal shortest-path problem asks for the shortest directed path from a specified nodes to a specified noded in a complete directed graphG onn nodes, where each edge has a nonnegative length. We show that if the length of each edge is chosen independently from the exponential distribution, and adjacency lists at each node are sorted by length, then a priority-queue implementation of Dijkstra's unidirectional search algorithm has the expected running time Θ(n logn). We present a bidirectional search algorithm that has expected running time Θ(√n logn). These results are generalized to apply to a wide class of edge-length distributions, and to sparse graphs. If adjacency lists are not sorted, bidirectional search has the expected running time Θ(a√n) on graphs of average degreea, as compared with Θ(an) for unidirectional search.     

Minimizing worst-case and average-case makespan over scenarios

We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all scenarios in an explicitly given set. Each scenario is a subset of jobs that must be executed in that scenario. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. We also consider some (easier) special cases. Combinatorial optimization problems under scenarios in general, and scheduling problems under scenarios in particular, have seen only limited research attention so far. With this paper, we make a step in this interesting research direction.     

Separable resolution method for checking the satisfiability of formulas in the languageL

Conclusion This paper offers an effective resolution method for checking the satisfiability of a collection of disjuncts in the languageL. The method permits one to substantially reduce the number of generated resolvents in comparison with the method ofR-resolution. One more factor ensuring the efficiency of the method is a significant reduction in the number of disjunct pairs checked for the possibility of resolving them. As for the number of generated disjuncts, its greatest reduction is obtained in the case of the use of the disjunct-set partition corresponding to the limiting system of predicate-symbol subsets given by symbol ordering. It is possible to interpret the result obtained for this case as proof of the completeness of the strategy combining an ordering of predicate symbols andR-resolution. It is necessary to note that to different orderings of predicate symbols correspond different partitions of the disjunct set giving, in turn, different numbers of generated disjuncts in the process ofSp-completion. Nevertheless, the methods described in Sec. 2, which use partition of the disjunct set into two classes, are of independent importance. As has already been said, completion of a disjunct set is used for solution of a number of problems during the design of a procedural automaton specification. For example, in the case of checking the consistency of two interacting automata [5] based on completion of a disjunct set, there exists a natural partition of the predicate symbols into input and output symbols, to which corresponds the partition of the disjunct set into subsets specifying the interacting automata. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 13–20, November–December, 1998.     

基于满二叉树的二分K-means聚类并行推荐算法

在推荐系统中应用K-means算法聚类可有效降维,然而聚类效果往往依赖于选定的初始中心,并且一旦选定目标簇后,推荐过程只针对目标簇进行,与其他簇无关。针对上述两个问题,提出一种基于满二叉树的二分K-means聚类并行推荐算法。该算法首先反复迭代二分K-means算法,迭代过程中使用簇内凝聚度作为分裂阈值,形成一颗满二叉树;然后通过层次遍历将用户归入到K个叶子节点(簇);最后针对K个簇,应用MapReduce框架进行并行推荐预测。MovieLens上的实验结果表明,该算法可大幅度提高推荐系统准确性,同时增强系统可扩展性。     

A simplifier for propositional formulas with many binary clauses

Deciding whether a propositional formula in conjunctive normal form is satisfiable (SAT) is an NP-complete problem. The problem becomes linear when the formula contains binary clauses only. Interestingly, the reduction to SAT of a number of well-known and important problems--such as classical AI planning and automatic test pattern generation for circuits--yields formulas containing many binary clauses. In this paper we introduce and experiment with 2-SIMPLIFY, a formula simplifier targeted at such problems. 2-SIMPLIFY constructs the transitive closure of the implication graph corresponding to the binary clauses in the formula and uses this graph to deduce new unit literals. The deduced literals are used to simplify the formula and update the graph, and so on, until stabilization. Finally, we use the graph to construct an equivalent, simpler set of binary clauses. Experimental evaluation of this simplifier on a number of bench-mark formulas produced by encoding AI planning problems prove 2-SIMPLIFY to be a useful tool in many circumstances.     

An effective heuristic algorithm for the maximum satisfiability problem

Stochastic local search algorithms (SLS) have been increasingly applied to approximate solutions of the weighted maximum satisfiability problem (MAXSAT), a model for solutions of major problems in AI and combinatorial optimization. While MAXSAT instances have generally a strong intrinsic dependency between their variables, most of SLS algorithms start the search process with a random initial solution where the value of each variable is generated independently with the same uniform distribution. In this paper, we propose a new SLS algorithm for MAXSAT based on an unconventional distribution known as the Bose-Einstein distribution in quantum physics. It provides a stochastic initialization scheme to an efficient and very simple heuristic inspired by the co-evolution process of natural species and called Extremal Optimization (EO). This heuristic was introduced for finding high quality solutions to hard optimization problems such as colouring and partitioning. We examine the effectiveness of the resulting algorithm by computational experiments on a large set of test instances and compare it with some of the most powerful existing algorithms. Our results are remarkable and show that this approach is appropriate for this class of problems.     

Performance analysis of diamond search algorithm over full search algorithm

Microsystem Technologies - Motion estimation is a progression used to estimate motion vectors between two or more images with a high degree of temporal redundancy. It is commonly used in video...     

求解可满足性问题的信息传播算法研究综述

信息传播算法来自统计物理,被广泛应用于人工智能各个领域,特别是求解组合优化问题时,具有良好的有效性。通过对信息传播算法的相关文献进行分析,综述了信息传播算法以及其相关应用的发展史,根据信息传播算法的发展,介绍了求解可满足性问题的信息传播算法相关概念,主要涉及到警示传播算法、置信传播算法和调查传播算法,描述了三种算法发展中出现的收敛性、有效性研究,分别综述了各个算法在相关领域的应用情况,并总结了信息传播算法的研究路径和应用方向。     

二元域多项式基的按字求模算法

介绍了二元域多项式基及其按位(bit)求模算法,给出了一种新的通用的不要预计算的二元域多项式基按字(word)求模算法,由于可以选择不同的字长如8位字长或16位字长等,因而该算法既适合软件也适合硬件。在32位字长PC机环境下,给出了针对特定二元域和模约多项式的简化算法。在大量实验的基础上,对按字求模算法和按位求模算法的运算结果和运算速度的比较结果表明,两者运算结果相同,但前者平均运算速度比后者快30多倍。     

A Redundant Binary Algorithm for RSA

The normal form and modified normal form for binary redundant representation are defined.A redundant binary algorithm to compute modular exponentiation for very large integers is proposed.It is shown that the proposed algorithm requires the minimum number of basic operations(modular multiplications)among all possible binary redundant representations.     

An Algorithm Based on Tabu Search for Satisfiability Problem

In this paper,a computationally effective algorithm based on tabu search for solving the satisfiability problem(TSSAT)is proposed.Some novel and efficient heuristic strategies for generating candidate neighborhood of the curred assignment and selecting varibables to be flipped are presented. Especially,the aspiration criterion and tabu list tructure of TSSAT are different from those of traditional tabu search.Computational experiments on a class of problem insteances show that,TSSAT,in a reasonable amount of computer time ,yields better results than Novelty which is currently among the fastest known.Therefore TSSAT is feasible and effective.     

求解多文字可满足SAT问题的置信传播算法

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真.多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真.显然,此问题仍然是一个NP难问题.为了研究解决多文字可满足SAT问题的算法,引入随机实例产生模型,设计求解多文字可满足SAT问题的置信传播算法.最后,用实例模型产生了大量数据进行实验验证,结果表明:该算法求解多文字可满足SAT问题的性能优于其他启发式算法.     

A modified full multigrid algorithm for the Navier-Stokes equations

A modified full multigrid (FMG) method for the solution of the Navier-Stokes equations is presented. The method proposed is based on a V-cycle omitting the restriction procedure for dependent variables but retaining it for the residuals. This modification avoids possible mismatches between the mass fluxes and the restricted velocities as well as the turbulent viscosity and the turbulence quantities on the coarse grid. In addition, the pressure on the coarse grid can be constructed in the same way as the velocities. These features simplify the multigrid strategy and corresponding programming efforts. This algorithm is applied to accelerate the convergence of the solution of the Navier-Stokes equations for both laminar and high-Reynolds number turbulent flows. Numerical simulations of academic and practical engineering problems show that the modified algorithm is much more efficient than the FMG-FAS (Full Approximation Storage) method.     

GASAT: a genetic local search algorithm for the satisfiability problem

This paper presents GASAT, a hybrid algorithm for the satisfiability problem (SAT). The main feature of GASAT is that it includes a recombination stage based on a specific crossover and a tabu search stage. We have conducted experiments to evaluate the different components of GASAT and to compare its overall performance with state-of-the-art SAT algorithms. These experiments show that GASAT provides very competitive results.     

A parallel shrinking algorithm for binary patterns

A shrinking algorithm for parallel processing of binary patterns is proposed. It shrinks any pattern symmetrically from all sides to an isolated point at the center irrespective of the complexity of the pattern. It uses a window of 3 × 3 elements. This algorithm does not alter the connectivity properties of the patterns and shrinks each pattern to a single isolated element.