Method and apparatus for transparent backtracking

• US 6,157,922 A
• Filed: 10/24/1997
• Issued: 12/05/2000
• Est. Priority Date: 10/24/1997
• Status: Expired due to Term

• Current Assignee: Open Invention Network LLC
• Original Assignee: Trilogy Development Group Incorporated (ESW Capital, LLC)
• Inventors: Vaughan, Paul William
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US08/957,346
• Time in Patent Office: 1,138 Days
• Field of Search: 706/46, 706/45
• 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 computerized method of backtracking in a program executable in a memory medium of a computer system comprising:

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

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

generating a failure exception in said program associated with said choice point when said at least one alternative is invalid;

specifying a catch point associated with a point of execution in said program wherein said failure exception is generated.

2. The method of claim 1 further comprising:

associating one or more modifications with said choice point.

3. The method of claim 2 further comprising:

undoing said one or more modifications when said at least one alternative is invalid.

4. The method of claim 1 further comprising:

identifying a previous choice point of said choice point having at least one untried alternative;

determining whether said catch point occurs prior to the creation of said previous choice point; and

generating another failure when said catch point does not occur prior to said previous choice point.

5. The method of claim 1 further comprising:

re-running said program to reach a point in said program at which an untried alternative can be selected.

6. The method of claim 5 wherein said re-running further comprises:

regenerating said choice point; and

regenerating a plurality of modifications for said choice point.

7. The method of claim 6 wherein said regenerating said choice point further comprises:

verifying a regenerated set of alternatives with said at least one alternative associated with said choice point.

8. The method of claim 6 wherein said regenerating said plurality of modifications for said choice point further comprises:

verifying a regenerated set of modifications with said plurality of modifications associated with said choice point.

9. A backtracking search system executable in a memory medium on a computer system, said search system comprising:

a search stack residing in said memory medium, 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;

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

an engine coupled to said model and said execution stack, said engine capable of reverting said search system to one of said plurality of catch points of said execution stack and reverting said search stack to a choice point having at least one untried alternative.

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

11. The system of claim 9 wherein said engine is capable of causing said model to recreate a portion of said search execution stack.

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

13. The system of claim 12 wherein said engine is capable of reverting said set of modifications.

14. An article of manufacturing comprising:

a computer usable medium having computer readable program code embodied therein for backtracking in a program comprising;

computer readable program code configured to cause a computer to instantiate a choice point in an executable program said choice point identifying a point of decision in said program, at least one alternative being associated with said choice point;

computer readable program code configured to cause a computer to examine said choice point to find said at least one alternative;

computer readable program code configured to cause a computer to generate a failure exception in said program associated with said choice point when said at least one alternative is invalid; and

computer readable program code configured to cause a computer to specify a catch point associated with a point of execution in said program wherein said failure exception is generated.

15. The article of manufacture of claim 14 further comprising:

computer readable program code configured to cause a computer to associate one or more modifications with said choice point.

16. The article of manufacture of claim 15 further comprising:

computer readable program code configured to cause a computer to undo said one or more modifications when said at least one alternative is invalid.

17. The article of manufacture of claim 14 further comprising:

computer readable program code configured to cause a computer to identify a previous choice point of said choice point having at least one untried alternative;

computer readable program code configured to cause a computer to determine whether said catch point occurs prior to the creation of said previous choice point; and

computer readable program code configured to cause a computer to generate another failure when said catch point does not occur prior to said previous choice point.

18. The article of manufacture of claim 14 further comprising:

computer readable program code configured to cause a computer to re-run said program to reach a point in said program at which an untried alternative can be selected.

19. The article of manufacture of claim 18 wherein said re-running further comprises:

computer readable program code configured to cause a computer to regenerate said choice point; and

computer readable program code configured to cause a computer to regenerate a plurality of modifications for said choice point.

20. The article of manufacture of claim 19 wherein said computer readable program code configured to cause a computer to regenerate said choice point further comprises:

computer readable program code configured to cause a computer to verify a regenerated set of alternatives with said at least one alternative associated with said choice point.

21. The article of manufacture of claim 19 wherein said computer readable program code configured to cause a computer to regenerate said plurality of modifications for said choice point further comprises:

computer readable program code configured to cause a computer to verify a regenerated set of modifications with said plurality of modifications associated with said choice point.