IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
US-0781497
(2010-05-17)
|
등록번호 |
US-8965826
(2015-02-24)
|
발명자
/ 주소 |
|
출원인 / 주소 |
- International Business Machines Corporation
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
0 인용 특허 :
8 |
초록
▼
A method of performing constraint satisfaction problem (CSP) solving. The method comprises evaluating the nodes of a CSP tree for a TRUE or FALSE state according to a script, wherein the tree models a CSP problem and the script associates rules and corresponding actions with each tree node. During a
A method of performing constraint satisfaction problem (CSP) solving. The method comprises evaluating the nodes of a CSP tree for a TRUE or FALSE state according to a script, wherein the tree models a CSP problem and the script associates rules and corresponding actions with each tree node. During a step of evaluating a specific node, there is dynamically computed a backjump pointer according to a specific rule associated with the specific node, wherein the value of the computed backjump pointer identifies an ancestor node of the tree. Upon a failure to evaluate the node to a TRUE state, the evaluation is restarted at the ancestor node identified by the backjump pointer.
대표청구항
▼
1. A computer-readable non-transitory storage medium comprising program code for controlling a computer to perform constraint satisfaction problem (CSP) solving, the program code comprising code for evaluating variables at nodes of a CSP tree for a TRUE or FALSE state according to a script user-defi
1. A computer-readable non-transitory storage medium comprising program code for controlling a computer to perform constraint satisfaction problem (CSP) solving, the program code comprising code for evaluating variables at nodes of a CSP tree for a TRUE or FALSE state according to a script user-defined for each specific CSP, wherein the tree models a CSP problem and the script associates rules and corresponding actions with each tree node,code executed during a step of evaluating a variable at a specific node, for computing a backjump pointer according to a specific user-defined rule associated with the specific node and CSP, wherein the value of the computed backjump pointer identifies a node of the tree, wherein the specific node receives information from a parent node and computes the backjump pointer based on the received information, the received information including one or more attribute-value pairs corresponding to attributes of a variable evaluated at an ancestor node,code executed upon evaluating the specific node to a TRUE state, for pushing state information created by other user-defined rules in the specific node and attribute-value pairs for the variable evaluated at the specific node to a child node to be used by the child node to compute a backjump pointer from the child node, andcode executed upon a failure to evaluate the node to a TRUE state, for restarting evaluation at the node identified by the backjump pointer. 2. The storage medium of claim 1 further comprising code for passing the value of the computed backjump pointer from the specific node under evaluation to a child node of the specific node under evaluation for use in subsequently determining a backjump pointer from the child node. 3. The storage medium of claim 2 further comprising code to be executed at a child node of the specific node to calculate a new backjump pointer according to a rule associated with the child node. 4. The storage medium of claim 1 further comprising code to be executed at the specific node under evaluation for generating second information according to a rule and passing the second information to a child node for computing a backjump pointer at the child node. 5. The storage medium of claim 1 further comprising code to be executed at the specific node under evaluation for restarting evaluation at a parent node of the specific node under evaluation if the backjump pointer has no valid value. 6. A computer system for performing constraint satisfaction problem (CSP) solving, comprising an engine for evaluating variables at nodes of a CSP tree for a TRUE or FALSE state according to a script user-defined for each specific CSP, wherein the tree models a CSP problem and the script associates rules and corresponding actions with each tree node,during an evaluation of a variable at a specific node, the engine computes a backjump pointer according to a specific user-defined rule associated with the specific node and CSP, wherein the value of the computed backjump pointer identifies a node of the tree, wherein the specific node receives information from a parent node and computes the backjump pointer based on the received information, the received information including one or more attribute-value pairs corresponding to attributes of a variable evaluated at an ancestor node,upon evaluating the specific node to a TRUE state, pushing state information created by other user-defined rules in the specific node and attribute-value pairs for the variable evaluated at the specific node to a child node to be used by the child node to compute a backjump pointer from the child node, andupon a failure to evaluate the specific node to a TRUE state, the engine restarts evaluation at the node identified by the backjump pointer. 7. The computer system of claim 6 wherein the engine further comprises program code for passing the value of the computed backjump pointer from the specific node under evaluation to a child node of the tree. 8. The computer system of claim 7 wherein the engine further comprises program code executed at the child node wherein the child node can calculate a new backjump pointer according to a rule associated with the child node. 9. The computer system of claim 6, wherein the engine further comprises program code executed at the specific node under evaluation to generate second information according to a rule and to pass the second information to a child node for computing a backjump pointer at the child node. 10. The computer system of claim 6 wherein the engine further comprises program code executed at the specific node under evaluation to restart evaluation at a parent node of the specific node under evaluation if the backjump pointer has no valid value. 11. A method of performing constraint satisfaction problem (CSP) solving, comprising evaluating nodes of a CSP tree for a TRUE or FALSE state according to a script, wherein the tree models a CSP problem and the script associates rules and corresponding actions with each tree node,during a step of evaluating a specific node, computing a backjump pointer according to a specific user-defined rule associated with the specific node and CSP, wherein the value of the computed backjump pointer identifies a node of the tree, wherein the specific node receives information from a parent node and computes the backjump pointer based on the received information, the received information including one or more attribute-value pairs corresponding to attributes of a variable evaluated at an ancestor node,upon evaluating the specific node to a TRUE state, pushing state information created by user-defined rules in the specific node and attribute-value pairs for the variable evaluated at the specific node to a child node to be used by the child node to compute a backjump pointer from the child node, andupon a failure to evaluate the specific node to a TRUE state, restarting evaluation at the node identified by the backjump pointer. 12. The method of claim 11 further comprising passing the value of the computed backjump pointer from the specific node under evaluation to a child node of the tree. 13. The method of claim 12 wherein a descendent node can calculate a new backjump pointer according to a rule associated with the child node. 14. The method of claim 11 further comprising at the specific node under evaluation generating second information according to a rule and passing the second information to a descendent node. 15. The method of claim 11 further comprising at the specific node under evaluation restarting evaluation at a parent node of the specific node under evaluation if the backjump pointer has no valid value.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.