Method and apparatus for transparent backtracking

• US 6,446,057 B1
• Filed: 12/04/2000
• Issued: 09/03/2002
• Est. Priority Date: 10/24/1997
• Status: Expired due to Term

• Current Assignee: Versata Development Group, Inc. (ESW Capital, LLC)
• Original Assignee: Paul William Vaughan
• Inventors: Vaughan, Paul William
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/730,481
• Time in Patent Office: 638 Days
• Field of Search: 706/46, 706/48, 706/58, 717/5, 711/200, 716/1, 704/8
• US Class Current: 706/46
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A technique is used in embodiments of the invention such that backtracking programs can be written in a general purpose computer language (e.g., C++ or Java) without requiring the control structure of the program to reflect the structure of the decision tree. A data state and a control state are restored during backtracking. For restoring the data state, embodiments of the invention keep track of the changes made to variables and the point in execution at which the changes are made. When backtracking occurs, the data state can be restored by undoing the changes to the desired point in execution. For restoring the control state, the method of the invention provides a “failure” exception state that is invoked upon failure in the program (e.g., a failure to find a solution in a search program). The failure exception is “caught” by catch points established in the execution stack. The failure exception is passed up the execution stack until a point is reached prior to the failure at which execution should be re-initiated. Since the control structure of the search program need not have the same form as the decision tree, part of the control state for the desired decision point may no longer exist on the execution stack, so the catch point may not be directly associated with the desired point but merely preceed it. The remaining part of the control state is restored by re-executing the program in a special re-execution mode until the desired state is achieved and another alternative may be chosen.

Claims

1. A method of backtracking in a program executable in a memory medium of a computer system comprising a computer program written in a general purpose computer programming language comprising:

instantiating a choice point in an executable computer program in a memory medium, said choice point identifying a decision point in said program, at least one alternative choice being linked with said choice point;

preserving modifications to data in said program as defined at said choice point as a data state portion of part of said program'"'"'s processing state;

specifying a catch point associated with a point of execution prior to said choice point as a control state portion of said program'"'"'s processing state;

examining said choice point to find said at least one alternative choice;

traversing said choice point to evaluate the validity of said at least one alternative choice; and

restoring said program to said processing state at said catch point associated with said choice point by throwing an exception to said catch point and undoing said modifications when said at least one alternative choice is invalid.

2. The method of claim 1 further comprising:

retaining said modifications to said data state aftere restoring said processing state.

3. The method of claim 2 further comprising:

utilizing said retained modifications for verifying said data state after restoring said processing state.

4. The method of claim 1 wherein said catch point is explicitly specified.

5. The method of claim 1 wherein said catch point is implicitly specified.

6. A method of backtracking in a program executable in a memory medium of a computer system comprising a computer program written in a general purpose computer programming language comprising:

identifying a target choice point in a decision tree of an executable computer program by traversing a search stack backwards for at least one choice point linked to at least one untried alternative choice;

preserving data state of said program as defined at said target choice point by storing modifications to said data values in a modification object;

specifying a catch point associated with a point of execution prior to said target choice point in said program;

examining said target choice point to find said at least one untried alternative choice;

traversing said target choice point to evaluate the validity of said at least one untried alternative choice;

throwing an exception to said catch point when said at least one untried alternative choice is invalid;

restoring said program data state using said modification object; and

re-executing said program when said catch point is prior to said target choice point.

7. The method of claim 6 further comprising repeating from said identifying step on each of said at least one untried alternative choices.

8. The method of claim 6 further comprising:

retaining said modifications to said program data state after restoring said program data state.

9. The method of claim 8 retaining said modifications to said modifications to said program data state after restoring said program data state.

10. The method of claim 6 wherein said catch point is explicitly specified.

11. The method of claim 6 wherein said catch point is implicitly specified.

12. A transparent backtracking search system executable in a memory medium of a computer system comprising a computer program written in a general purpose computer programming language comprising:

a search system comprising;

a search stack residing in a memory medium of a computer system, said search stack comprising at least one choice point having a set of alternatives;

a model capable of examining said search stack to determine whether said set of alternatives are viable;

a means for inputting data; and

a means for outputting the search result;

an execution stack coupled to said model storing the execution state of said search system and a plurality of catch points in said search system;

an engine coupled to said model and said execution stack;

a means for validating the viability of choices of said set of alternatives;

a means for reverting said search system to one of said plurality of catch points of said execution stack and reverting said search stack to said a least one choice point having at least one untried alternative.

13. The system of claim 12 wherein said search system is capable of determining the viability of alternative configurations of a computer system.

14. The system of claim 13 wherein said validating means can determine the viability of installing a particular component in said computer system.

15. The system of claim 13 wherein said validating means can choose a component from a set of components existing in said computer system.

16. The system of claim 12 wherein said validating means is not recursive.

17. The system of claim 12 further comprising a means for re-executing processing from said catch point to said at least one choice point when said catch point is prior to said choice point.

18. The system of claim 12 wherein said engine is capable of causing said model to recreate a portion of said search stack.

19. The system of claim 12 wherein a set of modifications are associated with said at least one choice point.