1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # This file is free software, which comes along with NIT. This software is
4 # distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
5 # without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
6 # PARTICULAR PURPOSE. You can modify it is you want, provided this header
7 # is kept unaltered, and a notification of the changes is added.
8 # You are allowed to redistribute it and sell it, alone or is a part of
11 # Basic framework for active backtrack solver
13 # This module provides a simple abstract class `BacktrackProblem[S,A]` to be specialized for a specific problem.
15 # The concrete class `BacktrackSolver` is used to configure, query, and run a solver for a given problem.
17 # For an example, see the `queens.nit` program in the `examples` subdirectory.
20 # Abstract backtrack problem of states (`S`) and actions (`A`).
22 # This class serves to model search problems using a backtracking approach.
23 # A state, `S`, is a point in the search problem and fully model a given state of the world.
24 # An action, `A`, is an available mean of transition between two states.
25 # While there is a potential large number of distinct states and actions, there should be only
26 # a small number of possible actions from a specific state (thus, a small, or at least finite, branching factor).
28 # The point this class is that the state is a mutable object, the roles of the actions is to modify
31 # This abstract class is generic and made to work with any kind of states and actions.
32 # Therefore, specific subclasses must be developed to implements the required services:
42 # The method `solve` returns a new solver for a backtrack search.
43 abstract class BacktrackProblem[S
: Object,A
]
44 # The starting state of the problem.
45 # It is this object that will be modified by `apply_action` and `backtrack`.
46 fun initial_state
: S
is abstract
48 # The available and applicable actions for a given state
49 # Because of `backtracking`, actions must also be reversible (see `backtrack`).
51 # If there is no available actions, null (or an empty collection) must be returned.
53 # In order to optimise the search time, it is sensible to return `null`
54 # (or an empty collection) as early as possible.
56 # Node: to help some specific implementations, the current node is also available.
57 # See `BacktrackNode` for details.
58 fun actions
(state
: S
, node
: BacktrackNode[A
]): nullable Collection[A
] is abstract
60 # Modify `state` by applying `action`
61 # The `action` comes from an earlier invocation of `actions`.
62 fun apply_action
(state
: S
, action
: A
) is abstract
64 # Modify `state` by undoing `action`
65 # Because of this method, it is important that any action can be undone
66 # knowing only the post-state and the action.
67 fun backtrack
(state
: S
, action
: A
) is abstract
69 # Is the state a goal state?
70 # Once a goal state is found, the solver is automatically stopped.
71 # See `BacktrackSolver.run`.
72 fun is_goal
(state
: S
): Bool is abstract
75 fun solve
: BacktrackSolver[S
,A
] do
76 return new BacktrackSolver[S
,A
](self, initial_state
)
80 # A running solver for a given problem, that can be configured and controlled.
83 # # Basic run and results.
85 # 1. Instantiate it with the method `solve` from `BacktrackProblem`.
86 # 2. Apply the method `run`, that will search and return a solution.
87 # 3. Retrieve information from the solution.
90 # var p: BacktrackProblem = new MyProblem
91 # var solver = p.solve
92 # var res = solver.run
94 # print "Found solution in {res.depth} actions: {res.plan.join(", ")}"
95 # print "The state of the solution is: {solver.state}"
100 # # Step-by-step runs and multiple runs
102 # The `run_steps` method (see also `steps`, and `steps_limit`) can be used to run only a maximum number of steps.
103 # Thus, this method can be used as a *co-routine* and be run periodically for a small amount of time.
105 # `run` and `run_steps` return the next solution.
106 # A subsequent call to `run` returns the following solution and so on.
108 # When there is no more solutions available, `null` is returned and `is_running` become false.
110 # Between run, the state of the current search can be read.
115 # Internally, solvers use a zipper on the virtual search-tree where nodes are elements in the apply/backtrack graph.
116 # See the class `BacktrackNode` for details
118 # The `run` and `node` methods return a `BacktrackNode` that can be used to retrieve a lot of useful information,
119 # like the full `path` or the `plan`.
120 # If only the solved state is required, the `state` method from the solver gives it.
121 class BacktrackSolver[S
: Object, A
]
122 # The problem currently solved
123 var problem
: BacktrackProblem[S
,A
]
126 # Do not modify it directly: the solver will do that by its own use of
127 # `problem.apply_action` and `problem.backtrack`.
130 # The current `node` in the backtrack-zipper.
131 var node
: nullable BacktrackNode[A
] = null
133 # Is the solver still running?
134 # A running solver has not yet exhausted all the possible solutions.
135 var is_running
= true
138 private fun start
: BacktrackNode[A
]
141 var node
= new BacktrackNode[A
](null, null, 0, 0)
147 # The total steps executed since the beginning.
150 # Limit in the number of steps for a `run`.
152 # One can modify this value then `run` or just call `run_steps`.
154 # Use 0 for no limit.
156 var steps_limit
= 0 is writable
158 # Update `steps_limit` then just run some additional steps.
159 # Return the `node` corresponding to the found solution, or `null` if no solution is found.
160 fun run_steps
(steps
: Int): nullable BacktrackNode[A
]
162 steps_limit
= self.steps
+ steps
166 # Run the solver and return the next solution found (if any).
167 # Return null is one of these is true:
168 # * `steps_limit` is reached
169 # * no more reachable solution, in this case `is_running` become false.
170 fun run
: nullable BacktrackNode[A
]
173 # Not yet started, of finished?
175 if steps
> 0 then return null
177 var res
= problem
.is_goal
(state
)
178 if res
then return node
182 if steps_limit
> 0 and steps
> steps_limit
then break
185 var totry
= node
.totry
187 # It is the first visit in this state?
188 if totry
== null then
189 var actions
= problem
.actions
(state
, node
)
190 if actions
!= null and not actions
.is_empty
then
199 # No remaining actions?
200 if totry
== null or totry
.is_empty
then
204 #print "no more action"
210 problem
.backtrack
(state
, a
)
217 problem
.apply_action
(state
, a
)
218 #print "Play {a or else ""}"
219 node
= new BacktrackNode[A
](node
, a
, node
.depth
+1, steps
)
221 var res
= problem
.is_goal
(state
)
231 redef fun to_s
do return "{node or else "#0"}"
234 # A node in the backtrack-zipper visited by a `BacktrackSolver`.
236 # The solver visits the virtual search tree with a zipper.
238 # A node is the zipper (this class) is associated to:
239 # * a state of the problem (indirectly),
240 # * the actions not yet explored from the state (see `totry`)
241 # * the action that yields to the state (see `action`), used to backtrack.
242 # * and the parent node in the zipper (see `parent`).
244 # There is no direct link between a node and a state; it is unneeded
245 # since the same state is used, and mutated, during the whole execution of the solver.
247 # This class is exposed to allow queries on the solution provided by the solver.
248 class BacktrackNode[A
]
249 # The previous node in the backtrack-zipper
250 var parent
: nullable BacktrackNode[A
]
252 # The last action executed
253 var action
: nullable A
255 # The remaining actions to try from this node
256 var totry
: nullable Array[A
] = null
258 # The depth of `self` in the search-tree.
261 # The number of steps needed by the solver to process `self`.
262 # This is just a useless generation number, but could be used to evaluate
263 # the behavior of search algorithms.
266 # Build a sequence of nodes from the initial node to `self`
267 # ensure `result.first.parent == null and result.last == self`
268 fun path
: Sequence[BacktrackNode[A
]]
270 var res
= new List[BacktrackNode[A
]]
273 while node
!= null do
280 # Build a sequence of actions from the initial state to `self`
281 # See `path` for a more detailed plan.
282 fun plan
: Sequence[A
]
284 var res
= new List[A
]
285 var node
: nullable BacktrackNode[A
] = self
286 while node
!= null do
288 if a
!= null then res
.unshift
(a
)
295 var res
= "#{steps} d={depth}"
297 if tt
!= null then res
+= " tt={tt.join(" ")}"