Packages

class BacktrackingStrategy extends RefiningStrategy

Refining strategies that start with a list of components belonging to a single problem, working bottom-up to expand the model lazily. "Backtracking" refers to the fact that this strategy propagates updates to ensure consistency. For example, if refining the subproblem of an expandable component forces the creation of new subproblems, then the strategy expands subproblems again until this process terminates.

In terms of performance characteristics, it is known that there exist models with n components for which this strategy requires Omega(n2) time. However, upper bounds on running time, as well as sufficient conditions for this algorithm to take linear time, remain open. For an alternative lazy algorithm with better understood performance, consider RecursionDepthStrategy.

Linear Supertypes
RefiningStrategy, AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. BacktrackingStrategy
  2. RefiningStrategy
  3. AnyRef
  4. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new BacktrackingStrategy(problem: Problem, initialComponents: List[ProblemComponent[_]], maxDepth: Int = Int.MaxValue)

    problem

    Problem to refine.

    initialComponents

    List of components belonging to the problem from which to begin bottom-up decomposition.

    maxDepth

    Maximum depth of expansion from the initial components given. Depth is decremented each time the algorithm recurses into a subproblem through an expandable component. When the depth reaches -1, the algorithm returns * for the range of a component. Thus, setting the maximum depth to 0 corresponds to not recursing at all. Defaults to Int.MaxValue for expansion of the entire model (does not terminate on infinite models).

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  4. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  5. def checkArg[T](element: Element[T]): ProblemComponent[T]

    Get the problem component associated with an element.

    Get the problem component associated with an element. This involves adding the element to the collection if a problem component has not yet been created.

    Attributes
    protected
  6. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  7. val collection: ComponentCollection
    Definition Classes
    RefiningStrategy
  8. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  9. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  10. def execute(): Unit

    Execute this decomposition strategy, starting with the initial components.

    Execute this decomposition strategy, starting with the initial components. This should only be called once.

    Definition Classes
    BacktrackingStrategyRefiningStrategy
  11. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  12. def generateRange(comp: ProblemComponent[_]): Unit

    Process a component by generating its range, if it is not already fully enumerated.

    Process a component by generating its range, if it is not already fully enumerated. After calling this method, it may be necessary to check if the component is fully enumerated or refined.

    comp

    Component to process.

    Definition Classes
    RefiningStrategy
  13. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  14. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  15. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  16. def markProblemsUnsolved(problems: Set[Problem]): Unit

    Recursively marks as unsolved any problem whose solution could have changed as a result of refinement by this strategy or any of its recursively generated strategies.

    Recursively marks as unsolved any problem whose solution could have changed as a result of refinement by this strategy or any of its recursively generated strategies.

    Attributes
    protected
    Definition Classes
    RefiningStrategy
  17. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  18. final def notify(): Unit
    Definition Classes
    AnyRef
  19. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  20. def process[V](comp: ProblemComponent[V], depth: Int): Unit

    Generate the range for the given component.

    Generate the range for the given component. Mark it as fully refined or enumerated if applicable.

    comp

    Component to process.

    depth

    Depth of expansion.

  21. def processAtomic[V](atomicComp: AtomicComponent[V]): Unit

    Generate the range for the given atomic component.

    Generate the range for the given atomic component. Mark it as fully refined or enumerated if applicable.

    atomicComp

    Atomic component to process.

  22. def processChain[P, V](chainComp: ChainComponent[P, V], depth: Int): Unit

    Generate the range for the given Chain component.

    Generate the range for the given Chain component. Mark it as fully refined or enumerated if applicable.

    chainComp

    Chain component to process.

    depth

    Depth of expansion with respect to this component.

  23. def processMakeArray[V](maComp: MakeArrayComponent[V], depth: Int): Unit

    Generate the range for the given MakeArray component.

    Generate the range for the given MakeArray component. Mark it as fully refined or enumerated if applicable.

    maComp

    MakeArray component to process.

    depth

    Depth of expansion.

  24. def refine(comp: ProblemComponent[_], depth: Int): Unit

    Decompose a single problem component by recursively decomposing components on which it depends, then generating the range for each component.

    Decompose a single problem component by recursively decomposing components on which it depends, then generating the range for each component. This guarantees that when ranges are created, all components on which a component depends (at that depth) will have been processed.

    As a rule, this method never works in the other direction. If component B depends (directly or indirectly) on component A, then calling decompose on A will never recursively call decompose on component B. This is to avoid infinite loops, and to guarantee that the range of A does not unpredictably change in the middle of a call to decompose A.

    Once the range has been created, the depths map is updated. If any previously visited components depend on comp, this method updates those components in a top-down manner.

    comp

    Component to decompose. This strategy never decomposes a component more than once, so if the component is fully refined or has already been expanded to the desired depth, this method does nothing.

    depth

    Depth of expansion with respect to this component.

  25. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  26. def toString(): String
    Definition Classes
    AnyRef → Any
  27. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  28. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  29. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )

Inherited from RefiningStrategy

Inherited from AnyRef

Inherited from Any

Ungrouped