S
) and actions (A
).This class serves to model search problems using a backtracking approach.
A state, S
, is a point in the search problem and fully model a given state of the world.
An action, A
, is an available mean of transition between two states.
While there is a potential large number of distinct states and actions, there should be only
a small number of possible actions from a specific state (thus, a small, or at least finite, branching factor).
The point this class is that the state is a mutable object, the roles of the actions is to modify the state.
This abstract class is generic and made to work with any kind of states and actions. Therefore, specific subclasses must be developed to implements the required services:
The method solve
returns a new solver for a backtrack search.
ai :: BacktrackProblem :: actions
The available and applicable actions for a given stateai :: BacktrackProblem :: apply_action
Modifystate
by applying action
ai :: BacktrackProblem :: defaultinit
ai :: BacktrackProblem :: initial_state
The starting state of the problem.ai $ BacktrackProblem :: SELF
Type of this instance, automatically specialized in every classai :: BacktrackProblem :: actions
The available and applicable actions for a given stateai :: BacktrackProblem :: apply_action
Modifystate
by applying action
core :: Object :: class_factory
Implementation used byget_class
to create the specific class.
core :: Object :: defaultinit
ai :: BacktrackProblem :: defaultinit
ai :: BacktrackProblem :: initial_state
The starting state of the problem.core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
core :: Object :: native_class_name
The class name of the object in CString format.core :: Object :: output_class_name
Display class name on stdout (debug only).ai :: QueenProblem
The (eight-)queens problem, modeled naively as aBacktrackProblem
.
# Abstract backtrack problem of states (`S`) and actions (`A`).
#
# This class serves to model search problems using a backtracking approach.
# A state, `S`, is a point in the search problem and fully model a given state of the world.
# An action, `A`, is an available mean of transition between two states.
# While there is a potential large number of distinct states and actions, there should be only
# a small number of possible actions from a specific state (thus, a small, or at least finite, branching factor).
#
# The point this class is that the state is a mutable object, the roles of the actions is to modify
# the state.
#
# This abstract class is generic and made to work with any kind of states and actions.
# Therefore, specific subclasses must be developed to implements the required services:
#
# * `initial_state`
# * `actions`
# * `apply_action`
# * `backtrack`
# * `is_goal`
#
# # Basic search
#
# The method `solve` returns a new solver for a backtrack search.
abstract class BacktrackProblem[S: Object,A]
# The starting state of the problem.
# It is this object that will be modified by `apply_action` and `backtrack`.
fun initial_state: S is abstract
# The available and applicable actions for a given state
# Because of `backtracking`, actions must also be reversible (see `backtrack`).
#
# If there is no available actions, null (or an empty collection) must be returned.
#
# In order to optimise the search time, it is sensible to return `null`
# (or an empty collection) as early as possible.
#
# Node: to help some specific implementations, the current node is also available.
# See `BacktrackNode` for details.
fun actions(state: S, node: BacktrackNode[A]): nullable Collection[A] is abstract
# Modify `state` by applying `action`
# The `action` comes from an earlier invocation of `actions`.
fun apply_action(state: S, action: A) is abstract
# Modify `state` by undoing `action`
# Because of this method, it is important that any action can be undone
# knowing only the post-state and the action.
fun backtrack(state: S, action: A) is abstract
# Is the state a goal state?
# Once a goal state is found, the solver is automatically stopped.
# See `BacktrackSolver.run`.
fun is_goal(state: S): Bool is abstract
# Return a new solver
fun solve: BacktrackSolver[S,A] do
return new BacktrackSolver[S,A](self, initial_state)
end
end
lib/ai/backtrack.nit:20,1--78,3