didppy.WeightedAstar

class didppy.WeightedAstar(model, weight, f_operator=Ellipsis, primal_bound=None, time_limit=None, get_all_solutions=False, quiet=False, initial_registry_capacity=1000000)

Weighted A* solver.

This performs weighted A* using the dual bound as the heuristic function.

To apply this solver, the cost must be computed in the form of x + state_cost, x * state_cost, didppy.max(x, state_cost), or didppy.min(x, state_cost) where, state_cost is either of IntExpr.state_cost() and FloatExpr.state_cost(), and x is a value independent of state_cost. In addition, the model must be minimization. Otherwise, it cannot compute the cost correctly and may not produce the optimal solution.

Parameters:

model (Model) – DyPDL model to solve`time_limit` or .
weight (int or float) – Weight of the h-value.
f_operator (FOperator, default: FOperator.Plus) – Operator to combine a g-value and the dual bound to compute the f-value. If the cost is computed by +, this should be Plus. If the cost is computed by *, this should be Product. If the cost is computed by max, this should be Max. If the cost is computed by min, this should be Min.
primal_bound (int, float, or None, default: None) – Primal bound.
time_limit (int, float, or None, default: None) – Time limit.
get_all_solutions (bool, default: False) – Return a solution if it is not improving when search_next() is called.
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:

TypeError – If the type of primal_bound and the cost type of model are different.
OverflowError – If initial_registry_capacity is negative.
PanicException – If time_limit is negative.

Examples

Example with + operator.

>>> 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.WeightedAstar(model, weight=1.5, quiet=True)
>>> solution = solver.search()
>>> print(solution.cost)
1

Example with max operator.

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=2)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=dp.max(x, dp.IntExpr.state_cost()),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.WeightedAstar(model, weight=1.5, f_operator=dp.FOperator.Max, quiet=True)
>>> solution = solver.search()
>>> print(solution.cost)
2

Methods

`search`()	Search for a bounded-suboptimal solution of a DyPDL model.
`search_next`()	Search for the next solution of a DyPDL model.

search()

Search for a bounded-suboptimal 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.WeightedAstar(model, weight=1.5, quiet=True)
>>> solution = solver.search()
>>> solution.cost
1

search_next()

Search for the next solution of a DyPDL model.

Returns:

solution (Solution) – Solution.
terminated (bool) – Whether the search is terminated.

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.WeightedAstar(model, weight=1.5, quiet=True)
>>> solution, terminated = solver.search_next()
>>> solution.cost
1
>>> terminated
True