ai :: BacktrackNode :: defaultinit
# 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