didppy.ForwardRecursion

class didppy.ForwardRecursion(model, time_limit=None, quiet=False, initial_registry_capacity=1000000)

Forward recursion solver.

This performs forward recursion while memoizing encountered states.

This solver can handle any types of cost expressions, but the state space must be acyclic. If the state space is cyclic, this solver may fall in an infinite loop.

Parameters:

  • model (Model) – DyPDL model to solve.

  • time_limit (int, float, or None, default: None) – Time limit.

  • quiet (bool, default: False) – Suppress the log output or not.

  • initial_registry_capacity (int, default: 1000000) – Initial size of the data structure storing all generated states.

Raises:

OverflowError – If initial_registry_capacity is negative.

Methods

search()

Search for the optimal solution of a DyPDL model.
search()

Search for the optimal solution of a DyPDL model.

Returns:

Solution.

Return type:

Solution

Raises:

PanicException – If the model is invalid.

Examples

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=1)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=1 + dp.IntExpr.state_cost(),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.Dijkstra(model, quiet=True)
>>> solution = solver.search()
>>> print(solution.cost)
1