ai :: SearchNode :: defaultinit
# A node in the search-tree visited by a `SearchSolver`.
# In search-trees, nodes are labeled with states (`S`), and edges by actions (`A`).
#
# The root node is labeled by the initial state of the problem.
#
# This class is exposed to allow queries on the solution provided by the solver.
class SearchNode[S: Object, A]
# A flag that indicate that `self` is virtually removed from the todo-list.
# `self` was added to the todo-list but that a better node for the
# same state was found latter.
private var drop = false
# The associated problem
var problem: SearchProblem[S, A]
# The state associated to `self`.
# The state labels the node `self`.
var state: S
# Is `self` a root node of the search-tree?
# ensure: `result` == `parent == null` and `result`== `action == null`
fun is_root: Bool do return parent == null
# The previous node in the search-tree (if not root).
var parent: nullable SearchNode[S, A]
# The action used to go from `parent` to `self` (if not root)
# The action labels the edge from `parent` to `self`.
var action: nullable A
# The past cost (g) from the root node to `self`.
var cost: Float
# The heuristic from self to the goal (according to `problem.heuristic(state)`
# It is the future cost (h)
var heuristic: Float is noinit
# The sum of `cost` and `heuristic`
# It is the f function.
var score: Float is noinit
# Update `heuristic` and `score` according to `problem`.
private fun compute_heuristic
do
var h = problem.heuristic(state)
heuristic = h
score = cost + h
end
# The depth of `self` in the search tree
# It is the number of parents to the root node.
var depth: Int
# The number of steps needed by the solver to process `self`
# It is just a useless generation number, but could be used to evaluate
# the behavior of search algorithms.
var steps: Int = 0
# The rank of creation of nodes by the solver.
# It is just a useless generation number, but could be used to evaluate
# the behavior of search algorithms.
var id: Int = 0
# The number of (potential) revisits of `node`.
# This information can be used to debug search algorithms.
# And to detect when heuristics are not admissible.
#
# See `SearchSolver::revisits` and `SearchSolver::do_revisit`
# for details.
var revisits: Int = 0
# Create a new child node for the next state, according to `problem`.
# Used internally by the solvers but made public for those who want to replay a plan.
#
# ensure `result.parent == self`
# ensure `result.action == action`
fun apply_action(action: A): SearchNode[S, A]
do
var new_state = problem.apply_action(state, action)
var new_cost = problem.cost(state, action, new_state)
var new_node = new SearchNode[S, A](problem, new_state, self, action, cost + new_cost, depth+1)
new_node.compute_heuristic
return new_node
end
# Build the sequence of nodes from the initial node to `self`
#
# ensure `result.first.is_root and result.last == self`
fun path: Sequence[SearchNode[S, A]]
do
var res = new List[SearchNode[S, 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 SearchNode[S, A] = self
while node != null do
var a = node.action
if a != null then res.unshift(a)
node = node.parent
end
return res
end
# Just print a detailed path on the screen
fun dump
do
print "result:{state}"
for n in path do
var a = n.action
if a != null then print " + {a}"
print " {n.steps}: {n.state} ({n.cost}$)"
end
end
redef fun to_s do return "#{steps}/{id} d={depth} f={cost+heuristic} g={cost} h={heuristic}: {state}"
#redef fun to_s do return "#{steps} f={(cost+heuristic).to_i} g={cost.to_i} h={heuristic.to_i}"
end
lib/ai/search.nit:614,1--741,3