智能回溯的两大途径

本文详细介绍了获得智能回溯的两个基本方法:最小不一致演绎树和最大可合一约束集。逻辑程序求解失败时,这两种方法均可分析引起失败的原因,前者在与失败有关的子句空间内进行回溯,后者找出所有可能的回溯点,以便选择最佳回溯点进行回溯。     

变量驱动的智能回溯

本文提出了一个逻辑程序与并行智能回溯模型——变量驱动的智能回溯.文字求解失败时,分析其中参数的失败类型,生成回溯文字集。以变量驱动图为基础,回溯仅在回溯文字集中进行.     

超前检查和选择回溯策略

本文提出了PROLOG语言的一种新的推理策略:超前检查和选择回溯算法-FTSB(Forword Testing and Selected Backtracking),FTSB的推理过程全部在产生变量约束的目标上进行,而不是在每个目标上进行,它采用超前检查的方法尽早放弃不可能成为解的约束,使回溯发生率下降,并用智能的方法选择回溯点和获得多重解。     

共享变量的识别与智能回溯算法

本文分析讨论了PROLOG程序中的变量共享及其在流并行处理和智能回溯中的重要作用,提出了识别共享变量的静、动态结合算法以及在此基础上的流并行子目标的识别算法和智能回溯算法。     

基于几何相交测试的机器人路径规划算法

针对机器人路径规划问题,提出一种基于几何相交测试的路径规划方法.该方法首先搜索位于当前路径点到目标点连线上的首障碍栅格;然后结合贪婪法、回溯法和邻域搜索策略从障碍栅格邻域搜索下一个路径栅格;接着从新的路径点出发迭代搜索后续的路径点,从而确定从起点到目标点的路径;最后对得到的最好路径进行路径点合并以提高路线的连贯性.实验结果表明,新方法规划的路径性能优于其他同类算法,路径呈现出更好的连续性,规划时间能满足实际应用的要求.     

电路结构特殊点及可测性研究

电路结构上一些特殊点对于电路的测试影响很大,通过对电路结构上一些特殊点的性质、作用、它们之间的相互关系,以及电路结构可测性与这些点的关系进行研究,按照它们的作用大小进行排序,从而加快确定性测试码的生成速度,减少回溯次数和缩短回溯时间,提高其可测性。     

覆盖测试中基于回溯法的路径选择

单元覆盖测试的目标是达到尽可能高的覆盖率。为了提高自动化单元测试的覆盖率,本文提出了一种面向目标覆盖元素,基于回溯法遍历程序控制流图,选择可达路径的方法。该方法从函数入口节点开始,进行深度优先的路径遍历,以当前的部分路径是否可达和当前节点是否能够到达目标覆盖元素,作为回溯的条件进行回溯,最终获得一条经过目标覆盖元素的可达路径。最后结合测试用例生成对5个函数单元与原有的选路方案进行语句覆盖测试的对比实验,平均覆盖率从70%提升到了90%,验证了该方法能够有效地提升覆盖率。又针对linux实际大工程进行语句,分支,MCDC覆盖的选路实验,能够获得较高的覆盖率,验证了该方法能够适用于多种不同覆盖准则下的选路。     

从节点度数生成无向简单连通图

许多现实问题可以抽象成无向简单连通图的生成问题。为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题。     

贪心与回溯算法在城市马拉松路线规划中的实践

针对目前城市马拉松路线人工规划效率低下的问题, 本文采用贪心和回溯算法进行城市马拉松路线智能规划, 具体方法是: 通过城市路网信息构建由经纬度坐标点拓扑关系连接而成的路网, 采用贪心和回溯算法对坐标点进行遍历搜索, 结合城市马拉松路线特殊要求, 运用直接逼近、启发式远离、启发式靠近和方向预估等策略实现路线的智能规划. 在此基础上, 提出一种综合POI热度值、道路宽度适宜度、路线畅通指数、过弯舒适度以及POI密集度5个维度的马拉松路线评估方法. 最后, 开展了北京、合肥马拉松人工和智能规划路线对比分析, 结果表明所采用的方法可快速高效实现马拉松路线规划.     

基于单模式匹配算法的研究

针对应用广泛的单模式匹配算法进行阐述:先分析最原始的BF算法,它会产生指针回溯;接着分析KMP算法,它避免了BF算法中的指针回溯;然后分析Snort系统中采用的BM模式匹配算法的基本思想,它对目标串进行跳跃式搜索;分析了BMH算法,它较BM算法性能上又有显著提高;最后对各种算法作了一个比较,并通过实验进行性能测试。     

高效逻辑语言实现方法

本文提出了一个基于优化编译和智能控制的高效逻辑语言实现方法。该方法克服了逻辑语言中合一和回溯操作的瓶颈问题，有效地提高了逻辑程序的执行效率。该方法可为设计智能加速部件和智能计算机提供参考。     

合一和回溯智能加速部件的设计与实现

本文设计了一个高效的合一和回溯智能加速部件，在实现时我们运用了自己提出的优化线性合一算法超前检查智能回溯策略。经测试和分析表明，采用该加速部件的Ｐｒｏｌｏｇ实现系统的效率要比软件实现提高十倍以上。     

Prolog语言抽象机器GOAM的设计与实现

本文提出了一种抽象机ＧＯＡＭ,是Ｐｒｏｌｏｇ语言新的运行和实现方式,因为ＧＯＡＭ内存管理是一种堆式内存分配方法,所以具有潜在的并行性,另外ＧＯＡＭ控制算法是智能回溯方法,ＧＯＡＭ在没有引入冗余信息的情况下提高了系统的效率。     

Backtracking in independent and-parallel implementations of logicprogramming languages

In this paper, we present an implementation model which efficiently supports backtracking in an independent and-parallel nondeterministic system. The problem is tackled in the context of logic programming, although the solution proposed is sufficiently general to be easily extended to different nondeterministic systems, such as constraint programming systems. The complexity of the problem is demonstrated by the fact that most existing and-parallel systems either do not support backtracking over and-parallel calls or simply avoid analyzing the performance of their systems in the presence of nondeterministic benchmarks. The implementation model we present is an extension of the backtracking scheme developed by Hermenegildo and Nasr (1986) and relies on a novel memory organization scheme and on the use of various optimizations to reduce communication and overhead. The solution developed has been implemented in the ACE Parallel Prolog system. The performance of the system is analyzed on a variety of benchmarks. The results obtained are remarkable: speedups achieved during forward execution are not lost in heavy backtracking activities and, frequently, super-linear speedups are obtained thanks to a semi-intelligent backtracking scheme     

Reverse execution in a generalized control regime

The value of advanced control forms in programming languages is currently being recognized. A combination of control forms in a single environment can increase the expressive power of a system but may lead to difficulties in semantic definition and implementation. This paper describes an implementation for a control combination of backtracking and logical concurrent structures. In particular, we present a reversible execution implementation for backtracking across scheduled coroutines or processes as defined in Simula [1]. Such a control combination, particularly useful for debugging simulation programs, is incorporated as a basic feature in a debugging tool expecially designed for programs using scheduled processes.     

Dynamic Reverse Code Generation for Backward Execution

The need for backward execution in debuggers has been raised a number of times. Backward execution helps a user naturally think backwards and, in turn, easily locate the cause of a bug. Backward execution has been implemented mostly by state-saving or checkpointing, which are inherently not scalable. In this paper, we present a method to generate reverse code, so that backtracking can be performed by executing reverse code. The novelty of our work is that we generate reverse code on-the-fly, while running a debugger, which makes it possible to apply the method even to debugging multi-threaded programs.     

Labelled splitting

We define a superposition calculus with explicit splitting on the basis of labelled clauses. For the first time we show a superposition calculus with an explicit non-chronological backtracking rule sound and complete. The new backtracking rule advances backtracking with branch condensing known from SPASS. An experimental evaluation of an implementation of the new rule shows that it improves considerably on the previous SPASS splitting implementation. Finally, we discuss the relationship between labelled first-order splitting and DPLL style splitting with intelligent backtracking and clause learning.     

Intelligent backtracking in CLP(ℜ)

CLP() is a constraint logic programming language in which constraints can be expressed in the domain of real numbers. Computation in this specialized domain gives access to information useful in intelligent backtracking. In this paper, we present an efficient constraint satisfaction algorithm for linear constraints in the real number domain and show that our algorithm directly generates minimal sets of conflicting constraints when failures occur. We demonstrate how information gleaned during constraint satisfaction can be integrated with unification failure analysis. The resulting intelligent backtracking method works in the context of a two-sorted domain, where variables can be bound to either structured terms or real number expressions. We discuss the implementation of backtracking and show examples where the benefit of pruning the search tree outweights the overhead of failure analysis.     

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).     

Automated software test data generation

An alternative approach to test-data generation based on actual execution of the program under test, function-minimization methods and dynamic data-flow analysis is presented. Test data are developed for the program using actual values of input variables. When the program is executed, the program execution flow is monitored. If during program execution an undesirable execution flow is observed then function-minimization search algorithms are used to automatically locate the values of input variables for which the selected path is traversed. In addition, dynamic data-flow analysis is used to determine those input variables responsible for the undesirable program behavior, significantly increasing the speed of the search process. The approach to generating test data is then extended to programs with dynamic data structures and a search method based on dynamic data-flow analysis and backtracking is presented. In the approach described, values of array indexes and pointers are known at each step of program execution; this information is used to overcome difficulties of array and pointer handling