ai :: BacktrackNode
BacktrackSolver
.The solver visits the virtual search tree with a zipper.
A node is the zipper (this class) is associated to:
totry
)action
), used to backtrack.parent
).There is no direct link between a node and a state; it is unneeded since the same state is used, and mutated, during the whole execution of the solver.
This class is exposed to allow queries on the solution provided by the solver.
ai :: BacktrackNode :: _parent
The previous node in the backtrack-zipperai :: BacktrackNode :: _steps
The number of steps needed by the solver to processself
.
ai :: BacktrackNode :: defaultinit
ai :: BacktrackNode :: depth=
The depth ofself
in the search-tree.
ai :: BacktrackNode :: parent
The previous node in the backtrack-zipperai :: BacktrackNode :: parent=
The previous node in the backtrack-zipperai :: BacktrackNode :: path
Build a sequence of nodes from the initial node toself
ai :: BacktrackNode :: steps
The number of steps needed by the solver to processself
.
ai :: BacktrackNode :: steps=
The number of steps needed by the solver to processself
.
ai $ BacktrackNode :: SELF
Type of this instance, automatically specialized in every classai :: BacktrackNode :: _parent
The previous node in the backtrack-zipperai :: BacktrackNode :: _steps
The number of steps needed by the solver to processself
.
core :: Object :: class_factory
Implementation used byget_class
to create the specific class.
core :: Object :: defaultinit
ai :: BacktrackNode :: defaultinit
ai :: BacktrackNode :: depth=
The depth ofself
in the search-tree.
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 :: BacktrackNode :: parent
The previous node in the backtrack-zipperai :: BacktrackNode :: parent=
The previous node in the backtrack-zipperai :: BacktrackNode :: path
Build a sequence of nodes from the initial node toself
ai :: BacktrackNode :: steps
The number of steps needed by the solver to processself
.
ai :: BacktrackNode :: steps=
The number of steps needed by the solver to processself
.
# A node in the backtrack-zipper visited by a `BacktrackSolver`.
#
# The solver visits the virtual search tree with a zipper.
#
# A node is the zipper (this class) is associated to:
# * a state of the problem (indirectly),
# * the actions not yet explored from the state (see `totry`)
# * the action that yields to the state (see `action`), used to backtrack.
# * and the parent node in the zipper (see `parent`).
#
# There is no direct link between a node and a state; it is unneeded
# since the same state is used, and mutated, during the whole execution of the solver.
#
# This class is exposed to allow queries on the solution provided by the solver.
class BacktrackNode[A]
# The previous node in the backtrack-zipper
var parent: nullable BacktrackNode[A]
# The last action executed
var action: nullable A
# The remaining actions to try from this node
var totry: nullable Array[A] = null
# The depth of `self` in the search-tree.
var depth: Int
# The number of steps needed by the solver to process `self`.
# This is just a useless generation number, but could be used to evaluate
# the behavior of search algorithms.
var steps: Int
# Build a sequence of nodes from the initial node to `self`
# ensure `result.first.parent == null and result.last == self`
fun path: Sequence[BacktrackNode[A]]
do
var res = new List[BacktrackNode[A]]
res.add(self)
var node = parent
while node != null do
res.unshift(node)
node = node.parent
end
return res
end
# Build a sequence of actions from the initial state to `self`
# See `path` for a more detailed plan.
fun plan: Sequence[A]
do
var res = new List[A]
var node: nullable BacktrackNode[A] = self
while node != null do
var a = node.action
if a != null then res.unshift(a)
node = node.parent
end
return res
end
redef fun to_s do
var res = "#{steps} d={depth}"
var tt = totry
if tt != null then res += " tt={tt.join(" ")}"
return res
end
end
lib/ai/backtrack.nit:234,1--300,3