deferred class ABSTRACT_BACKTRACKING

Features exported to ABSTRACT_BACKTRACKING_ALTERNATIVE

This class is intended to explore structures that matches the and/or pattern. The and/or pattern is found for example in the evaluation of the regular expressions, in the evaluation of prolog queries, in solving some generic problem of artificial intelligency.

The instances of the class inheriting ABSTRACT_BACKTRACKING are typically used through code like the following one that enumerate all the solutions:

        from
           init_exploration(explorer)
           explorer.search_first
        until
           explorer.is_off
        loop
           treat_solution(explorer)
           explorer.search_next
        end
The exploration is the enumeration of all the path in an abstract structure made of alternatives or sequences of goals to satisfy.

The class ABSTRACT_BACKTRACKING does not make any assumption on what is explored. That is its strength because it can be used in many situations. In such case, nothing is said of what is a solution and what is a context. The implementations often have to supply it.

A good understanding of how works that class is required if you intend to use it. See also the more easy to use class BACKTRACKING.

See tutorial/backtracking for examples.

The deferred features are 'evaluate_current_state'. 'context_clear', 'context_push', 'context_restore', 'context_restore_and_pop', 'context_cut'.

When the feature 'evaluate_current_state' is called, the implementor must perform actions to process the exploration. Here are some of the common things that can be done (note that one or more of this action can be done):

  + actions enougth by themselves
    - replace the current state by an other state.
    - call 'backtrack': cancel the exploration of the current
      alternative and explore the next alternative.
    - call 'continue': explore the continuation of the
      current alternative.
  + actions that can be mixed but that need to be completed by
    one of the above actions
    - create a sequence of future path to evaluate and push it
      to the continuation path by calling 'push_sequence'.
    - create an alternative of future alternate path and push it
      to the alternative stack by calling 'push_alternative'.
    - push a cut point by calling 'push_cut_point'.
    - remove all alternatives until upper cut point by calling 'cut'.
    - remove all alternatives by calling 'cut_all'.

Because the exploration of and/or abstractions can be huge, that class requires to manage alternatives and sequences in pools.

Direct parents

non-conformant parents

ABSTRACT_BACKTRACKING_GLOBALS

Known children

conformant children

BACKTRACKING

Summary

exported features

Common client features

Control of the exploration

Specific to alternatives

Details

search_first

Resets all and searchs the first solution. The current state must be set. It is the first state, the root of the search. When the feature returns, 'search_is_success' must be checked to know if a solution was found. When search_is_success=False, it means that there is no solution at all. Conversly, if search_is_success=True, then the first solution is found and 'search_next' can be called to get the next solution if it exists.

ensure

  • success_or_off: search_is_success and not is_off or is_off and not search_is_success

search_next

Searchs the next solution. When the feature returns, 'search_is_success' must be checked to know if a solution was found. When search_is_success=False at the end, it means that there is no more solution. Conversly, if search_is_success=True, then a solution is found and 'search_next' can be called again to get the next solution.

require

  • last_search_was_a_success: search_is_success

ensure

  • success_or_off: search_is_success and not is_off or is_off and not search_is_success

search_is_success: BOOLEAN

True when search is successfull

is_off: BOOLEAN

True when search is finished

ensure

  • definition: Result = not search_is_success

clear

Clears the current state to nothing.

ensure

  • cleared: is_cleared
  • no_solution: is_off

is_cleared: BOOLEAN

True if no partial data remain in the current state

ensure

  • no_solution_when_cleared: Result implies is_off

push_sequence (sequence: ABSTRACT_BACKTRACKING_SEQUENCE)

Pushs the 'sequence' in front of the continuation path.

require

  • sequence_not_void: sequence /= Void

ensure

    push_alternative (alternative: ABSTRACT_BACKTRACKING_ALTERNATIVE)

    Pushs the 'alternative' before the continuation path.

    require

    • alternative_not_void: alternative /= Void

    ensure

    • is_on_top: top_alternative = alternative

    continue

    Continues the exploration of the current path.

    backtrack

    Stops the exploration of the current path and tries to explore the next alternative path.

    push_cut_point

    Inserts a cut point into the continuation path. The inserted cut point records the current to of the alternatives.

    cut

    Removes the alternatives until the one recorded by the next cut point in the continuation path.

    cut_all

    Cuts all alternatives.

    top_alternative: ABSTRACT_BACKTRACKING_ALTERNATIVE

    Stack of alternatives represented by its top (can be Void)

    continue_alternative

    Returns to the alternative on the top of the stack and put its saved continuation path as the current continuation path.

    require

    • top_alternative /= Void

    ensure

    • alternative_remain: top_alternative = old top_alternative

    pop_alternative

    Returns to the alternative on the top of the stack and put its saved continuation path as the current continuation path. Remove the alternative from the stack of alternatives. Same as 'continue_alternative' but also removes the alternative.

    require

    • top_alternative /= Void

    ensure

      pool_of_cut_points: ABSTRACT_BACKTRACKING_POOL_OF_CUT_POINT

      Bank of cut points

      Class invariant