didppy.ExpressionBeamSearch
- class didppy.ExpressionBeamSearch
Beam search solver using expressions to compute heuristic values.
This performs beam search using user-defined cost expressions as cost and heuristic functions.
To apply this solver, the user-defined cost must be computed in the form of
x + state_cost
,x * state_cost
,didppy.max(x, state_cost)
, ordidppy.min(x, state_cost)
where,state_cost
is either ofIntExpr.state_cost()
andFloatExpr.state_cost()
, andx
is a value independent ofstate_cost
. Otherwise, it cannot compute the cost correctly.This solver does not have a guarantee for optimality.
- Parameters:
model (Model) – DyPDL model to solve.
beam_size (int) – Beam size.
custom_cost_dict (dict[str, Union[IntExpr|IntVar|IntResourceVar|FloatExpr|FloatVar|FloatResourceVar|int|float] or None, default: None) – Expressions to compute g-values. A g-value is the cost of the path from the target state to the current state. A key is the name of a transition, and the value is an expression to compute a g-value. An expression can use
IntExpr.state_cost()
orFloatExpr.state_cost()
, which returns the current g-value. If the name of a transition is not included, its cost expression is used. IfNone
, the cost expressions in the DyPDL model are used for all transitions.h_expression (IntExpr, IntVar, IntResourceVar, FloatExpr, FloatVar, FloatResourceVar, int, float, or None, default: None) – Expression to compute an h-value.
f_operator (FOperator, default: FOperator.Plus) – Operator to combine a g-value and the base cost. If the cost is computed by
+
, this should bePlus
. If the cost is computed by*
, this should beProduct
. If the cost is computed bymax
, this should beMax
. If the cost is computed bymin
, this should beMin
. This solver keeps topb
best nodes with regard to f-values at each depth.custom_f_operator (FOperator, default: FOperator.Plus) – Operator to combine a g-value and the h-value to compute the f-value. If the custom cost is computed by
+
, this should bePlus
. If the custom cost is computed by*
, this should beProduct
. If the custom cost is computed bymax
, this should beMax
. If the custom cost is computed bymin
, this should beMin
. This solver keeps topb
best nodes with regard to f-values at each depth.maximize (bool, default: False) – Maximize f-values or not. Greater f-values are better if
True
, and smaller are better ifFalse
.keep_all_layers (bool, default: False) – Keep all layers of the search graph for duplicate detection in memory.
time_limit (int, float, or None, default: None) – Time limit.
quiet (bool, default: False) – Suppress the log output or not.
float_custom_cost (bool or None, default: None) – Use continuous values for g-, h-, and f-values. The cost type of the model is used if
None
.
- Raises:
TypeError – If the custom cost type is int and
h_evaluator
or a value incustom_cost_dict
isFloatExpr
,FloatVar
,FloatResourceVar
, orfloat
.OverflowError – If
beam_size
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.ExpressionBeamSearch(model, 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.ExpressionBeamSearch(model, f_operator=dp.FOperator.Max, quiet=True) >>> solution = solver.search() >>> print(solution.cost) 2
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:
- 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.ExpressionBeamSearch(model, quiet=True) >>> solution = solver.search() >>> print(solution.cost) 1