Visual Prolog截断机制对回溯的作用机理

回溯是一种获得目标所有可能解的良好方法.然而不恰当地使用回溯,可能导致系统效率降低,时空开销增大,因此必须设置相应机制,仔细控制回溯过程.Visual Prolog的控制谓词,即失败谓词fail和否定谓词not,与截断机制,包括静态截断机制和动态截断机制,构成了完整的目标搜索求解控制机制,可以实现对搜索过程的仔细控制,减少不必要的回溯.该文在考察Visual Prolog回溯机制和截断机制的基础上,通过实例,对其静态截断机制和动态截断机制进行了详细分析,从而揭示回溯机制和截断机制的本质特性和应用机理.

Effects of Cut Mechanisms on Backtracking in Visual Prolog

The backtracking is a good approach for obtaining all the possible solutions. However, the backtracking improperly used might lead to the reduced efficiency of a system and the augmented overheads in running time and memory required. Hence, it is necessary to setup a related mechanism to carefully control backtracking courses. The full control mechanism of goal-searching and problem-solving is composed of both the control predicates in Visual Prolog, or predicates fail and not, and the cut mechanisms, including those of the static and dynamic cut, and can be utilized for controlling exactly the goal-searching courses and for reducing unnecessary backtracking. On the basis of exposing the backtracking mechanism and the cut mechanism in Visual Prolog illustrated with a group of instances, both the static and dynamic cut mechanisms are investigated in detail. Thus the essential characteristics and fundamentals of applications of the backtracking mechanism and that of the cut mechanisms are demonstrated.