deferred class ABSTRACT_BACKTRACKING

All features

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

Internal

Internal deferred

Specific to sequences

Specific to alternatives

internal: allocation and collection

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

  • is_on_top: top_sequence = sequence
  • is_first_continuation: current_continuation = sequence
  • previous_top_linked: top_sequence.previous = old top_sequence
  • previous_continuation_linked: top_sequence.continuation = old current_continuation

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
  • previous_top_linked: top_alternative.previous = old top_alternative
  • top_sequence_recorded: top_alternative.top_sequence = old top_sequence
  • continuation_recorded: top_alternative.continuation = old current_continuation

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.

stop_search_loop: BOOLEAN

True if at the end of a search

search

Common search loop to search_first and serch_next

ensure

  • stop_search_loop

cut_until (alternative: ABSTRACT_BACKTRACKING_ALTERNATIVE)

Cut all alternatives until 'alternative'. To cut an alternative is currently to remove it.

ensure

  • definition: top_alternative = alternative

deferred evaluate_current_state

That feature is called to evaluate the current state.

deferred context_clear
deferred context_push
deferred context_restore
deferred context_restore_and_pop
deferred context_cut
top_sequence: ABSTRACT_BACKTRACKING_SEQUENCE

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

current_continuation: ABSTRACT_BACKTRACKING_SEQUENCE

The current continuation path

pop_sequence

Removes the current sequence and replace it by the next sequence in the continuation path.

require

  • top_sequence /= Void
  • current_continuation /= Void

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

  • alternative_poped: top_alternative = old top_alternative.previous
  • top_sequence_restored: top_sequence = old top_alternative.top_sequence
  • continuation_restored: current_continuation = old top_alternative.continuation

remove_top_sequence

Removes the top sequence.

require

  • top_sequence /= Void

ensure

  • top_sequence = old top_sequence.previous

remove_top_alternative

Removes the top alternative.

require

  • top_alternative /= Void

ensure

  • top_alternative = old top_alternative.previous

pool_of_cut_points: ABSTRACT_BACKTRACKING_POOL_OF_CUT_POINT

Bank of cut points

Class invariant