This class is intended to explore structures that match 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 intelligence.
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 paths 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 a case, nothing is said about what
is a solution and what is a context. The implementations usually
have to provide it.
A good understanding of how that class works 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 these actions can be done):
+ stand-alone actions
- 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.
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. Conversely, 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.
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. Conversely, if search_is_success=True,
then a solution is found and 'search_next'
can be called again to get the next solution.
This occurs if either a solution is found
(and then search_is_success=True) or no solution
is found (and then search_is_success=False).
That feature should be modified only by continue
and backtrack.
Restore the context to the last saved one and drop it.
The saved context MUST be removed.
Called each time that the last alternative (of the
previous alternative point) is starting.
Should be similar to context_restore followed by context_cut.
from init_exploration(explorer) explorer.search_first until explorer.is_off loop treat_solution(explorer) explorer.search_next endThe exploration is the enumeration of all the paths in an abstract structure made of alternatives or sequences of goals to satisfy.+ stand-alone actions - 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'.