solve
from BacktrackProblem
.run
, that will search and return a solution.var p: BacktrackProblem = new MyProblem
var solver = p.solve
var res = solver.run
if res != null then
print "Found solution in {res.depth} actions: {res.plan.join(", ")}"
print "The state of the solution is: {solver.state}"
end
The run_steps
method (see also steps
, and steps_limit
) can be used to run only a maximum number of steps.
Thus, this method can be used as a co-routine and be run periodically for a small amount of time.
run
and run_steps
return the next solution.
A subsequent call to run
returns the following solution and so on.
When there is no more solutions available, null
is returned and is_running
become false.
Between run, the state of the current search can be read.
Internally, solvers use a zipper on the virtual search-tree where nodes are elements in the apply/backtrack graph.
See the class BacktrackNode
for details
The run
and node
methods return a BacktrackNode
that can be used to retrieve a lot of useful information,
like the full path
or the plan
.
If only the solved state is required, the state
method from the solver gives it.
ai :: BacktrackSolver :: defaultinit
ai :: BacktrackSolver :: is_running=
Is the solver still running?ai :: BacktrackSolver :: node
The currentnode
in the backtrack-zipper.
ai :: BacktrackSolver :: node=
The currentnode
in the backtrack-zipper.
ai :: BacktrackSolver :: problem=
The problem currently solvedai :: BacktrackSolver :: run
Run the solver and return the next solution found (if any).ai :: BacktrackSolver :: run_steps
Updatesteps_limit
then just run some additional steps.
ai :: BacktrackSolver :: steps=
The total steps executed since the beginning.ai :: BacktrackSolver :: steps_limit=
Limit in the number of steps for arun
.
ai $ BacktrackSolver :: SELF
Type of this instance, automatically specialized in every classcore :: Object :: class_factory
Implementation used byget_class
to create the specific class.
ai :: BacktrackSolver :: defaultinit
core :: Object :: defaultinit
ai :: BacktrackSolver :: is_running=
Is the solver still running?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.
ai :: BacktrackSolver :: node
The currentnode
in the backtrack-zipper.
ai :: BacktrackSolver :: node=
The currentnode
in the backtrack-zipper.
core :: Object :: output_class_name
Display class name on stdout (debug only).ai :: BacktrackSolver :: problem=
The problem currently solvedai :: BacktrackSolver :: run
Run the solver and return the next solution found (if any).ai :: BacktrackSolver :: run_steps
Updatesteps_limit
then just run some additional steps.
ai :: BacktrackSolver :: steps=
The total steps executed since the beginning.ai :: BacktrackSolver :: steps_limit=
Limit in the number of steps for arun
.
# A running solver for a given problem, that can be configured and controlled.
#
#
# # Basic run and results.
#
# 1. Instantiate it with the method `solve` from `BacktrackProblem`.
# 2. Apply the method `run`, that will search and return a solution.
# 3. Retrieve information from the solution.
#
# ~~~~nitish
# var p: BacktrackProblem = new MyProblem
# var solver = p.solve
# var res = solver.run
# if res != null then
# print "Found solution in {res.depth} actions: {res.plan.join(", ")}"
# print "The state of the solution is: {solver.state}"
# end
# ~~~~
#
#
# # Step-by-step runs and multiple runs
#
# The `run_steps` method (see also `steps`, and `steps_limit`) can be used to run only a maximum number of steps.
# Thus, this method can be used as a *co-routine* and be run periodically for a small amount of time.
#
# `run` and `run_steps` return the next solution.
# A subsequent call to `run` returns the following solution and so on.
#
# When there is no more solutions available, `null` is returned and `is_running` become false.
#
# Between run, the state of the current search can be read.
#
#
# # Search-trees
#
# Internally, solvers use a zipper on the virtual search-tree where nodes are elements in the apply/backtrack graph.
# See the class `BacktrackNode` for details
#
# The `run` and `node` methods return a `BacktrackNode` that can be used to retrieve a lot of useful information,
# like the full `path` or the `plan`.
# If only the solved state is required, the `state` method from the solver gives it.
class BacktrackSolver[S: Object, A]
# The problem currently solved
var problem: BacktrackProblem[S,A]
# The current state.
# Do not modify it directly: the solver will do that by its own use of
# `problem.apply_action` and `problem.backtrack`.
var state: S
# The current `node` in the backtrack-zipper.
var node: nullable BacktrackNode[A] = null
# Is the solver still running?
# A running solver has not yet exhausted all the possible solutions.
var is_running = true
# Initialize `node`
private fun start: BacktrackNode[A]
do
assert node == null
var node = new BacktrackNode[A](null, null, 0, 0)
self.node = node
return node
end
# The total steps executed since the beginning.
var steps = 0
# Limit in the number of steps for a `run`.
#
# One can modify this value then `run` or just call `run_steps`.
#
# Use 0 for no limit.
# Default: 0
var steps_limit = 0 is writable
# Update `steps_limit` then just run some additional steps.
# Return the `node` corresponding to the found solution, or `null` if no solution is found.
fun run_steps(steps: Int): nullable BacktrackNode[A]
do
steps_limit = self.steps + steps
return run
end
# Run the solver and return the next solution found (if any).
# Return null is one of these is true:
# * `steps_limit` is reached
# * no more reachable solution, in this case `is_running` become false.
fun run: nullable BacktrackNode[A]
do
var node = self.node
# Not yet started, of finished?
if node == null then
if steps > 0 then return null
node = start
var res = problem.is_goal(state)
if res then return node
end
loop
if steps_limit > 0 and steps > steps_limit then break
steps += 1
var totry = node.totry
# It is the first visit in this state?
if totry == null then
var actions = problem.actions(state, node)
if actions != null and not actions.is_empty then
totry = actions.to_a
node.totry = totry
end
end
#print state
#print node
# No remaining actions?
if totry == null or totry.is_empty then
#print "Backtrack"
var a = node.action
if a == null then
#print "no more action"
is_running = false
self.node = null
return null
end
problem.backtrack(state, a)
node = node.parent
assert node != null
continue
end
var a = totry.pop
problem.apply_action(state, a)
#print "Play {a or else ""}"
node = new BacktrackNode[A](node, a, node.depth+1, steps)
var res = problem.is_goal(state)
if res then
self.node = node
return node
end
end
self.node = node
return null
end
redef fun to_s do return "{node or else "#0"}"
end
lib/ai/backtrack.nit:80,1--232,3