--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# This file is free software, which comes along with NIT. This software is
+# distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
+# without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+# PARTICULAR PURPOSE. You can modify it is you want, provided this header
+# is kept unaltered, and a notification of the changes is added.
+# You are allowed to redistribute it and sell it, alone or is a part of
+# another product.
+
+# Basic framework for active backtrack solver
+#
+# This module provides a simple abstract class `BacktrackProblem[S,A]` to be specialized for a specific problem.
+#
+# The concrete class `BacktrackSolver` is used to configure, query, and run a solver for a given problem.
+module backtrack
+
+# Abstract backtrack problem of states (`S`) and actions (`A`).
+#
+# This class serves to model search problems using a backtracking approach.
+# A state, `S`, is a point in the search problem and fully model a given state of the world.
+# An action, `A`, is an available mean of transition between two states.
+# While there is a potential large number of distinct states and actions, there should be only
+# a small number of possible actions from a specific state (thus, a small, or at least finite, branching factor).
+#
+# The point this class is that the state is a mutable object, the roles of the actions is to modify
+# the state.
+#
+# This abstract class is generic and made to work with any kind of states and actions.
+# Therefore, specific subclasses must be developed to implements the required services:
+#
+# * `initial_state`
+# * `actions`
+# * `apply_action`
+# * `backtrack`
+# * `is_goal`
+#
+# # Basic search
+#
+# The method `solve` returns a new solver for a backtrack search.
+class BacktrackProblem[S: Object,A]
+ # The starting state of the problem.
+ # It is this object that will be modified by `apply_action` and `backtrack`.
+ fun initial_state: S is abstract
+
+ # The available and applicable actions for a given state
+ # Because of `backtracking`, actions must also be reversible (see `backtrack`).
+ #
+ # If there is no available actions, null (or an empty collection) must be returned.
+ #
+ # In order to optimise the search time, it is sensible to return `null`
+ # (or an empty collection) as early as possible.
+ #
+ # Node: to help some specific implementations, the current node is also available.
+ # See `BacktrackNode` for details.
+ fun actions(state: S, node: BacktrackNode[A]): nullable Collection[A] is abstract
+
+ # Modify `state` by applying `action`
+ # The `action` comes from an earlier invocation of `actions`.
+ fun apply_action(state: S, action: A) is abstract
+
+ # Modify `state` by undoing `action`
+ # Because of this method, it is important that any action can be undone
+ # knowing only the post-state and the action.
+ fun backtrack(state: S, action: A) is abstract
+
+ # Is the state a goal state?
+ # Once a goal state is found, the solver is automatically stopped.
+ # See `BacktrackSolver.run`.
+ fun is_goal(state: S): Bool is abstract
+
+ # Return a new solver
+ fun solve: BacktrackSolver[S,A] do
+ return new BacktrackSolver[S,A](self, initial_state)
+ end
+end
+
+# 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.
+#
+# ~~~~
+# 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
+ 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
+
+# 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
nitlanguage / nit.git / commitdiff