ADOPT-ing: unifying asynchronous distributed optimization with asynchronous backtracking

This article presents an asynchronous algorithm for solving distributed constraint optimization problems (DCOPs). The proposed technique unifies asynchronous backtracking (ABT) and asynchronous distributed optimization (ADOPT) where valued nogoods enable more flexible reasoning and more opportunities for communication, leading to an important speed-up. While feedback can be sent in ADOPT by COST messages only to one predefined predecessor, our extension allows for sending such information to any relevant agent. The concept of valued nogood is an extension by Dago and Verfaille of the concept of classic nogood that associates the list of conflicting assignments with a cost and, optionally, with a set of references to culprit constraints. DCOPs have been shown to have very elegant distributed solutions, such as ADOPT, distributed asynchronous overlay (DisAO), or DPOP. These algorithms are typically tuned to minimize the longest causal chain of messages as a measure of how the algorithms will scale for systems with remote agents (with large latency in communication). ADOPT has the property of maintaining the initial distribution of the problem. To be efficient, ADOPT needs a preprocessing step consisting of computing a Depth-First Search (DFS) tree on the constraint graph. Valued nogoods allow for automatically detecting and exploiting the best DFS tree compatible with the current ordering. To exploit such DFS trees it is now sufficient to ensure that they exist. Also, the inference rules available for valued nogoods help to exploit schemes of communication where more feedback is sent to higher priority agents. Together they result in an order of magnitude improvement.     

Multi-variable fuzzy logic control for a class of distributed parameter systems

A multi-variable fuzzy logic controller (FLC) is proposed to control a class of distributed parameter systems (DPSs). When a DPS is transformed into finite-dimensional ordinary differential equations (ODEs) by using time/space separation, each ODE can be considered as a subsystem. According to design strategy of conventional FLC, one FLC should be designed for one subsystem. It will be very complex because there are many subsystems. In order to reduce design complexity, only a MF and a rule base are designed in the controller. For other subsystems or ODEs, their MFs can be designed equivalently by introducing scaling factors. Then, the proposed FLC has ability to control multi-variable processes. At last, the proposed FLC is applied to control a rod catalytic reaction process. The simulation results demonstrate the effectiveness of the proposed fuzzy control strategy.     

用回溯法求哈密顿通路

回溯法是一种按照深度优先的策略从根结点开始搜索解空间树的算法,该算法可以用来求出问题的全部解,也可以在求出问题的一个解之后停止对问题的求解,即只求该问题是否有解。哈密顿通路就是判断图中是否存在一条通过所有顶点一次且仅一次的路径。本文主要讲的就是用回溯法来求解一个任意的图中是否存在一条哈密顿通路的问题,并用具体的算法来实现它。     

Universal traversal sequences with backtracking

In this paper we introduce a new notion of traversal sequences that we call exploration sequences. Exploration sequences share many properties with the traversal sequences defined in Aleliunas et al. (Proceedings on the 20th Annual Symposium of Foundations of Computer Science, 1979, pp. 218–223), but they also exhibit some new properties. In particular, they have an ability to backtrack, and their random properties are robust under choice of the probability distribution on labels.Further, we present simple constructions of polynomial-length universal exploration sequences for some previously studied classes of graphs (e.g., 2-regular graphs, cliques, expanders), and we also present universal exploration sequences for trees. These constructions do not obey previously known lower bounds on the length of universal traversal sequences; thus, they highlight another difference between exploration and traversal sequences.     

Improving inter-block backtracking with interval Newton

Inter-block backtracking (IBB) computes all the solutions of sparse systems of nonlinear equations over the reals. This algorithm, introduced by Bliek et al. (1998) handles a system of equations previously decomposed into a set of (small) k ×k sub-systems, called blocks. Partial solutions are computed in the different blocks in a certain order and combined together to obtain the set of global solutions. When solutions inside blocks are computed with interval-based techniques, IBB can be viewed as a new interval-based algorithm for solving decomposed systems of nonlinear equations. Previous implementations used Ilog Solver and its IlcInterval library as a black box, which implied several strong limitations. New versions come from the integration of IBB with the interval-based library Ibex. IBB is now reliable (no solution is lost) while still gaining at least one order of magnitude w.r.t. solving the entire system. On a sample of benchmarks, we have compared several variants of IBB that differ in the way the contraction/filtering is performed inside blocks and is shared between blocks. We have observed that the use of interval Newton inside blocks has the most positive impact on the robustness and performance of IBB. This modifies the influence of other features, such as intelligent backtracking. Also, an incremental variant of inter-block filtering makes this feature more often fruitful.     

Debugging with dynamic slicing and backtracking

Programmers spend considerable time debugging code. Symbolic debuggers provide some help but the task remains complex and difficult. Other than breakpoints and tracing, these tools provide little high-level help. Programmers must perform many tasks manually that the tools could perform automatically, such as finding which statements in the program affect the value of an output variable for a given test case, and what was the value of a given variable when the control last reached a given program location. If debugging tools provided explicit support for these tasks, the debugging process could be automated to a significant extent. In this paper we present a debugging model, based on dynamic program slicing and execution backtracking techniques, that easily lends itself to automation. This model is based on experience with using these techniques to debug software. We also present a prototype debugging tool, SPYDER, that explicitly supports the proposed model, and with which we are performing further debugging research.     

Intractable unifiability problems and backtracking

Restrictions of the problem of finding all maximal unifiable or minimal nonunifiable subsets to those of certain sizes are shown to be NP-hard, and consequently inappropriate in general for reducing thrashing by intelligent backtracking in resolution theorem provers and logic program executions. We also show that existing backtrack methods based on the computation of all maximal unifiable subsets of assignments as a means to avoid thrashing are intractable because the solution length of these subsets can increase exponentially with the input length, and we give a corresponding result for minimal nonunifiability. The results apply not only to standard unification, but to a characterized collection of unification algorithms which includes unification without the occurs check. This now justifies the necessity for approximate or heuristic approaches to reduce thrashing in resolution theorem provers and the execution of logic programs.A version of this paper appears in Proceedings of the Third International Logic Programming Conference, London, Lecture Notes in Computer Science, Springer 225, 107–121 (1986).     

Intelligent backtracking in plan-based deduction

This paper develops a method of mechanical deduction based on a graphical representation of the structure of proofs. Attempts to find a refutation(s) are recorded in the form of plans, corresponding to portions of an AND/OR graph search space and representing a purely deductive structure of derivation. This method can be applied to any initial base (set of nonnecessarily Horn clauses). Unlike the exhaustive (blind) backtracking which treats all the goals deduced in the course of a proof as equally probable sources of failure, his approach detects the exact source of failure. Only a small fragment of the solution space is kept on disk as a collection of pairs, each of which consists of a plan and a graph of constraints. The search strategy and the method of nonredundant processing of individual pairs which leads to a solution (if it exists) is presented. This approach is compared?on a special case?with a blind backtracking algorithm for which an exponential improvement is demonstrated. Some important implementation problems are discussed, and toplevel design of a mechanical deduction system implementing our algorithm is presented. It is proven that the algorithm is complete in the following sense: if for a given base a resolution refutation exists, then this refutation is found by the algorithm.     

Backjump-based backtracking for constraint satisfaction problems

The performance of backtracking algorithms for solving finite-domain constraint satisfaction problems can be improved substantially by look-back and look-ahead methods. Look-back techniques extract information by analyzing failing search paths that are terminated by dead-ends. Look-ahead techniques use constraint propagation algorithms to avoid such dead-ends altogether. This paper describes a number of look-back variants including backjumping and constraint recording which recognize and avoid some unnecessary explorations of the search space. The last portion of the paper gives an overview of look-ahead methods such as forward checking and dynamic variable ordering, and discusses their combination with backjumping.     

多变量涡街变送器的研究

在生产过程自动控制领域中,用1台仪表同时进行温度、压力、流量等参数测量的多变量变送器是非常重要的,介绍了多变量变送器的工作原理、结构,讨论了二线制变送器的设计难点。     

A quantum mutation-based backtracking search algorithm

The exposition of any nature-inspired optimization technique relies firmly upon its executed organized framework. Since the regularly utilized backtracking search algorithm (BSA) is a fixed framework, it is not always appropriate for all difficulty levels of problems and, in this manner, probably does not search the entire search space proficiently. To address this limitation, we propose a modified BSA framework, called gQR-BSA, based on the quasi reflection-based initialization, quantum Gaussian mutations, adaptive parameter execution, and quasi-reflection-based jumping to change the coordinate structure of the BSA. In gQR-BSA, a quantum Gaussian mechanism was developed based on the best population information mechanism to boost the population distribution information. As population distribution data can represent characteristics of a function landscape, gQR-BSA has the ability to distinguish the methodology of the landscape in the quasi-reflection-based jumping. The updated automatically managed parameter control framework is also connected to the proposed algorithm. In every iteration, the quasi-reflection-based jumps aim to jump from local optima and are adaptively modified based on knowledge obtained from offspring to global optimum. Herein, the proposed gQR-BSA was utilized to solve three sets of well-known standards of functions, including unimodal, multimodal, and multimodal fixed dimensions, and to solve three well-known engineering optimization problems. The numerical and experimental results reveal that the algorithm can obtain highly efficient solutions to both benchmark and real-life optimization problems.

     

An empirical comparison of backtracking algorithms

In this paper we report the results of experimental studies of zero-level, one-level, and two-level search rearrangement backtracking. We establish upper and lower limits for the size problem for which one-level backtracking is preferred over zero-level and two-level methods, thereby showing that the zero-level method is best for very small problems. The one-level method is best for moderate size problems, and the two-level method is best for extremely large problems. Together with our theoretical asymptotic formulas, these measurements provide a useful guide for selecting the best search rearrangement method for a particular problem.     

Dead-beat Response in Multi-variable Systems

In this paper linear sampled data multi-variable synthesis is considered by the use of state difference equations. Murphy and Meksuwan's “1963” of approach is generalized for multi-variable systems. The non-interaction condition limits the achievement of dead-beat response depending on the nature of the input and the order of the individual transfer functions of the system. The method is general and can be applied to any polynominal input and also when non-linearities are present just after the compensator.     

基于回溯算法的选课推荐系统的设计与实现

大学生选课是一个既重要又繁琐的过程,如果不提前规划,就有可能出现错失特定学期的中意课程,单学期课业量过重和时间浪费问题,进而影响学习主动性和学业成绩.为解决上述问题,研发选课推荐系统,根据学生所设限定条件推荐多学期的选课方案.文章提出基于0-1背包的回溯算法来处理约束,可以大范围剪枝,加快求解速度.测试结果表明,本系统可以为学生推荐意向匹配率高且课业量少的选课方案.     

On the efficiency of parallel backtracking

Analytical models and experimental results concerning the average case behavior of parallel backtracking are presented. Two types of backtrack search algorithms are considered: simple backtracking, which does not use heuristics to order and prune search, and heuristic backtracking, which does. Analytical models are used to compare the average number of nodes visited in sequential and parallel search for each case. For simple backtracking, it is shown that the average speedup obtained is linear when the distribution of solutions is uniform and superlinear when the distribution of solutions is nonuniform. For heuristic backtracking, the average speedup obtained is at least linear, and the speedup obtained on a subset of instances is superlinear. Experimental results for many synthetic and practical problems run on various parallel machines that validate the theoretical analysis are presented     

A data-dependency-based intelligent backtracking scheme for PROLOG

This paper presents a scheme for intelligent backtracking in PROLOG programs. Rather than doing the analysis of unification failures, this scheme chooses backtrack points by doing the analysis of data dependency between literals. The other data-dependency-based methods previously developed cannot be easily incorporated in Warren's abstract machine, and are not able to perform across-the-clause backtracking intelligently. Our scheme overcomes all these defects. For many problems this scheme is just as effective as intelligent backtracking schemes based upon (more accurate) analysis of unification failure, and yet incurs small space and time over- head. To demonstrate the usefulness of our scheme, we have modified a simulator of Warren's abstract machine to incorporate our intelligent backtracking scheme, and have evaluated its performance on a number of problems.