Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.opencyc.constraintsolver
Class ForwardCheckingSearcher

    java.lang.Object
      |
      +--org.opencyc.constraintsolver.ForwardCheckingSearcher

public class ForwardCheckingSearcher
extends java.lang.Object

The `ForwardCheckingSearcher` object to perform forward checking search for one or more solutions to the `ConstraintProblem`.

Author:
  Stephen L. Reed

  Copyright 2001 Cycorp, Inc., license is open source GNU LGPL.

  the license

  www.opencyc.org

  OpenCyc at SourceForge

  THIS SOFTWARE AND KNOWLEDGE BASE CONTENT ARE PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OPENCYC ORGANIZATION OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE AND KNOWLEDGE BASE CONTENT, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

See Also:
  `UnitTest#testConstraintProblem`

Field Summary
`protected static int` | `ASK_ALL_OR_INDIV_THRESHOLD` When instantiating a rule having one variable left to instantiate for subsequent asking the KB, this parameter sets the threshold beyond which a variable is used in the ask -- returning what bindings are known (or proven) in the KB.
`protected ConstraintProblem` | `constraintProblem` Reference to the parent `ConstraintProblem` object.
`protected java.util.ArrayList` | `constraintRules` Reference to the collection of the constraint rules used in the search for solution(s).
`protected int` | `nbrSteps` Number of search steps performed during the search for solution(s).
`protected Solution` | `solution` Reference to the `Solution` for the parent `ConstraintProblem` object.
`protected ValueDomains` | `valueDomains` Reference to the `ValueDomains` object for the parent `ConstraintProblem` object.
`protected int` | `verbosity` Sets verbosity of the constraint solver output.

Constructor Summary
`ForwardCheckingSearcher(ConstraintProblem constraintProblem)` Constructs a new `FowardCheckingSearcher` object.

Method Summary
`protected java.util.ArrayList` | `askWithVariable(CycList instantiatedRule, CycVariable variable)` Returns a list of bindings for single unbound variable left in the rule.
`protected boolean` | `checkForwardDifferentRule(ConstraintRule rule, java.util.ArrayList remainingRuleVariables, int level, Binding currentBinding)` Applies the all-different constraint rule to the remaining domains and returns `true` iff no domains are wiped out.
`protected boolean` | `checkForwardInstantiatedRule(CycList instantiatedRule, java.util.ArrayList remainingRuleVariables, java.util.ArrayList bindings, int level, Binding currentBinding)` Recurses to instantiate the rule in the constraint problem microtheory with all remaining variables as bindings.
`protected boolean` | `checkForwardNonEvaluatableRule(ConstraintRule rule, int level, Binding currentBinding)` Performs forward checking of the given non-evaluatable rule to restrict the domains of remaining variables.
`protected boolean` | `checkForwardRule(ConstraintRule rule, java.util.ArrayList remainingRuleVariables, int level, Binding currentBinding)` Performs forward checking of the given rule to restrict the domains of remaining variables.
`protected boolean` | `checkForwardRules(java.util.ArrayList remainingVariables, int level, Binding currentBinding)` Performs forward checking of applicable rules to restrict the domains of remaining variables.
`protected int` | `constraintDegree(CycVariable variable, java.util.ArrayList variables)` Returns the number of constraint rules applicable to variable and one or more of the other variables.
`protected void` | `markPermittedRemainingBindings(CycList instantiatedRule, java.util.ArrayList remainingVariables, java.util.ArrayList bindings, Binding currentBinding, ConstraintRule currentRule)` Recurses to instantiate the constraint rule in the constraint problem KB microtheory with all remaining variables as bindings, marking the domain values as permitted with `Boolean` `true`.
`protected void` | `restore(java.util.ArrayList remainingVariables, int level)` Restores the eliminated value choices for constraint variables due to a backtrack in the search.
`boolean` | `search(java.util.ArrayList variables, int level)` Performs a depth-first search of the solution space, using forward checking to prune alternatives.
`protected CycVariable` | `selectVariable(java.util.ArrayList variables)` From the list of variables, heuristically chooses the one most likely to narrow the remaining search space.
`void` | `setVerbosity(int verbosity)` Sets verbosity of the constraint solver output.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### verbosity

    protected int verbosity

  Sets verbosity of the constraint solver output. 0 --> quiet ... 9 -> maximum diagnostic input.

### constraintProblem

    protected ConstraintProblem constraintProblem

  Reference to the parent `ConstraintProblem` object.

### constraintRules

    protected java.util.ArrayList constraintRules

  Reference to the collection of the constraint rules used in the search for solution(s).

### solution

    protected Solution solution

  Reference to the `Solution` for the parent `ConstraintProblem` object.

### valueDomains

    protected ValueDomains valueDomains

  Reference to the `ValueDomains` object for the parent `ConstraintProblem` object.

### ASK_ALL_OR_INDIV_THRESHOLD

    protected static final int ASK_ALL_OR_INDIV_THRESHOLD

  When instantiating a rule having one variable left to instantiate for subsequent asking the KB, this parameter sets the threshold beyond which a variable is used in the ask -- returning what bindings are known (or proven) in the KB. Under this threshold, the rule is fully instantiated for the of each variable binding in the unmarked value domain and the KB ask is performed on each of these.

### nbrSteps

    protected int nbrSteps

  Number of search steps performed during the search for solution(s).

Constructor Detail

### ForwardCheckingSearcher

    public ForwardCheckingSearcher(ConstraintProblem constraintProblem)

  Constructs a new `FowardCheckingSearcher` object.
  Parameters:
    `constraintProblem` - the parent constraint problem

Method Detail

### setVerbosity

    public void setVerbosity(int verbosity)

  Sets verbosity of the constraint solver output. 0 --> quiet ... 9 -> maximum diagnostic input.
  Parameters:
    `verbosity` - 0 --> quiet ... 9 -> maximum diagnostic input

### search

    public boolean search(java.util.ArrayList variables,
                          int level)
                   throws java.io.IOException,
                          CycApiException

  Performs a depth-first search of the solution space, using forward checking to prune alternatives. Employs recursion to search subtrees.
  Parameters:
    `variables` - is the `ArrayList` of remaining variables to solve
    `level` - is the current depth of the search
  Returns:
    `true` when done with the search

### selectVariable

    protected CycVariable selectVariable(java.util.ArrayList variables)

  From the list of variables, heuristically chooses the one most likely to narrow the remaining search space.
  Parameters:
    `variables` - the `ArrayList` of variables from which the choice is made
  Returns:
    the variable most likely to narrow the remaining search space

### checkForwardRules

    protected boolean checkForwardRules(java.util.ArrayList remainingVariables,
                                        int level,
                                        Binding currentBinding)
                                 throws java.io.IOException,
                                        CycApiException

  Performs forward checking of applicable rules to restrict the domains of remaining variables. Returns `true` iff no remaining variable domains are wiped out.
  Parameters:
    `remainingVariables` - the `ArrayList` of variables for which no domain values have yet been bound
    `currentBinding` - the current variable and bound value
  Returns:
    `true` iff no remaining variable domains are wiped out

### checkForwardRule

    protected boolean checkForwardRule(ConstraintRule rule,
                                       java.util.ArrayList remainingRuleVariables,
                                       int level,
                                       Binding currentBinding)
                                throws java.io.IOException,
                                       CycApiException

  Performs forward checking of the given rule to restrict the domains of remaining variables. Returns `true` iff no remaining variable domains are wiped out. Delegates forward checking to specific methods for all-different constraint, evaluatable constraint, non-evaluatable constraint. Non-evaluatable constraints are asked in the knowledge base rather than evaluated in the constraint solver object.
  Parameters:
    `rule` - the constraint rule
    `remainingRuleVariables` - the `ArrayList` of rule variables for which no domain values have yet been bound
    `level` - the current level of solution search depth
    `currentBinding` - the current variable and bound value
  Returns:
    `true` iff no remaining variable domains are wiped out

### checkForwardNonEvaluatableRule

    protected boolean checkForwardNonEvaluatableRule(ConstraintRule rule,
                                                     int level,
                                                     Binding currentBinding)
                                              throws java.io.IOException,
                                                     CycApiException

  Performs forward checking of the given non-evaluatable rule to restrict the domains of remaining variables. Returns `true` iff no remaining variable domains are wiped out. Non-evaluatable constraints are asked in the knowledge base rather than evaluated in the constraint solver object.
  Parameters:
    `rule` - the constraint rule
    `level` - the current level of solution search depth
    `currentBinding` - the current variable and bound value
  Returns:
    `true` iff no remaining variable domains are wiped out

### markPermittedRemainingBindings

    protected void markPermittedRemainingBindings(CycList instantiatedRule,
                                                  java.util.ArrayList remainingVariables,
                                                  java.util.ArrayList bindings,
                                                  Binding currentBinding,
                                                  ConstraintRule currentRule)
                                           throws java.io.IOException,
                                                  CycApiException

  Recurses to instantiate the constraint rule in the constraint problem KB microtheory with all remaining variables as bindings, marking the domain values as permitted with `Boolean` `true`.
  Parameters:
    `instantiatedRule` - the constraint rule
    `remainingVariables` - the variables left to instantiate in the constraint rule
    `bindings` - the instantiated values for variables already instantiated in the constraint rule

### askWithVariable

    protected java.util.ArrayList askWithVariable(CycList instantiatedRule,
                                                  CycVariable variable)
                                           throws java.io.IOException,
                                                  CycApiException

  Returns a list of bindings for single unbound variable left in the rule.
  Parameters:
    `instantiatedRule` - the rule in `CycList` form which has a single unbound variable
    `variable` - the variable for which bindings are sought
  Returns:
    a `ArrayList` of bindings for single unbound variable left in the rule

### checkForwardDifferentRule

    protected boolean checkForwardDifferentRule(ConstraintRule rule,
                                                java.util.ArrayList remainingRuleVariables,
                                                int level,
                                                Binding currentBinding)

  Applies the all-different constraint rule to the remaining domains and returns `true` iff no domains are wiped out.
  Parameters:
    `rule` - the all-different constraint rule
    `remainingRuleVariables` - the variables left to instantiate in the constraint rule
    `level` - the current level of solution search depth
    `currentBinding` - the current variable and bound value
  Returns:
    `true` iff no remaining variable domains are wiped out

### checkForwardInstantiatedRule

    protected boolean checkForwardInstantiatedRule(CycList instantiatedRule,
                                                   java.util.ArrayList remainingRuleVariables,
                                                   java.util.ArrayList bindings,
                                                   int level,
                                                   Binding currentBinding)
                                            throws java.io.IOException

  Recurses to instantiate the rule in the constraint problem microtheory with all remaining variables as bindings. Returns `true` iff no domains are wiped out.
  Parameters:
    `rule` - the instantiated constraint rule
    `remainingRuleVariables` - the variables left to instantiate in the constraint rule
    `bindings` - the list of bindings instantiated so far
    `level` - the current level of solution search depth
    `currentBinding` - the current variable and bound value
  Returns:
    `true` iff no remaining variable domains are wiped out

### restore

    protected void restore(java.util.ArrayList remainingVariables,
                           int level)

  Restores the eliminated value choices for constraint variables due to a backtrack in the search.

### constraintDegree

    protected int constraintDegree(CycVariable variable,
                                   java.util.ArrayList variables)

  Returns the number of constraint rules applicable to variable and one or more of the other variables.
  Parameters:
    `variable` - the variable which must be used in the counted constraint rules
    `variables` - the counted constraint rules must use only these variables and no others.
  Returns:
    the number of constraint rules applicable to variable and one or more of the other variables

Overview | Package | Class | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD