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.
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.
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.